Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
input = sys.stdin.readline

H,W=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

from collections import deque
QUE=deque()

for i in range(H):
    for j in range(W):

        if MAP[i][j]=="#":
            QUE.append([i,j,0])

ANS=[[-1]*W for i in range(H)]

while QUE:
    NQUE=deque()
    while QUE:
        x,y,z=QUE.pop()
        ANS[x][y]=z

        for nx,ny in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:
            if nx<0 or ny<0 or nx>=H or ny>=W:
                continue

            if ANS[nx][ny]!=-1:
                continue

            NQUE.append([nx,ny,z+1])

    QUE=NQUE

            
print(max([max(ANS[i]) for i in range(H)]))
    
    


### FIXED CODE ###

import sys
input = sys.stdin.readline

H,W=map(int,input().split())
MAP=[list(input().strip()) for i in range(H)]

ANS=[[-1]*W for i in range(H)]

from collections import deque
QUE=deque()

for i in range(H):
    for j in range(W):

        if MAP[i][j]=="#":
            QUE.append([i,j,0])
            ANS[i][j]=0

while QUE:
    NQUE=deque()
    while QUE:
        x,y,z=QUE.pop()

        for nx,ny in [[x+1,y],[x-1,y],[x,y+1],[x,y-1]]:
            if nx<0 or ny<0 or nx>=H or ny>=W:
                continue

            if ANS[nx][ny]!=-1:
                continue

            NQUE.append([nx,ny,z+1])
            ANS[nx][ny]=z+1

    QUE=NQUE

            
print(max([max(ANS[i]) for i in range(H)]))
### BUGGY CODE ###

from collections import deque

# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs(sx, gx, sy, gy):
    # すべての点を INF で初期化
    d = [[float("inf")] * m for i in range(n)]

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        if p[0] == gx and p[1] == gy:
            break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]

n, m = map(int, input().split())
maze = [list(input()) for i in range(n)]
ans = 1

for x in range(n):
    for y in range(m):
        sx = x
        sy = y
        for i in range(n):
            for j in range(m):
                gx = i
                gy = j
                if sx == gx and sy == gy:
                    continue
                if maze[sx][sy] == "#" or maze[gx][gy] == "#":
                    continue
                A = bfs(sx, gx, sy, gy)
                ans = max(A, ans)
print(ans)

### FIXED CODE ###

from collections import deque
import numpy as np

# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs(sx, sy):
    # すべての点を INF で初期化
    d = [[float("-inf")] * m for i in range(n)]

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        #if p[0] == gx and p[1] == gy:
        #    break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] != "#" and d[nx][ny] == float("-inf"):
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    a = np.max(d) 
    return a

n, m = map(int, input().split())
maze = [list(input()) for i in range(n)]
ans = 1

for x in range(n):
    for y in range(m):
        sx = x
        sy = y
        if maze[sx][sy] == "#":
            continue
        A = bfs(sx, sy)
        ans = max(A, ans)
print(int(ans))
### BUGGY CODE ###

from collections import Counter
S=raw_input()

L=len(S)

ans=L/2
for r in range(L/2,L):
	C=Counter(S[L-r-1:r+1])
	if len(C)==1:
		ans=r+1

print ans

### FIXED CODE ###

S=raw_input()
N=len(S)
TS=N
for k in range(N-1):
	if S[k]!=S[k+1]:
		TS=min(TS, max(k+1, N-k-1))

print TS
### BUGGY CODE ###

N=int(input())
ans=1
A=list(map(int,input().split()))
for i in A:
  ans*=i
if ans>1000000000000000000:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

def kai():
    N=int(input())
    A=list(map(int,input().split()))
    
    if  0 in A:
        print(0)
        return
    
    ans=1
    for i in A:
        ans*=i
        if ans>10**18:
            print(-1)
            return
    print(ans)
    return
kai()
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))

from collections import Counter
c = Counter(a)
for k in c.keys():
    if c[k] == 2:
        break
