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

import sys
input = sys.stdin.readline
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

s = []
for i in range(h):
   s.append(input().rstrip('\n'))

INF = 10 ** 10
d = [INF] * (h*w)

stack = deque([(ch-1, cw-1, 0)])
stack_append = stack.append
stack_popleft = stack.popleft

nex = []
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i, j) in [(-1,0),(1,0),(0,-1),(0,1),(0,0)]:
            continue
        else:
            nex.append((i,j))

while stack:
    curh, curw, cnt = stack_popleft()
    if d[curh * w + curw] <= cnt:
        continue
    else:
        d[curh * w + curw] = cnt
    for dh, dw in ((-1,0), (1,0), (0,1), (0,-1)):
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and d[nh * w + nw] > cnt:
            stack_append((nh, nw, cnt))
    for dh, dw in nex:
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and  d[nh * w + nw] > cnt:
            stack_append((nh, nw, cnt+1))

# for item in d:
#     print(item)
gh -= 1
gw -= 1

if d[gh*w + gw] == INF:
    print(-1)
else:
    print(d[gh*w + gw])


### FIXED CODE ###

import sys
input = sys.stdin.readline

import heapq

INF = 10 ** 10

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    h = []
    heapq.heappush(h, (0, s))

    while h:
        # 使っていない頂点のうち、現時点で最も距離の近いものを選びvとする
        d, v = heapq.heappop(h)
        if dist[v] < d:
            continue
        # vから到達可能な頂点について、距離が短くなれば更新
        for end, cost in G[v]:
            if dist[end] > dist[v] + cost:
                dist[end] = dist[v] + cost
                heapq.heappush(h, (dist[end], end))
    return dist


H, W = map(int, input().split())
N = H * W
ch, cw = map(lambda x:int(x)-1, input().split())
gh, gw = map(lambda x:int(x)-1, input().split())

s = []
es = tuple([] for i in range(N))

for h in range(H):
   s.append(input().rstrip('\n'))

for h in range(H):
    for w in range(W):
        if s[h][w] != '.':
            continue
        a = h*W+w
        esappend = es[a].append
        for dh in (-2, -1, 0, 1, 2):
            for dw in (-2, -1, 0, 1, 2):
                if dh == 0 and dw == 0:
                    continue
                nh = h + dh
                nw = w + dw
                if 0 <= nh and nh < H and 0 <= nw and nw < W and s[nh][nw] == '.':
                    b = nh*W+nw
                    if (dh, dw) in [(-1,0),(1,0),(0,-1),(0,1)]:
                        esappend((b, 0))
                    else:
                        esappend((b, 1))

dist = dijkstra(N, es, ch*W+cw)
if dist[gh*W+gw] == INF:
    print(-1)
else:
    print(dist[gh*W+gw])
### BUGGY CODE ###

import math
b = list(map(int,input().split()))
ans=0
check=0
i=0
for i in range(100000000):
    if b[2]-i <0:
        break
    check = math.floor((b[0]*(b[2]-i))/b[1]) - b[0]*math.floor((b[2]-i)/b[1])
    if check > ans:
        ans=check
print(ans)

### FIXED CODE ###

import math
b = list(map(int,input().split()))
ans=0
check=0
if b[2]>b[1]-1:
    check = math.floor((b[0]*(b[1]-1))/b[1]) - b[0]*math.floor((b[1]-1)/b[1])
else:
    check = math.floor((b[0]*b[2])/b[1]) - b[0]*math.floor(b[2]/b[1])
if check>ans:
    ans=check
print(ans)
### BUGGY CODE ###

from sys import stdin
input = stdin.readline

R, G, B, N = map(int, input().split())

ans = 0

for i in range(N + 1):
    for j in range(N + 1):
        k = (N - i * R - j * G) / B
        if k.is_integer() and k >= 0:
            # print(i, j, k)
            ans += 1

print(ans)


### FIXED CODE ###

from sys import stdin
input = stdin.readline

R, G, B, N = map(int, input().split())

ans = 0

