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

import itertools

N = int(input())
for n in range(1,N+1):
    if n<6: 
        print(0)
        continue
    cnt = 0
    for x,y,z in itertools.product(list(range(1,n)),repeat=3):
        if n == x*x + y*y +z*z + x*y + y*z + z*x:
            cnt += 1
    print(cnt)

### FIXED CODE ###

import itertools

N = int(input())
lst = [0]*N
for x,y,z in itertools.product(list(range(1,int(N**0.5))),repeat=3):
    val = x*x + y*y + z*z + x*y + y*z + z*x
    if val <= N:
        lst[val-1] += 1
print(*lst,sep="\n")
### BUGGY CODE ###

import itertools
from collections import Counter
N = int(input().strip())
seq_list = [''.join(sorted(input().strip())) for _ in range(N)]
hash = {}
for seq in seq_list:
  if seq[0] in hash:
    hash[seq[0]] += [seq]
  else:
    hash[seq[0]] = [seq]
result = 0
for s in hash.values():
  if len(s) < 2: continue
  result += len([1 for i,j in itertools.combinations(range(len(s)), 2) if s[i] == s[j]])
print(result)


### FIXED CODE ###

import itertools
N = int(input().strip())
seq_list = [''.join(sorted(input().strip())) for _ in range(N)]
hash = {}
result = 0
for seq in seq_list:
  if seq in hash:
    result += hash[seq]
    hash[seq] += 1
  else:
    hash[seq] = 1
print(result)
### BUGGY CODE ###

import collections

def main():
    N  = int(input()) 
    A=list(map(int, input().split()))
    C = collections.Counter(A)
    B = list(set(A))
    B.sort()
    lenb = len(B)
    Boo = [True]*lenb
    s,_ = sieve((10**6)+5)

    if C[1]>1:
        print(0)
        return
    if C[1]==1:
        print(1)
        return

    for i in range(lenb):
        if Boo[i] and B[i]<500004:
            temp = Boo[i]*2 -1
            for j in range(i+1,lenb):
                if Boo[j] and s[B[j]-1]==False and B[j]>temp and B[j] % B[i] == 0:
                    Boo[j] = False

    cnt = 0
    for i in range(lenb):
        if Boo[i] and C[B[i]]==1:
            cnt += 1

    print(cnt)


def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table


if __name__ == '__main__':
    main()

### FIXED CODE ###

import collections

def main():
    N  = int(input()) 
    A=list(map(int, input().split()))
    C = collections.Counter(A)
    B = list(set(A))
    B.sort()
    lenb = len(B)
    Boo = [True]*lenb
    ZENBU = [False]*(10**6+4)

    if C[1]>1:
        print(0)
        return
    if C[1]==1:
        print(1)
        return

    for i in range(lenb):
        temp = 2
        if ZENBU[B[i]]==False:
            while B[i]*temp < 1000002:
                ZENBU[B[i]*temp] = True
                temp+=1

    cnt = 0
    for i in range(lenb):
        if ZENBU[B[i]]==False and C[B[i]]==1:
            cnt += 1

    print(cnt)


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

N = int(input())
A = [int(x) for x in input().split()]

flg = True
if N%2 == 0:
  for i in range(1, N, 2): flg &= A.count(i) == 2
else:
  flg &= A.count(0) == 1
  for i in range(2, N+1, 2): flg &= A.count(i) == 2