l = []
for i in range(len(a)):
    if a[i] == k:
        l.append(i)

ll = l[0]
rr = len(a) - 1 - l[1]
d =  ll + rr

tmp = 1
dc = 1
for k in range(1, n + 2):
    tmp = tmp * (n - k + 2) // k
    # print(tmp)

    if k == 1:
        dc = 1
    elif d >= k - 1:
        dc = dc * (d - k + 2) // (k - 1)
    else:
        dc = 0
    print((tmp - dc) % (10 ** 9 + 7))


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))

from collections import Counter
c = Counter(a)
for k in c.keys():
    if c[k] == 2:
        break
l = []
for i in range(len(a)):
    if a[i] == k:
        l.append(i)
    if len(l) == 2:
        break
d = n - l[1] + l[0]

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y // 2) ** 2 % mod
    else            : return power(x, y // 2) ** 2 * x % mod

mod = (10 ** 9 + 7)

N1 = n + 2
factorial1 = [1]
for i in range(1, N1):
    factorial1.append(factorial1[i - 1] * i % mod)
inverseFactorial1 = [0] * N1
inverseFactorial1[N1 - 1] = power(factorial1[N1 - 1], mod - 2)
for i in range(N1 - 2, -1, -1):
    inverseFactorial1[i] = inverseFactorial1[i + 1] * (i + 1) % mod
def combi1(x, y):
    return factorial1[x] * inverseFactorial1[y] * inverseFactorial1[x - y] % mod

for k in range(1, n + 2):
    if d >= k - 1:
        print((combi1(n+1, k) - combi1(d, k-1)) % mod)
    else:
        print(combi1(n+1, k))
### BUGGY CODE ###

dp = [[0]*3001 for _ in range(3001)]
n,s = (int(num) for num in input().split())
a = [int(num) for num in input().split()]
MOD = 998244353
dp[0][0] = 1
for i in range(1,n+1):
    for j in range(s+1):
        dp[i][j] = (dp[i-1][j] * 2) % MOD
        if j >= a[i-1]:
            dp[i][j] = (dp[i][j] + dp[i-1][j-a[i-1]])%MOD
            
print(dp[n][s])

### FIXED CODE ###

dp = [[0]*3001 for _ in range(3001)]
n,s = (int(num) for num in input().split())
a = [int(num) for num in input().split()]
MOD = 998244353
dp[0][0] = 1
for i in range(1,n+1):
    for j in range(s+1):
        dp[i][j] = (dp[i-1][j] * 2) % MOD
        if j >= a[i-1]:
            dp[i][j] = (dp[i][j] + dp[i-1][j-a[i-1]])%MOD
            
print(dp[n][s])
### BUGGY CODE ###

from functools import lru_cache
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
left = -10**9
right = 10**9

@lru_cache(maxsize=100000)
def cal(num):
  tmp = 0
  for i in range(n):
    tmp += abs(a[i]-(num+(i+1)))
  return tmp
 

while abs(right-left)>1:
  mid = (right+left)//2
  if cal(mid-1)<cal(mid+1):
    right = mid
  else:
    left = mid
print(min(cal(left),cal(right)))

### FIXED CODE ###

from functools import lru_cache
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
left = -10**9
right = 10**9

@lru_cache(maxsize=100000)
def cal(num):
  tmp = 0
  for i in range(n):
    tmp += abs(a[i]-(num+(i+1)))
  return tmp
 

while abs(right-left)>1:
  mid = (right+left)//2
  if cal(mid-1)<cal(mid+1):
    right = mid
  else:
    left = mid
print(min(cal(left),cal(right)))
### BUGGY CODE ###

n,m = map(int,input().split())
ab = []
for _ in range(m):
    a=int(input())
    ab.append(a)

dp = [0]*(n+1)
dp[0] = 1

for i in range(1, n+1):
    dp[i] = (dp[i-1] + dp[i-2])
    if i in ab:
        dp[i] = 0

print(dp[-1]%1000000007)

### FIXED CODE ###

N, M = map(int, input().split())
a = set([int(input()) for i in range(M)])
 
dp = [0] * (N+1)
dp[0] = 1
for i in range(1, N+1):
    dp[i] = (dp[i-1] + dp[i-2]) % (10**9+7)
    if i in a:
        dp[i] = 0
print(dp[N])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
i = 0
SUM = 1
while i < N:
    SUM = SUM * A[i]
    i += 1

if SUM > 10**18:
    print(-1)
    
else:
    print(SUM)

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    SUM = 1

    if 0 in A:
        print(0)
        return

    for a in A:
        SUM = SUM * a
        if SUM > 1000000000000000000:
            print(-1)
            return

    print(SUM)
main()
### BUGGY CODE ###

N = int(input())
S = input()

ans = 0

for i in range(1000):
    t = str(i).zfill(3)
    t_index = 0
    for s_index in range(N):
        if S[s_index] == t[t_index]:
            t_index += 1
            if t_index == 3:
                break
    if t_index == 3:
        ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
S = tuple(map(int, input()))

ans = 0

for i in range(10):
    if i in S[:N - 2]:
        i_index = S.index(i)
        for j in range(10):
            if j in S[i_index + 1: N - 1]:
                j_index = i_index + S[i_index + 1: N - 1].index(j) + 1
                for k in range(10):
                    if k in S[j_index + 1:]:
                        ans += 1
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
h = tuple(map(int, input().split()))
inf = 10**9
dp = [inf]*n
dp[0] = 0
for i in range(n):
    for j in range(1, k+1):
        step = i+j
        if step < n:
            dp[step] = min(dp[step], dp[i]+abs(h[step]-h[i]))
print(dp[-1])


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    stones = tuple(map(int, input().split()))
    inf = 10**9
    dp = [inf]*n
    dp[0] = 0
    for i in range(n):
        for t in range(1, k+1):
            step = i+t
            if step < n:
                v = dp[i]+abs(stones[i]-stones[step])
                if v < dp[step]:
                    dp[step] = v
    print(dp[-1])


if __name__ == '__main__':    
    main()
### BUGGY CODE ###

n = int(input())
s = input()
char_list = list(s)
sum=0

for i in range(n):
    for j in range(n):
        for k in range(n):
            #print("i,j,k:{},{},{}".format(i,j,k))
            if not (i<j<k):
                continue
            if ([char_list[i],char_list[j],char_list[k]]==["R", "G", "B"])&(j-i!=k-j):
                sum+=1
                #print("i,j,k:{},{},{}".format(i,j,k))
            elif ([char_list[i],char_list[j],char_list[k]]==["R", "B", "G"])&(j-i!=k-j):
                sum+=1
                #print("i,j,k:{},{},{}".format(i,j,k))
            elif ([char_list[i],char_list[j],char_list[k]]==["G", "R", "B"])&(j-i!=k-j):
                sum+=1
                #print("i,j,k:{},{},{}".format(i,j,k))
            elif ([char_list[i],char_list[j],char_list[k]]==["G", "B", "R"])&(j-i!=k-j):
                sum+=1
                #print("i,j,k:{},{},{}".format(i,j,k))
            elif ([char_list[i],char_list[j],char_list[k]]==["B", "G", "R"])&(j-i!=k-j):
                sum+=1
                #print("i,j,k:{},{},{}".format(i,j,k))
            elif ([char_list[i],char_list[j],char_list[k]]==["B", "R", "G"])&(j-i!=k-j):
                sum+=1
                #print("i,j,k:{},{},{}".format(i,j,k))

print(sum)


### FIXED CODE ###

n=int(input())
s=input()
r=s.count("R")
g=s.count("G")
b=s.count("B")
ans=r*g*b

for i in range(n):
    for d in range(n):
        j=i+d
        k=j+d
        if k>=n:
            break
        if (s[i]!=s[j]) & (s[j]!=s[k]) & (s[k]!=s[i]):
            ans-=1

print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
for i in range(1, n + 1):
  if i != n:
    print(a.index(i) + 1, end=" ")
  else:
    print(a.index(i) + 1)


### FIXED CODE ###

n = int(input())
a = [int(i) - 1 for i in input().split()]
ans = [-1 for _ in range(n)]
for i in range(n):
  ans[a[i]] = i
for i in range(n):
  print(ans[i] + 1, end=" ")
### BUGGY CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

N,Q = II()
a = [0]*(N-1)
b = [0]*(N-1)
p = [0]*Q
x = [0]*Q

for i in range(N-1):
    a1,b1 = II()
    a[i] = a1-1
    b[i] = b1-1

for i in range(Q):
    p1,x1 = II()
    p[i] = p1-1
    x[i] = x1


#深さ優先探索
def dfs(pt,v):
    n=len(pt)
    d=[-1]*n
    check_visited = [False]*n
    check_visited[v] = True
    S = [v]
    d[v] = 0
    while S:
        v1 = S.pop()
        for i in pt[v1]:
            if check_visited[i] == False:
                check_visited[i] = True
                d[i] = d[v1] + 1
                S.append(i)
    return d


pt = defaultdict(list)
for i in range(N-1):
    pt[a[i]].append(b[i])
    pt[b[i]].append(a[i])
d = dfs(pt,0)

parent = defaultdict(list)
for i in range(N-1):
    if d[a[i]]>d[b[i]]:
        parent[a[i]].append(b[i])
    else:
        parent[b[i]].append(a[i])

val = [0]*N
for i in range(Q):
    val[p[i]] += x[i]

for i in range(N):
    now = i
    ans = 0
    while now != 0:
        ans += val[now]
        now = parent[now][0]
    print(val[0]+ans)

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

N,Q = II()
a = [0]*(N-1)
b = [0]*(N-1)
p = [0]*Q
x = [0]*Q

for i in range(N-1):
    a1,b1 = II()
    a[i] = a1-1
    b[i] = b1-1

for i in range(Q):
    p1,x1 = II()
    p[i] = p1-1
    x[i] = x1


parent = defaultdict(list)
for i in range(N-1):
    parent[b[i]].append(a[i])

val = [0]*N
for i in range(Q):
    val[p[i]] += x[i]

for i in range(1,N):
    val[i] += val[parent[i][0]]

print(*val)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))