for i in range(N + 1):
    for j in range(N + 1):
        k = (N - i * R - j * G) / B
        if k.is_integer() and k >= 0:
            # print(i, j, k)
            ans += 1

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

n, k = map(int, input().split())
A = [*map(int, input().split())]
for i in range(k):
    B = [0]*(n+1)
    for j in range(n):
        l = max(0, j - A[j])
        r = min(n, j + A[j] + 1)
        B[l] += 1; B[r] -= 1
    for j in range(n-1): B[j+1] += B[j]
    B.pop()
    if A == B: break
    A = B
print(*A, sep=' ')


### FIXED CODE ###

n,k = map(int,input().split())
A=[*map(int,input().split())]
for i in range(k):
    B = [0]*n
    for j in range(n):
        d = A[j] # 強さ
        l = max(0, j-d) # 範囲
        r = j+d+1 # 範囲
        B[l] += 1
        if r <= n-1: B[r] -= 1
    is_same = True
    for j in range(n-1):
        B[j+1] = B[j+1] + B[j]
        if B[j+1] != n: is_same = False
    # print(B)
    if is_same: break
    A = B
# print(B)
print(*B,sep=' ')
### BUGGY CODE ###

import sys
n, a, b, c, d = map(int, sys.stdin.readline().split())
s = sys.stdin.readline().rstrip()

dp = [[False for _ in range(n)] for _ in range(n)]
dp[a-1][b-1] = True

for i in range(a-1, n):
    for j in range(b-1, n):
        if i == j: continue
        if not dp[i][j]: continue
        for x, y in ((1, 0), (2, 0), (0, 1), (0, 2)):
            if (i+x < n) and (j+y < n) and s[i+x] == '.' and s[j+y] == '.':
                dp[i+x][j+y] = True

print('Yes' if dp[c-1][d-1] else 'No')


### FIXED CODE ###

import sys
n, a, b, c, d = map(int, sys.stdin.readline().split())
s = sys.stdin.readline().rstrip()

def can_reach(start, end):
    for i in range(start-1, end-1):
        if s[i] == '#' and s[i+1] == '#':
            return False
    return True

if can_reach(a, c) and can_reach(b, d):
    if c < d:
        print('Yes')
    else:
        flag = False
        for i in range(b-1, d):
            if s[i-1] == '.' and s[i] == '.' and s[i+1] == '.':
                flag = True
        print('Yes' if flag else 'No')
else:
    print('No')
### BUGGY CODE ###

H,W,M=map(int,input().split())
nh=[0]*H
nw=[0]*W
boms=[]
for _ in range(H):
    boms.append([False]*W)
for _ in range(M):
    h,w=map(int,input().split())
    nh[h-1] += 1
    nw[w-1] += 1
    boms[h-1][w-1]=True

maxh = max(nh)
maxw = max(nw)

i_indexes=[]
for i in range(H):
    if nh[i] == maxh:
        i_indexes.append(i)
j_indexes=[]
for j in range(W):
    if nw[j] == maxw:
        j_indexes.append(j)

for i in i_indexes:
    for j in j_indexes:
        if not boms[i][j]:
            print(maxh + maxw)
            exit()
print(maxh + maxw - 1)


### FIXED CODE ###

import sys
input = sys.stdin.readline

H,W,M=map(int,input().split())
nh=[0]*H
nw=[0]*W
boms=set()
for _ in range(M):
    h,w=map(int,input().split())
    nh[h-1] += 1
    nw[w-1] += 1
    boms.add((h-1, w-1))

maxh = max(nh)
maxw = max(nw)

i_indexes=[]
for i in range(H):
    if nh[i] == maxh:
        i_indexes.append(i)
j_indexes=[]
for j in range(W):
    if nw[j] == maxw:
        j_indexes.append(j)

for i in i_indexes:
    for j in j_indexes:
        if (i,j) in boms:
            continue
        print(maxh + maxw)
        exit()
print(maxh + maxw - 1)
### BUGGY CODE ###

from collections import Counter

n, p = map(int, input().split())
s = input().rstrip()