print(2**(N//2) if flg else 0)


### FIXED CODE ###

N = int(input())
A = sorted([int(x) for x in input().split()])

flg = True
if N%2 == 0:
  for i in range(0, N//2): flg &= A[2*i] == A[2*i+1] == 2*i+1
else:
  flg &= A[0] == 0
  for i in range(1, (N+1)//2): flg &= A[2*i-1] == A[2*i] == 2*i

def modpow(n, r, m):
  if r == 0: return 1
  if r%2 == 0: return modpow(n, r//2, m)**2 % m
  return n * modpow(n, r-1, m) % m

print(modpow(2, N//2, 10**9+7) if flg else 0)
### BUGGY CODE ###

import fractions
N,M = map(int,input().split())
S = input(); T = input()
gcd = fractions.gcd(N,M)
N_prime = N //gcd; M_prime = M // gcd
for i in range(0,N,N_prime):
    for j in range(0,M,M_prime):
        if i * M_prime - j * N_prime == 0 and S[i] != T[j]:
            print(-1)
            exit()
print(N*M // gcd)

### FIXED CODE ###

import fractions
N,M = map(int,input().split())
S = input(); T = input()
gcd = fractions.gcd(N,M)
N_prime = N //gcd; M_prime = M // gcd
for i in range(0,N,N_prime):
    for j in range(0,M,M_prime):
        if i * M_prime - j * N_prime == 0 and S[i] != T[j]:
            print(-1)
            exit()
print(N*M // gcd)
### BUGGY CODE ###

N = input()
ans = 1
n = len(N)
for i in range(n-1):
    for j in range(i, n):
        if N[i] != N[j]:
            ans += 1
print(ans)

### FIXED CODE ###

N = input()
ans = 0
n = len(N)
a = N.count("a")
ans += a * (a-1) // 2
a = N.count("b")
ans += a * (a-1) // 2
a = N.count("c")
ans += a * (a-1) // 2
a = N.count("d")
ans += a * (a-1) // 2
a = N.count("e")
ans += a * (a-1) // 2
a = N.count("f")
ans += a * (a-1) // 2
a = N.count("g")
ans += a * (a-1) // 2
a = N.count("h")
ans += a * (a-1) // 2
a = N.count("i")
ans += a * (a-1) // 2
a = N.count("j")
ans += a * (a-1) // 2
a = N.count("k")
ans += a * (a-1) // 2
a = N.count("l")
ans += a * (a-1) // 2
a = N.count("m")
ans += a * (a-1) // 2
a = N.count("n")
ans += a * (a-1) // 2
a = N.count("o")
ans += a * (a-1) // 2
a = N.count("p")
ans += a * (a-1) // 2
a = N.count("q")
ans += a * (a-1) // 2
a = N.count("r")
ans += a * (a-1) // 2
a = N.count("s")
ans += a * (a-1) // 2
a = N.count("t")
ans += a * (a-1) // 2
a = N.count("u")
ans += a * (a-1) // 2
a = N.count("v")
ans += a * (a-1) // 2
a = N.count("w")
ans += a * (a-1) // 2
a = N.count("x")
ans += a * (a-1) // 2
a = N.count("y")
ans += a * (a-1) // 2
a = N.count("z")
ans += a * (a-1) // 2
ans = n * (n-1) // 2 - ans + 1
print(ans)
### BUGGY CODE ###

import queue

H,W = map(int,input().split())
C = [int(i)+1 for i in input().split()]
D = [int(i)+1 for i in input().split()]

l = []
l.append([-1]*(W+4))
l.append([-1]*(W+4))
for _ in range(H):
    l.append([-1,-1]+ [0 if i=="." else -1 for i in input()] + [-1,-1])
l.append([-1]*(W+4))
l.append([-1]*(W+4))

l[C[0]][C[1]] = 1 

def p():
    for i in l[2:2+H]:
        print(",".join([str(j) for j in i[2:2+W]]))

q = queue.Queue()
q.put(C)
now = 1
q2 = queue.Queue()
while True:
    while not q.empty():
        x,y = q.get()
        q2.put([x,y])
        for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
            if l[x+i][y+j] ==0:
                q.put([x+i,y+j])
                l[x+i][y+j] = now
    if l[D[0]][D[1]] > 0:
        print(l[D[0]][D[1]]-1)
        break
    now += 1
    if q2.empty():
        print(-1)
        break
    while not q2.empty():
        x,y = q2.get()
        for i in range(-2,3):
            for j in range(-2,3):
                if l[x+i][y+j] ==0:
                    q.put([x+i,y+j])
                    l[x+i][y+j] = now
    if l[D[0]][D[1]] > 0:
        print(l[D[0]][D[1]]-1) 
        break
    

### FIXED CODE ###

import queue

H,W = map(int,input().split())
C = [int(i)+1 for i in input().split()]
D = [int(i)+1 for i in input().split()]

l = []
l.append([-1]*(W+4))
l.append([-1]*(W+4))
for _ in range(H):
    l.append([-1,-1]+ [0 if i=="." else -1 for i in input()] + [-1,-1])
l.append([-1]*(W+4))
l.append([-1]*(W+4))

l[C[0]][C[1]] = 1 

def p():
    for i in l[2:2+H]:
        print(",".join([str(j) for j in i[2:2+W]]))

q = queue.Queue()
q.put(C)
now = 1
q2 = queue.Queue()
while True:
    while not q.empty():
        x,y = q.get()
        q2.put([x,y])
        for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
            if l[x+i][y+j] ==0:
                q.put([x+i,y+j])
                l[x+i][y+j] = now
    if l[D[0]][D[1]] > 0:
        print(l[D[0]][D[1]]-1)
        break
    now += 1
    if q2.empty():
        print(-1)
        break
    while not q2.empty():
        x,y = q2.get()
        for i in range(-2,3):
            for j in range(-2,3):
                if l[x+i][y+j] ==0:
                    q.put([x+i,y+j])
                    l[x+i][y+j] = now
    if l[D[0]][D[1]] > 0:
        print(l[D[0]][D[1]]-1) 
        break
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
for i in range(N-K):
    mae = 1
    ato = 1
    for j in range(K):
        #print(i,j)
        mae = mae*A[K-j+i-1]
        #print(A[K-j+i-1])
        ato = ato*A[K-j+i]
        #print(A[K-j+i])
    if mae < ato:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
for i in range(N-K):
    if A[i] < A[i+K]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

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

Vdic = [{}, {}]
# 0: even 1: odd
for i in range(len(V_list)):
    v = V_list[i]

    tmp = (i + 1) % 2
    Vdic[tmp][v] = Vdic[tmp].get(v, 0) + 1

even = sorted(Vdic[0].values())
odd = sorted(Vdic[1].values())

ans_even = [(-1, 0)]
ans_odd = [(-2, 0)]
if(len(even) == 1):
    t = max(Vdic[0], key=Vdic[0].get)
    ans_even.append((t, even[0]))
else:
    n1 = even[-1]
    n2 = even[-2]

    ans_even = [(k, v) for k, v in Vdic[0].items() if v == n1 or v == n2]

if(len(odd) == 1):
    t = max(Vdic[1], key=Vdic[1].get)
    ans_odd.append((t, odd[0]))
else:
    n1 = odd[-1]
    n2 = odd[-2]

    ans_odd = [(k, v) for k, v in Vdic[1].items() if v == n1 or v == n2]

# print(ans_even, ans_odd)

ans = []
for ke, ve in ans_even:
    for ko, vo in ans_odd:
        if(ke != ko):
            ans.append(n - ve - vo)

print(min(ans))

### FIXED CODE ###

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

Vdic = [{}, {}]
# 0: even 1: odd
for i in range(len(V_list)):
    v = V_list[i]

    tmp = (i + 1) % 2
    Vdic[tmp][v] = Vdic[tmp].get(v, 0) + 1

even = sorted(Vdic[0].values())
odd = sorted(Vdic[1].values())

ans_even = [(-1, 0)]
ans_odd = [(-2, 0)]
if(len(even) == 1):
    t = max(Vdic[0], key=Vdic[0].get)
    ans_even.append((t, even[0]))
else:
    n1 = even[-1]
    n2 = even[-2]

    f1 = True
    f2 = True
    if(n1 == n2):
        for k, v in Vdic[0].items():
            if(v == n1):
                if(f1 is False and f2 is False):
                    continue
                if(f1 is False):
                    f2 = False
                f1 = False
                ans_even.append((k, v))
    else:
        for k, v in Vdic[0].items():
            if(v == n1 and f1 is True):
                f1 = False
                ans_even.append((k, v))
            if(v == n2 and f2 is True):
                f2 = False
                ans_even.append((k, v))

if(len(odd) == 1):
    t = max(Vdic[1], key=Vdic[1].get)
    ans_odd.append((t, odd[0]))
else:
    n1 = odd[-1]
    n2 = odd[-2]

    f1 = True
    f2 = True
    if(n1 == n2):
        for k, v in Vdic[1].items():
            if(v == n1):
                if(f1 is False and f2 is False):
                    continue
                if(f1 is False):
                    f2 = False
                f1 = False
                ans_odd.append((k, v))
    else:
        for k, v in Vdic[1].items():
            if(v == n1 and f1 is True):
                f1 = False
                ans_odd.append((k, v))
            if(v == n2 and f2 is True):
                f2 = False
                ans_odd.append((k, v))


# print(ans_even, ans_odd)

ans = []
for ke, ve in ans_even:
    for ko, vo in ans_odd:
        if(ke != ko):
            ans.append(n - ve - vo)

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

import heapq
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
q = []
for i, b in enumerate(B):
    q.append([-b, i])
heapq.heapify(q)
ans = 0
while q:
    b, idx = heapq.heappop(q)
    b = -b
    if b==A[idx]:
        continue
    nb = max(B[(idx+1)%N], B[idx-1], B[idx])
    d = B[(idx+1)%N] + B[idx-1]
    p = (b - nb) // d + 1
    b -= p * d
    B[idx] = b
    heapq.heappush(q, [-b, idx])
    ans += p
    if b < A[idx]:
        B[idx] += d
        for a, b in zip(A, B):
            if a!=b:
                print(-1)
                exit()
        else:
            print(ans-1)
            exit()
print(ans)


### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline

# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩
# 💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩💩

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
q = []
q = [(-b, i) for i, b in enumerate(B)]
heapq.heapify(q)
ans = 0
N_m1 = N-1
while len(q)>0:
    b, idx = q[0]
    b = -b
    b_p1, b_m1 = B[idx+1 if idx<N_m1 else 0], B[idx-1]
    d = b_p1 + b_m1

    a = A[idx]
    p = min((b-a)//d, (b-b_m1)//d+1, (b-b_p1)//d+1)

    b -= p * d
    B[idx] = b
    ans += p
    if b > a:
        heapq.heapreplace(q, (-b, idx))
        if q[0][1] == idx:
            print(-1)
            exit()
    else:
        heapq.heappop(q)
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush, heapify
import math
import itertools
import random
 
# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
INF = float('inf')
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N,M = inputMap()
    ab = []
    for i in range(N):
        a,b = inputMap()
        if a > M:
            continue
        ab.append((a,b))
        
    ab = sorted(ab, key=lambda x:(x[0],-x[1]))
    pq = []
    heapify(pq)
    
    ans = 0
    for i in range(1,M+1):
        ind = -1
        for j,val in enumerate(ab):
            a,b = val
            ind = -1
            if a > i:
                break
            if i == a:
                heappush(pq, -b)
                ind = j
                
        if len(pq) > 0:
            tmp = heappop(pq) * (-1)
            ans += tmp
            
        if ind != -1:
            ab = ab[ind+1:]
    
    print(ans)
    
if __name__ == "__main__":
	main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush, heapify
import math
import itertools
import random
 
# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
INF = float('inf')
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N,M = inputMap()
    ab = []
    heapify(ab)
    for i in range(N):
        a,b = inputMap()
        if a > M:
            continue
        heappush(ab, (a,b))
    
    ans = 0
    pq = []
    heapify(pq)
    for i in range(1,M+1):
        while True:
            if len(ab) == 0 or ab[0][0] != i:
                break
            a,b = heappop(ab)
            heappush(pq, -b)
            
        if len(pq) > 0:
            ans = ans + (heappop(pq) * (-1))
        
    
    print(ans)
    
if __name__ == "__main__":
	main()
### BUGGY CODE ###

n, k = map(int, input().split())
A = list(map(int, input().split()))
score = []
cnt = 0

for i in range(n - k + 1):
    wknum = 1
    point = (k + i -1)
    for j in range(k):
        wknum *= A[point - j]
    score.append(wknum)
    if cnt == 0:
        cnt += 1
        continue
    else:
        if score[i] <= score[i -1]:
            print('No')
        else:
            print('Yes')


### FIXED CODE ###

import numpy as np

n, k = map(int, input().split())
A = np.array(input().split(), dtype = np.int64)
score = np.array([0 for i in range(n- k + 1)], dtype = np.int64)
wknum = 1
for i  in range(k):
    wknum *= A[i]

for i in range(n - k):
    wknum //= A[i]
    wknum *= A[k + i]
    if A[i] >= A[k + i]:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

import itertools
N,K = map(int,input().split())
A = list(map(int,input().split()))
for i in range(K):
    newA = [0]*N
    for j in range(N):
        newA[max(0,j-A[j])] += 1
        if j+A[j]+1 < N:
            newA[min(N-1,j+A[j]+1)] -= 1
    A = list(itertools.accumulate(newA))
    if A == [N]*N:
        break
for i in range(N):
    A[i] = str(A[i])
print(' '.join(A))

### FIXED CODE ###

import itertools
N,K = map(int,input().split())
A = list(map(int,input().split()))
if K >= 50:
    print(*[N]*N)
    exit()
for i in range(K):
    newA = [0]*N
    for j in range(N):
        newA[max(0,j-A[j])] += 1
        if j+A[j]+1 < N:
            newA[min(N-1,j+A[j]+1)] -= 1
    A = list(itertools.accumulate(newA))
    if A == [N]*N:
        break
print(*A)
### BUGGY CODE ###

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

ans=0
RGB=[]
for i in range(N-2):
  for j in range(i+1,N-1):
    if S[i]!=S[j]:
      if not 'R' in [S[i],S[j]]:
        ans+=S[j+1:].count('R')
        if 2*j-i<N and S[2*j-i]=='R':
          ans-=1
      elif not 'G' in [S[i],S[j]]:
        ans+=S[j+1:].count('G')
        if 2*j-i<N and S[2*j-i]=='G':
          ans-=1
      else:
        ans+=S[j+1:].count('B')
        if 2*j-i<N and S[2*j-i]=='B':
          ans-=1
print(ans)

### 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-2):
  for j in range(i+1,N-1):
    if 2*j-i>=N:
      break
    elif S[i]!=S[j] and S[j]!=S[2*j-i] and S[2*j-i]!=S[i]:
      ans-=1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

H,W = map(int , input().split())
sh,sw = map(int , input().split())
eh,ew = map(int , input().split())
mv_a_pts = [[-1,0],[1,0],[0,-1],[0,1]]
mv_b_pts = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),
        (-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2),
        (0, -2), (0, -1), (0, 1), (0, 2),
        (1, -2), (1, -1), (1, 0), (1, 1), (1, 2),
        (2, -2), (2, -1), (2, 0), (2, 1), (2, 2),]
maze = [input() for _ in range(H)]
warp_cnts = [[None]*(W) for j in range(H)]

def mv_a(h,w):
  mv_b_tgs.append([h,w])
  warp_cnts[h][w] = cnt
  for vh,vw in mv_a_pts:
    tgh = h + vh
    tgw = w + vw
    if 0 <= tgh <= H-1 and 0 <= tgw <= W-1 :
      if warp_cnts[tgh][tgw] is None and maze[tgh][tgw] != "#":
        mv_a(tgh,tgw)

def mv_b(h,w):
  for vh,vw in mv_b_pts:
    tgh = h + vh
    tgw = w + vw
    if 0 <= tgh <= H-1 and 0 <= tgw <= W-1 :
      if warp_cnts[tgh][tgw] is None and maze[tgh][tgw] != "#":
        mv_a_tgs.append([tgh,tgw])
        

mv_b_tgs=[]
mv_a_tgs = [[sh-1,sw-1]]
cnt = 0
while len(mv_a_tgs)>0:
  while len(mv_a_tgs):
    tg0,tg1 = mv_a_tgs.pop()
    mv_a(tg0,tg1)
  while len(mv_b_tgs):
    wp0,wp1 = mv_b_tgs.pop()
    mv_b(wp0,wp1)
  cnt+=1
print(-1 if warp_cnts[eh-1][ew-1] is None else warp_cnts[eh-1][ew-1])

### FIXED CODE ###

from collections import deque
 
 
walk = [(1, 0), (-1, 0), (0, 1), (0, -1)]
warp = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),
        (-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2),
        (0, -2), (0, -1), (0, 1), (0, 2),
        (1, -2), (1, -1), (1, 0), (1, 1), (1, 2),
        (2, -2), (2, -1), (2, 0), (2, 1), (2, 2),]
 
 
def get_warped(walked, map_):
    warped = deque()
    while walked:
        h, w = walked.popleft()
        for i, j in warp:
            h2 = h + i
            w2 = w + j
            if -1 < h2 < H and -1 < w2 < W and map_[h2][w2] == '.':
                warped.append((h2, w2))
                map_[h2][w2] = map_[h][w] + 1
    return warped, map_
 
 
def get_walked(candidate, map_):
    walked = deque()
    while candidate:
        h, w = candidate.popleft()
        walked.append((h, w))
        for i, j in walk:
            h2 = h + i
            w2 = w + j
            if -1 < h2 < H and -1 < w2 < W and map_[h2][w2] == '.':
                candidate.append((h2, w2))
                map_[h2][w2] = map_[h][w]
    return walked, map_
 
H, W = map(int, input().split())
s_h, s_w = [i-1 for i in map(int, input().split())]
d_h, d_w = [i-1 for i in map(int, input().split())]
map_ = [list(input()) for i in range(H)]
 
candidate = deque([(s_h, s_w)])
map_[s_h][s_w] = 0
 
while candidate:
    walked, map_ = get_walked(candidate, map_)
    candidate, map_ = get_warped(walked, map_)
 
for h in range(H):
    for w in range(W):
        if map_[h][w] == '.':
            map_[h][w] = -1
 
print(map_[d_h][d_w])
### BUGGY CODE ###

from collections import deque
import sys

sys.setrecursionlimit(10 ** 9)

H, W = map(int, sys.stdin.readline().split())
field = [list(sys.stdin.readline().rstrip()) for i in range(H)]

dist_from_nearest_black = [[10 ** 9] * W for i in range(H)]
seen = [[0] * W for i in range(H)]
direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]


def bfs(h, w):
    if field[h][w] != "#":
        return

    queue = deque([])
    queue.append([h, w])
    dist_from_nearest_black[h][w] = 0

    while len(queue) != 0:

        h, w = queue.popleft()

        if seen[h][w] == 1:
            continue

        seen[h][w] = 1

        for dh, dw in direction:
            next_h = h + dh
            next_w = w + dw

            if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                continue
            else:
                dist_from_nearest_black[next_h][next_w] = min(
                    dist_from_nearest_black[h][w] + 1, dist_from_nearest_black[next_h][next_w])
                queue.append([next_h, next_w])


for h in range(H):
    for w in range(W):
        seen = [[0] * W for i in range(H)]
        bfs(h, w)

ans = 0

for d in dist_from_nearest_black:
    # print(d)
    ans = max(ans, max(d))

print(ans)


### FIXED CODE ###

from collections import deque
import sys
# from time import time

# start = time()

H, W = map(int, sys.stdin.readline().split())
field = [list(sys.stdin.readline().rstrip()) for i in range(H)]

# print(time() - start)

queue = deque([])

for h in range(H):
    for w in range(W):
        if field[h][w] == "#":
            queue.append([h, w])

dist_from_nearest_black = [[0] * W for i in range(H)]
direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]


def bfs():
    while len(queue) != 0:

        h, w = queue.popleft()

        for dh, dw in direction:
            next_h = h + dh
            next_w = w + dw

            if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                continue
            elif field[next_h][next_w] == "#":
                continue
            else:
                dist_from_nearest_black[next_h][next_w] = dist_from_nearest_black[h][w] + 1
                field[next_h][next_w] = "#"
                queue.append([next_h, next_w])


bfs()

ans = 0

for d in dist_from_nearest_black:
    ans = max(ans, max(d))

print(ans)
# print(time() - start)
### BUGGY CODE ###

n=int(input())
a=[int(input()) for i in range(n)] 

k=a.index(max(a))

for i in range(n):
    if i==k:
        print(sorted(a)[-2])
    else:
        print(max(a))

### FIXED CODE ###

n=int(input())
a=[int(input()) for i in range(n)] 
m=a[0]
k=0

for i in range(n):
    if m<a[i]:
        m=a[i]
        k=i

for j in range(n):
    if j==k:
        print(sorted(a)[-2])
    else:
        print(m)
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
n = 0
for i in range(1,N+1):
    for j in range(N+1-i):
        b = a[j:j+i]
        S = 0
        for x in b:
            S += x
        if S == 0:
            n += 1
print(n)

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
s = [0]*(len(a)+1)
for i in range(len(a)):
    s[i+1] = s[i] + a[i]
b = {}
for x in s:
    if str(x) not in b:
        b[str(x)] = 1
    else:
        b[str(x)] += 1
n = 0
for x in b:
    n += b[x]*(b[x]-1)/2
print(int(n))