mod = 7 + 10**9
s = 0
for i in range(N-1): 
	for	j in range(i+1, N):
		t = A[i] * A[j] 
		s += t
        
ans = s % mod
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))

ans = 0
mod = 7 + 10**9

s = sum(A)
for i in range(N):
	s -= A[i]
	ans += s * A[i]
	ans %= mod

print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(lambda x: int(x)-1, input().split()))
now = 0
visited = [now]
while A[now] not in visited:
    visited.append(A[now])
    now = A[now]
L = len(visited)
looplen = L-visited.index(A[now])
if K < L:
    print(visited[K]+1)
else:
    print(visited[L-looplen+(K-L)%looplen]+1)

### FIXED CODE ###

#!/usr/bin/env python3
import sys

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    count = 1
    now = 0
    visited = [1]
    set_v = set()
    set_v.add(1)
    l = -1
    while count < N:
        x = A[now]
        if x in set_v:
            l = visited.index(x)
            break
        else:
            count += 1
            visited.append(x)
            set_v.add(x)
            now = x-1
    r = count
    # print(l,r,visited)
    
    if K < l:
        print(visited[K])
    else:
        print(visited[l + (K-l) % (r-l)])

if __name__ == '__main__':
    main()
### BUGGY CODE ###

N,K = [int(i) for i in input().split()]
n = [int(i) for i in input().split()]
max=0
for i in range(N-K+1):
    tmp = sum(n[i:i+K]) 
    if tmp  > max:
        max=tmp 