total = 0
if p in [2, 5]:
    for i in range(n-1, -1, -1):
        if int(s[i]) % p == 0:
            total += i + 1
else:
    dp = [0] * (n + 1)
    fac = 1
    for i in range(n-1, -1, -1):
        dp[i] = (dp[i + 1] + int(s[i]) * fac) % p
        fac *= 10 % p

    c = Counter(dp)

    for k, v in c.items():
        if v >= 2:
            total += v * (v - 1) // 2

print(total)


### FIXED CODE ###

from collections import Counter

n, p = map(int, input().split())
s = input().rstrip()

total = 0
if p in [2, 5]:
    for i in range(n-1, -1, -1):
        if int(s[i]) % p == 0:
            total += i + 1
else:
    dp = [0] * (n + 1)
    fac = 1
    for i in range(n-1, -1, -1):
        dp[i] = (dp[i + 1] + int(s[i]) * fac) % p
        fac = (fac * 10) % p

    c = Counter(dp)

    for k, v in c.items():
        if v >= 2:
            total += v * (v - 1) // 2

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

import sys
import heapq
import numpy as np
from collections import defaultdict
n, m = map(int, sys.stdin.readline().split())
a_b = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
dic = defaultdict(list)
for ele in a_b:
    dic[ele[0]].append(ele[1])

#print(dic)
L =[]
money = 0
for d in range(1, m+1):
    L+=list(np.array(dic[d])*(-1))
    heapq.heapify(L)
    if L:
        money +=heapq.heappop(L)
print(-money)

### FIXED CODE ###

import sys
from collections import defaultdict
import heapq
input = sys.stdin.readline
n, limit = map(int, input().split())
dic = defaultdict(list)

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

L = []
ans = 0
for i in range(limit+1):
    for val in dic[i]:
        heapq.heappush(L, -val)
    if len(L):
        ans -= heapq.heappop(L)
print(ans)
### BUGGY CODE ###

import copy
n,m,k = map(int,input().split())
ab = [[] for _ in range(n)]
for _ in range(m):
    a, b= (int(x) for x in input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
bl = [[] for _ in range(n)]
for _ in range(k):
    a, b= (int(x) for x in input().split())
    bl[a-1].append(b-1)
    bl[b-1].append(a-1)
ans = []
#print(ab)
#print(bl)
check = [0]*n
for i in range(n):
    check = [0]*n
    first = copy.copy(ab[i])
    #print(ab)
    #print(first)
    move = []
    check[i] = 1
    while len(first)>0:
        p = first.pop(0)
        check[p] = 1
        for q in ab[p]:
            #print(q)
            move.append(q)
    #print(move)
    count = 0
    while len(move):
        j = move.pop(0)
        if check[j] == 0 :
            check[j] = 1
            if j not in bl[i]:
                count += 1
            for k in ab[j]:
                move.append(k)
    ans.append(count)
#print(ans)
print(' '.join(map(str,ans)))

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())
friends_table = [[] for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    friends_table[a-1] += [b-1]
    friends_table[b-1] += [a-1]

group_list = [i for i in range(N)]
friends_candidate = [[] for i in range(N)]

for i in range(N):
    # すでにDFS済み
    if i != group_list[i]:
        continue
    next_stack = [i]
    friend = [i]
    while next_stack:
        u = next_stack.pop(-1)
        for v in friends_table[u]:
            # 訪問済み
            if i == group_list[v]:
                continue
            friend += [v]
            group_list[v] = i
            next_stack += [v]
    for f in friend:
        friends_candidate[f] = friend

blocks_table = [[] for i in range(N)]
for _ in range(K):
    a, b = map(int, input().split())
    if group_list[a-1] == group_list[b-1]:
        blocks_table[a-1] += [b-1]
        blocks_table[b-1] += [a-1]

for i in range(N):
    print(len(friends_candidate[i]) - len(friends_table[i]) - len(blocks_table[i])-1)
### BUGGY CODE ###

N = int(input())
cnt = 0

sList = []

for n in range(0, N):
    string = list(input())
    sList.append(string)
    sList[n].sort()

for i in range(0, N - 1):
    for j in range(i + 1, N):
        if sList[i] == sList[j]:
            cnt += 1
print(cnt)


### FIXED CODE ###

import sys
import collections
import bisect


def main():
    n = int(input())
    s = [''.join(sorted(list(input()))) for _ in range(n)]
    c = collections.Counter(s)
    cVals = c.values()
    cSum = 0
    for cVal in cVals:
        cSum += cVal * (cVal - 1) // 2
    print(cSum)


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

n = int(input())
a = input().split()
ans = 'YES'

for i in range(n):
    if ans == 'NO':
        break;
    for j in range(i + 1, n):
        if a[i] == a[j]:
            ans = "NO"
            break;

print(ans)

### FIXED CODE ###

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

a = set(a)
if n == len(a):
    print('YES')
else:
    print("NO")
### BUGGY CODE ###

R=list()
s=0
L=list()
N=int(input())
for i in range(N):
  S=sorted(list(input()))
  if S not in R:
    R.append(S)
  L.append(S)
for i in range(len(R)):
  c=L.count(R[i])
  s+=(c*(c-1))//2
print(s)

### FIXED CODE ###

import collections
N=int(input())
j=0
L=list()
R=list()
for i in range(N):
  S="".join(sorted(list(input())))
  L.append(S)
c = collections.Counter(L)
counts=c.values()
counts=list(counts)
A=[i*(i-1)//2 for i in counts]
print(sum(A))
### BUGGY CODE ###

from collections import deque
xs,ys,xt,yt=map(int,input().split())
P=[]
inf=float("inf")
P.append((xs,ys,0))
N=int(input())
for i in range(N):
  x,y,r=map(int,input().split())
  P.append((x,y,r))
P.append((xt,yt,0))
G=[set() for i in range(N+2)]
for i in range(N+2):
  for j in range(N+2):
    if i!=j:
      x1,y1,r1,x2,y2,r2=P[i][0],P[i][1],P[i][2],P[j][0],P[j][1],P[j][2]
      d=((x1-x2)**2+(y1-y2)**2)**(1/2)
      if d<=r1+r2:
        G[i].add((0,j))
      else:
        G[i].add((d-r1-r2,j))

def dijkstra(s,n,links):
  cost=[inf]*n
  cost[s]=0
  stack=deque([(0,s)])
  while stack:
    hc,hp=stack.popleft()
    for c,p in links[hp]:
      if c+hc<cost[p]:
        cost[p]=c+hc
        stack.append((cost[p],p))
  return cost        

c=dijkstra(0,N+2,G)
print(c[-1])

### FIXED CODE ###

from collections import defaultdict
xs,ys,xt,yt=map(int,input().split())
P=[]
inf=float("inf")
P.append((xs,ys,0))
P.append((xt,yt,0))
N=int(input())
for i in range(N):
  x,y,r=map(int,input().split())
  P.append((x,y,r))

G=defaultdict(int)
for i in range(N+2):
  for j in range(N+2):
      x1,y1,r1,x2,y2,r2=P[i][0],P[i][1],P[i][2],P[j][0],P[j][1],P[j][2]
      d=((x1-x2)**2+(y1-y2)**2)**(1/2)
      G[(i,j)]=max(0,d-r1-r2)

def dijkstra():
  d=[inf]*(N+2)
  d[0]=0
  used=[False]*(N+2)
  
  while True:
    v=-1
    for i in range(N+2):
      if used[i]==False and (v==-1 or d[i]<d[v]):
        v=i
    if v==-1:
      break
    used[v]=True
    for j in range(N+2):
      d[j]=min(d[j],d[v]+G[(v,j)])    
  return d[1]
print(dijkstra())
### BUGGY CODE ###

import bisect

N=int(input())
A=[int(input()) for i in range(N)]

B=[]
for a in A:
  p=bisect.bisect_left(B,a)
  if p==0:
    B.insert(0,a)
  else:
    B[p-1]=a

print(len(B))


### FIXED CODE ###

import bisect

N=int(input())
A=[-int(input()) for i in range(N)]

B=[]
c=0
for a in A:
  p=bisect.bisect_right(B,a)
  if p==c:
    B.append(a)
    c += 1
  else:
    B[p]=a

print(len(B))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(1,1+n):
  c=a.count(i)
  ans+=(c*(c-1))//2
for k in range(n):
  c=a.count(a[k])
  print(ans-c+1)

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
l = [0]*N
ans = 0
for a in A:
    l[a-1] += 1
for j in l:
    ans += int(j*(j-1)/2)
for k in range(N):
    print(ans - l[A[k]-1] + 1)
### BUGGY CODE ###

R,G,B,N=[int(i) for i in input().split()]
num = 0
for i in range(N//R+1):
  for j in range(N//G+1):
#    print(i*R,j*G)
    if i*R+j*G<=N:
      if (N-i*R-j*G)%B==0:
#        print((N-i*R-j*G))
        num+=1
print(num)

### FIXED CODE ###

R,G,B,N=[int(i) for i in input().split()]
num = 0
for i in range(N//R+1):
  for j in range(N//G+1):
#    print(i*R,j*G)
    if i*R+j*G<=N:
      if (N-i*R-j*G)%B==0:
#        print((N-i*R-j*G))
        num+=1
print(num)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
S = input()
Q = int(input())
qs = list(input() for _ in range(Q))
rev = 0
for q in qs:
    q = q.split()
    if q[0] == '1':
        rev = (rev+1) % 2
    else:
        if (q[1]=='1' and rev==0) or (q[1]=='2' and rev==1):
            S = q[2] + S
        else:
            S = S + q[2]
print(S if rev == 0 else S[::-1])

### FIXED CODE ###

import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()
S = deque(input())
rev = False
apdlft = S.appendleft
apd = S.append

for _ in range(int(input())):
    q = input().split()
    if q[0] == '1':
        rev = not(rev)
    else:
        if (q[1]=='1' and rev is False) or (q[1]=='2' and rev is True):
            apdlft(q[2])
        else:
            apd(q[2])

if rev:
    print((''.join(S))[::-1])
else:
    print(''.join(S))
### BUGGY CODE ###

import collections
def main():
    s = input()
    K = int(input())
    d = collections.defaultdict(set)
    n = len(s)
    for i in range(n):
        for l in range(1, n-i+1):
            d[s[i]].add(s[i:i+l])
    for c in sorted(d.keys()):
        if len(d[c]) < K:
            K -= len(d[c])
        else:
            d[c] = sorted(d[c])
            return d[c][K-1]

if __name__ == '__main__':
    print(main())


### FIXED CODE ###

import collections
def main():
    s = input()
    K = int(input())
    d = collections.defaultdict(int)
    idx = collections.defaultdict(list)
    n = len(s)
    for i in range(n):
        idx[s[i]].append(i)

    cand = set()
    for c in sorted(idx.keys())[:K]:
        cand.add(c)
        for i in idx[c]:
            for l in range(1, K+1):
                cand.add(s[i:i+l])

    cand = sorted(list(cand))
    return cand[K-1]

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

import sys
input = sys.stdin.readline
r,c,k = map(int,input().split())
d = {}
for i in range(k):
    x,y,v = map(int,input().split())
    d[(x-1,y-1)] = v

dp = [[[0]*4 for i in range(c+1)] for j in range(r+1)]

for i in range(r):
    for j in range(c):
        M = max(dp[i][j+1])
        if (i,j) in d:
            v = d[(i,j)]
            dp[i+1][j+1][0] = max(M,dp[i+1][j][0])
            dp[i+1][j+1][1] = max(M+v,dp[i+1][j][0]+v,dp[i+1][j][1])
            dp[i+1][j+1][2] = max(dp[i+1][j][1]+v,dp[i+1][j][2])
            dp[i+1][j+1][3] = max(dp[i+1][j][2]+v,dp[i+1][j][3])
        else:
            dp[i+1][j+1][0] = max(M,dp[i+1][j][0])
            dp[i+1][j+1][1] = dp[i+1][j][1]
            dp[i+1][j+1][2] = dp[i+1][j][2]
            dp[i+1][j+1][3] = dp[i+1][j][3]
print(max(dp[-1][-1]))

### FIXED CODE ###

import sys
input = sys.stdin.readline
r,c,k = map(int,input().split())
l = [[0]*c for i in range(r)] 
for i in range(k):
    x,y,v = map(int,input().split())
    l[x-1][y-1] = v
dp = [[0]*4 for i in range(c+1)]

for i in range(r):
    ndp = [[0]*4 for i in range(c+1)]
    for j in range(c):
        M = max(dp[j+1])
        if l[i][j]>0:
            v = l[i][j]
            ndp[j+1][0] = max(M,dp[j][0],ndp[j][0])
            ndp[j+1][1] = max(M+v,dp[j][0]+v,ndp[j][0]+v,dp[j][1],ndp[j][1])
            ndp[j+1][2] = max(dp[j][1]+v,ndp[j][1]+v,dp[j][2],ndp[j][2])
            ndp[j+1][3] = max(dp[j][2]+v,ndp[j][2]+v,dp[j][3],ndp[j][3])
        else:
            ndp[j+1][0] = max(M,dp[j][0],ndp[j][0])
            ndp[j+1][1] = max(dp[j][1],ndp[j][1])
            ndp[j+1][2] = max(dp[j][2],ndp[j][2])
            ndp[j+1][3] = max(dp[j][3],ndp[j][3])
    dp = ndp
print(max(dp[-1]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
mod=10**9+7

N=int(input())
XY=[list(map(int,input().split())) for i in range(N-1)]

EDGELIST=[[] for i in range(N+1)]

for x,y in XY:
    EDGELIST[x].append(y)
    EDGELIST[y].append(x)

check=[0]*(N+1)


QUE=[1]

EDGE1=[[] for i in range(N+1)]

while QUE:
    x=QUE.pop()
    if check[x]==1:
        continue

    for to in EDGELIST[x]:
        if check[to]==1:
            continue
        else:         
            QUE.append(to)
            EDGE1[x].append(to)

    check[x]=1
        

def ANS(n):
    if EDGE1[n]==[]:
        return 1,1
    else:
        b=1
        w=1
        for to in EDGE1[n]:
            x,y=ANS(to)
            b=b*y%mod
            w=w*(x+y)%mod

        return b,w

print(sum(ANS(1))%mod)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
mod=10**9+7

N=int(input())
XY=[list(map(int,input().split())) for i in range(N-1)]

EDGELIST=[[] for i in range(N+1)]

for x,y in XY:
    EDGELIST[x].append(y)
    EDGELIST[y].append(x)

check=[0]*(N+1)

from collections import deque
QUE=deque([1])

EDGE1=[[] for i in range(N+1)]

while QUE:
    x=QUE.pop()
    if check[x]==1:
        continue

    for to in EDGELIST[x]:
        if check[to]==1:
            continue
        else:         
            QUE.append(to)
            EDGE1[x].append(to)

    check[x]=1
        

def ANS(n):
    if EDGE1[n]==[]:
        return 1,1
    else:
        b=1
        w=1
        for to in EDGE1[n]:
            x,y=ANS(to)
            b=b*y%mod
            w=w*(x+y)%mod

        return b,w

print(sum(ANS(1))%mod)
### BUGGY CODE ###

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

ListL = [i+1+List[i] for i in range(N)]
ListR = [i+1-List[i] for i in range(N)]

ans = 0
for i in range(2*10**5):
  ans += ListL.count(i)*ListR.count(i)

print(ans)  

### FIXED CODE ###

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

ListK = [i+1+List[i] for i in range(N)]
ListL = [i+1-List[i] for i in range(N)]

from collections import Counter 
ans = 0

NewlistK = Counter(ListK)
NewlistL = Counter(ListL)

for i in range(N):
  ans += (NewlistK[i])*(NewlistL[i])

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

N,M=map(int,input().split())
for g in range(M//N,0,-1):
    if M%g==0:
        print(g)
        break

### FIXED CODE ###

N,M=map(int,input().split())

for g in range(M//N,0,-1):
    if (M-(N-1)*g)%g==0:
        break

print(g)
### BUGGY CODE ###

import numpy as np
N, M = map(int, input().split())
X = np.ones((N))
for i in range(M):
    Y = np.zeros((N))
    L, R = map(int, input().split())
    Y[L-1:R]=1
    X=X*Y
print(np.sum(X, dtype=np.int64))

### FIXED CODE ###

import numpy as np
N, M = map(int, input().split())
LL, RR = map(int, input().split())
for i in range(M-1):
    L, R = map(int, input().split())
    LL = max(L, LL)
    RR = min(R, RR)
print(max(RR-LL+1,0))
### BUGGY CODE ###

#-*- coding:utf-8 -*-

import bisect

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
BC = [0]*M
for i in range(M):
    BC[i] = [int(n) for n in  input().split()]

A.sort()    # 昇順ソートO(NlogN)
BC.sort(key=(lambda x: x[1]), reverse=True)   # Ciの値で降順ソート

for i in range(M):
    b, c = BC[i]
    # cが降順なので、入替回数が減る？
    idx = bisect.bisect_left(A, c)
    if idx > 0:
        for j in range(min(idx,b)):
            A[j] = c
        A.sort()

print(sum(A))

### FIXED CODE ###

#-*- coding:utf-8 -*-

import bisect

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
BC = [0]*M
for i in range(M):
    BC[i] = [int(n) for n in  input().split()]

A.sort()    # 昇順ソートO(NlogN)
BC.sort(key=(lambda x: x[1]), reverse=True)   # Ciの値で降順ソート

st = 0 # 編集開始位置
for i in range(M):  # O(MlogN)
    b, c = BC[i]
    idx = bisect.bisect_left(A, c, st)  # A全体でのidxを返す
    edit = idx - st # 編集個数
    edit = min(b, edit)
    for j in range(edit):
        A[st+j] = c
    st += edit

print(sum(A))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
cur = [0 for i in range(N)]
ball = []
ball_num = 0
for x in range(N):
	i = N-1 - x
	n = i + 1
	if A[i] != cur[i]:
		ball.append(n)
		ball_num += 1
		for j in range(n // 2 + 1):
			m = j + 1
			if m * m > n:
				break
			if n % m == 0:
				cur[j] = 1 - cur[j]
				if n//m != m:
					cur[n//m - 1] = 1 - cur[n//m - 1]  
print(ball_num)
print(" ".join(list(map(str, ball))))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
cur = [0 for i in range(N)]
ball = []
ball_num = 0
for x in range(N):
	i = N-1 - x
	n = i + 1
	if A[i] != cur[i]:
		ball.append(n)
		ball_num += 1
		for j in range(n // 2 + 1):
			m = j + 1
			if m * m > n:
				break
			if n % m == 0:
				cur[j] = 1 - cur[j]
				if n//m != m:
					cur[n//m - 1] = 1 - cur[n//m - 1]  
print(ball_num)
print(" ".join(list(map(str, ball))))
### BUGGY CODE ###

N = int(input())

def f(n):
    cnt = 0
    for x in range(1, int(N ** 0.5) + 1):
        for y in range(1, int(N ** 0.5) + 1):
            for z in range(1, int(N ** 0.5) + 1):
                if x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x == n:
                    cnt += 1

    return cnt

for i in range(1, N+1):
    print(f(i))


### FIXED CODE ###

n = int(input())

ans = [0 for _ in range(n+1)]

for x in range(1, int(n ** 0.5) + 1):
    for y in range(1, int(n ** 0.5) + 1):
        for z in range(1, int(n ** 0.5) + 1):
            a = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
            if a <= n:
                ans[a] += 1

for i in range(1,n+1):
    print(ans[i])