print((max+K)*0.5)


### FIXED CODE ###

import numpy as np

N,K = [int(i) for i in input().split()]
n = np.array([int(i) for i in input().split()])
n=(n+1)
t=np.empty(N+1)
t[0] = 0
t[1:]=np.cumsum(n)
print(max(t[K:]-t[:-K])*0.5)
### BUGGY CODE ###

n, m = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(n)]
AB.sort(key=lambda ab: -ab[1])
counts = [0] * m
cands = [0] * m
total = 0
for a, b in AB:
    if a > m:
        continue
    for i in range(a - 1 + counts[a - 1], m):
        if cands[i] > 0:
            continue
        cands[i] = b
        counts[a - 1] += 1
        total += 1
        break
    if total == m:
        break
print(sum(cands))


### FIXED CODE ###

import heapq

n, m = map(int, input().split())

cands = [[] for _ in range(m)]
for _ in range(n):
    a, b = map(int, input().split())
    if a <= m:
        cands[a - 1].append(-b)

heapq.heapify(cands[0])
total = 0
for i in range(m):
    if len(cands[0]) > 0:
        total -= heapq.heappop(cands[0])
    if i < m - 1:
        for c in cands[i + 1]:
            heapq.heappush(cands[0], c)

print(total)
### BUGGY CODE ###

X=input()
A=len(X)
for i in range(A//2):
  X=X.replace("ST","")
print(len(X))

### FIXED CODE ###

L=0
R=0
X=list(input())
A=len(X)
for i in range(A):
  if X[i]=="S":
    R=R+1
  elif X[i]=="T":
    if R!=0:
      L=L+1
      R=R-1
print(A-2*L)
### BUGGY CODE ###

a = int(input())
b = list(input())
cr = []
for i in range(a):
    count = 0
    count += b[0:i].count("W")
    count += b[i+1:a].count("E")
    cr.append(count)
print(min(cr))

### FIXED CODE ###

a = int(input())
b = list(input())
e = b.count("E")
w = 0
z = e
for c in b:
    if c == "E":
        e -= 1
    else:
        w += 1
    if e + w < z:
        z = e + w
print(z)
### BUGGY CODE ###

import re
s = input()
first_len = len(s)
ans = 0

while True:
    s = s.replace("01","").replace("10","")
    if not re.search('01|10',s):
        break

# print(len(s),first_len - len(s),s)
print(first_len - len(s))

### FIXED CODE ###

import re
s = input()
first_len = len(s)

ten_3_zo = "0" * 10 * 10 * 10 + "1" * 10 * 10 * 10
ten_3_oz = "1" * 10 * 10 * 10 + "0" * 10 * 10 * 10

ten_1_zo = "0" * 10 + "1" * 10
ten_1_oz = "1" * 10 + "0" * 10


while True:
    s = s.replace(ten_3_zo,"").replace(ten_3_oz,"")
    s = s.replace(ten_1_zo,"").replace(ten_1_oz,"")
    s = s.replace("01","").replace("10","")
    if not re.search('01|10',s):
        break

print(first_len - len(s))
### BUGGY CODE ###

N,P=map(int,input().split())
S=input()
ans=0

if P==2 or P==5:
  for i in range(N):
    s=int(S[i])
    if s%P==0:
      ans+=i+1
  print(ans)
  exit()

U=[0]*(N+1)

for i in range(N):
  s=S[i:]
  s=int(s)
  U[i]+=s%P

for i in range(N):
  for j in range(i,N):
    if (U[i]-U[j+1])%P==0:
      ans+=1
print(ans)

### FIXED CODE ###

from collections import defaultdict

N,P=map(int,input().split())
S=input()

def solMin():
  dp=[[0]*P for i in range(N+1)]
  
  for i,s in enumerate(map(int,S), start=1):
    dp[i][s%P]+=1
    for p in range(P):
      dp[i][(p*10+s)%P]+=dp[i-1][p]
  
  return sum(dp[i][0] for i in range(N+1))

def solLarge():
  cnt=defaultdict(int)
  ret=0
  now=0
  
  for d,s in enumerate(map(int, S[::-1])):
    now+=pow(10,d,P)*s
    now%=P
    ret+=cnt[(now-P)%P]
    if now==0:
      ret +=1
    cnt[now]+=1
  
  return ret

print(solMin() if P*N<=10**6 else solLarge())
### BUGGY CODE ###

#hozon
[N,L] = [int(x) for x in input().split()]
A = {}
B = [0]*N
ANS = {}
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    B[i] = x
    if x in A : A[x] += [i]
    else : A[x] = [i]
for i in sorted(A) :
    for j in A[i] :
        for k in range(L) :
            if j + k not in ANS :
                ANS[j+k] = i
                count += 1
    if count > N * 0.999 : break
        
for i in range(L):
    if i not in ANS : ANS[i] = min(B[:i+1])
for i in range(L,N):
    if i not in ANS : ANS[i] = min(B[i+1-L:i+1])
for i in range(L-1,N-1) : print(ANS[i], end=" ")
print(ANS[N-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

n = int(input())
d = [[] for i in range(n)]
for i in range(n - 1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    d[u].append(v)
    d[v].append(u)
ans = 0
for l in range(n):
    cur = 0
    for r in range(l, n):
        cur += 1
        for t in d[r]:
            if l <= t < r:
                cur -= 1
        ans += cur
print(ans)

### FIXED CODE ###

n = int(input())
d = [0] * n
present = [[] for i in range(n)]
for i in range(n - 1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    if u > v:
        u, v = v, u
    d[v] += 1
    present[u].append(v)
ans = 0
cur = 0
for v in range(n):
    cur += (n - v) * d[v]
for l in range(n):
    ans += (l + 1) * (l + 2) // 2
    ans -= cur
    for v in present[l]:
        cur -= (n - v)
print(ans)
### BUGGY CODE ###

# bin/env/pypy3
import sys
import collections
import heapq
import math
n = int(sys.stdin.readline())
a = list(map(int,sys.stdin.readline().split()))
c = collections.Counter(a)
#print(n,a,c)
memo_f = {}
memo_c = {}
def combinations_count(n, r):
    return n*(n-1)//2
    s = str([n,r])
    if s in memo_c:
        return memo_c[s]
    if not n in memo_f: memo_f[n] = math.factorial(n)
    b = max(n - r,0)
    if not b in memo_f: memo_f[b] = math.factorial(b)
    if not r in memo_f: memo_f[r] = math.factorial(r)
    memo_c[s] = memo_f[n] // (memo_f[b] * memo_f[r])
    return memo_c[s]
memo_e = {}
for e in a:
    if not e in memo_e:
        c[e] -= 1
        b = [combinations_count(v,2) for v in c.values() if v > 1]
        memo_e[e] = sum(b)
        c[e] += 1
    print(memo_e[e])

### FIXED CODE ###

# bin/env/pypy3
import sys
import collections
n = int(sys.stdin.readline())
a = list(map(int,sys.stdin.readline().split()))
c = collections.Counter(a)
#print(n,a,c)
memo_e = {}
s = sum(v*(v-1)//2 for v in c.values() if v > 1)
for e in a:
    if not e in memo_e:
        #c[e] -= 1
        if 1 < c[e]:
            memo_e[e] = s - (c[e]*(c[e]-1)//2 - (c[e]-1)*(c[e]-2)//2)
        else:
            memo_e[e] = s
    print(memo_e[e])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))

ans = n
for i in range(n):
    x = a[i]
    sum_a = a[i]
    for j in range(i + 1, n):
        x ^= a[j]
        sum_a += a[j]
        if sum_a == x:
            ans += 1
        else:
            break
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))

ans = 0
sum_a = 0
r = 0
for l in range(n):
    while r < n:
        x = a[r]
        if sum_a & x != 0:
            break
        sum_a += x
        r += 1
    ans += r - l
    sum_a -= a[l]
print(ans)