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

# -*- coding: utf-8 -*-
import math

N = int(input())
f = [0] * N
for i in range(1, N+1):
  count = 0
  for x in range(1, int(math.sqrt(i+1))):
    for y in range(x, i):
      z = i-x-y
      if z < y:
        break
      n = x**2 + y**2 + z**2 + x*y + y*z + z*x
      if n <= N:
        if x == y and x == z:
          f[n-1] += 1
        elif x == y or y == z:
          f[n-1] += 3
        elif x != y and x != z and y != z:
          f[n-1] += 6
for i in f:
  print(i)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import math

N = int(input())
f = [0] * N
for i in range(1, N+1):
  count = 0
  for x in range(1, i):
    if x**2 > N:
      break
    for y in range(x, i):
      if y**2 > N:
        break
      z = i-x-y
      if z < y:
        break
      n = x**2 + y**2 + z**2 + x*y + y*z + z*x
      if z > math.sqrt(n + 1):
        break
      if n <= N:
        if x == y and x == z:
          f[n-1] += 1
        elif x == y or y == z:
          f[n-1] += 3
        elif x != y and x != z and y != z:
          f[n-1] += 6
for i in f:
  print(i)
### BUGGY CODE ###

import heapq

x,y,z,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

l = []

for p in range(0,x):
    for q in range(0,y):
        for r in range(0,z):
            if len(l) > k:
                heapq.heappushpop(l,a[p]+b[q]+c[r])
            else:
                heapq.heappush(l,a[p]+b[q]+c[r])

l.sort()

for i in range(1,k+1):
    print(l[-i])

### FIXED CODE ###

import heapq

x,y,z,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

a.sort(reverse = True)
b.sort(reverse = True)
c.sort(reverse = True)

l = []

for p in range(0,x):
    for q in range(0,y):
        for r in range(0,z):
            if len(l) > k and a[p]+b[q]+c[r] <= l[0]:
                break
            elif len(l) > k:
                heapq.heappushpop(l,a[p]+b[q]+c[r])
            else:
                heapq.heappush(l,a[p]+b[q]+c[r])

l.sort()

for i in range(1,k+1):
    print(l[-i])
### BUGGY CODE ###

n = int(input())
a = [int(input()) 
     for nesya in range(n)]
s = set(a)
b = list(sorted(s))
ans = 0
for i in range(len(b)):
  c = a.count(b[i])
  if c%2 == 1:
    ans += 1
  a = [j for j in a if j > b[i]]
print(ans)

### FIXED CODE ###

n = int(input())
a = [int(input()) 
     for nesya in range(n)]
s = set()
for b in a:
  if b in s:
    s.discard(b)
  else:
    s.add(b)
print(len(s))
### BUGGY CODE ###

lim = 1e18
n = int(input());
nums = list(map(int,str(input()).split(" ")))
ans = 1
for num in nums:
    ans *= num
if ans > lim:
    print(-1)
else:
    print(int(ans))



### FIXED CODE ###

def main():
    lim = 1e18
    n = int(input())
    nums = list(map(int,str(input()).split(" ")))
    if 0 in nums:
        print(0)
        return
    ans = 1
    for num in nums:
        ans *= num
        if ans > lim:
            print(-1)
            return
    print(ans)
    return

main()
### BUGGY CODE ###

K,S = map(int,(input().split()))

n = 0

for x in range(K+1) :
        if (S - x <= 2 * K):
                for y in range(K+1) :
                        if (K >= x) and (K >= y) and (S >= x + y) and (S-x-y <= K):
                                n = n + 1

                
print(n)

### FIXED CODE ###

K,S = map(int,(input().split()))

n = 0

for x in range(K+1) :
        if (S - x <= 2 * K):
                for y in range(K+1) :
                        if 0 <=S-x-y <= K:
                                n += 1

                
print(n)
### BUGGY CODE ###

S = input()
p = 10 ** 9 + 7
C = [1 for i in range(S.count('?') + 1)]
for i in range(1, len(C)):
  C[i] = C[i - 1] * i % p
Ci = [c for c in C]
Ci[-1] = pow(C[-1], p - 2, p)
for i in range(1, len(C) - 1):
  Ci[len(C) - i - 1] = Ci[len(C) - i] * (len(C) - i) % p
def comb(*A):
  c = C[sum(A)]
  for a in A:
    c *= Ci[a]
  return c % p
posB = []
posQ = []
for i, s in enumerate(S):
  if s == 'B':
    posB.append(i)
  elif s == '?':
    posQ.append(i)
cnt = 0
for b in sorted(posB + posQ):
  cntA = S[:b].count('A')
  cntAQ = S[:b].count('?')
  cntC = S[b + 1:].count('C')
  cntCQ = S[b + 1:].count('?')
  a = 0
  for ai in range(cntAQ + 1):
    a += (cntA + ai) * comb(ai, cntAQ - ai) * (2 ** (cntAQ - ai)) % p
  c = 0
  for ci in range(cntCQ + 1):
    c += (cntC + ci) * comb(ci, cntCQ - ci) * (2 ** (cntCQ - ci)) % p
  cnt += (a * c) % p
print(cnt % p)

### FIXED CODE ###

S = input()
p = 10 ** 9 + 7
DP = [0, 0, 0, 1]
dp = [0] * 4
for i in range(len(S) - 1, -1, -1):
  for j in range(3, -1, -1):
    if j == 3:
      dp[j] = DP[3] * (3 if S[i] == '?' else 1) % p
    elif S[i] == '?':
      dp[j] = (3 * DP[j] + DP[j + 1]) % p
    elif S[i] == chr(65 + j):
      dp[j] = (DP[j] + DP[j + 1]) % p
    else:
      dp[j] = DP[j]
  DP = [x for x in dp]
print(DP[0] % p)
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
rep = 1
for i in range(K):
    rep *= A[i]

#この段階でrepはK学期の評価
tmp = rep
for i in range(K,N):
    tmp = rep*A[i]//A[i-K]
    if tmp > rep:
        print("Yes")
    else:
        print("No")
    rep = tmp


### FIXED CODE ###

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

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

x = 0
n = int(input())+1

for i in range(1,n):
    for j in range(1, n):
        for k in range(1, n):
            x += int(gcd(i,j,k))
print(x)

### FIXED CODE ###

from math import gcd

x = 0
n = int(input())+1
 
for i in range(1,n):
    for j in range(1, n):
        for k in range(1, n):
            x += gcd(gcd(i,j), k)
 
print(x)
### BUGGY CODE ###

import sys

def main():
    N, K = list(map(int,input().split()))
    h = [0] * N
    for i in range(N):
        h[i] = int(input())

    h = sorted(h)

    abs_p = []
    for j in range(0,N-1):
        abs_p.append(abs(h[j]-h[j+1]))

    abon = []
    for k in range(0,N-K+1):
        abon.append(sum(abs_p[k:k+K-1]))

    print(min(abon))

main()

### FIXED CODE ###

import sys

def main():
    N, K = list(map(int,input().split()))
    h = [0] * N
    for i in range(N):
        h[i] = int(input())

    h = sorted(h)

    ave = []
    for j in range(0,N-K+1):
        ave.append(abs(h[j]-h[j+K-1]))

    print(min(ave))

main()
### BUGGY CODE ###

N = int(input())
MB = {}; MW = {}
for i in range(2*N):
    c, a = input().split()
    a = int(a)
    if c == 'W':
        MW[a] = i
    else:
        MB[a] = i
data = [0]*(2*N+1)
def add(k, x):
    while k <= 2*N:
        data[k] += x
        k += k & -k
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
AW = sorted(MW)
AB = sorted(MB)
cB = [[0]*(N+1) for i in range(N+1)]
cW = [[0]*(N+1) for i in range(N+1)]

IW = [MW[a]+1 for a in AW]
IB = [MB[a]+1 for a in AB]

for i in range(1, 2*N+1):
    data[i] = i & -i

for i, p in enumerate(IW):
    cWi = cW[i]; cBi = cB[i]
    for j, q in enumerate(IB):
        cWi[j] = get(p)-1
        cBi[j] = get(q)-1
        add(q, -1)
    cWi[N] = get(p)-1

    for q in IB:
        add(q, 1)
    add(p, -1)
cBi = cB[N]
for j, q in enumerate(IB):
    cBi[j] = get(q)-1
    add(q, -1)

rN1 = range(1, N+1)
dp = [[10**9]*(N+1) for i in range(N+1)]
dp[0][0] = tmp = 0
T = dp[0]; cBi = cB[0]
for j in rN1:
    tmp = T[j] = tmp + cBi[j-1]

for i in rN1:
    T = dp[i]
    S = dp[i-1]
    cWi = cW[i-1]; cBi = cB[i]
    tmp = T[0] = S[0] + cWi[0]
    for j in rN1:
        tmp = T[j] = min(S[j] + cWi[j], tmp + cBi[j-1])
print(dp[N][N])


### FIXED CODE ###

from bisect import bisect
N = int(input())
B = []
BW = []; BB = []
MB = {}; MW = {}
for i in range(2*N):
    c, a = input().split()
    a = int(a)
    c = "BW".index(c)
    B.append((c, a))
    if c:
        MW[a-1] = i
    else:
        MB[a-1] = i

P = [[0]*(N+1) for i in range(N+1)]
Q = [[0]*(N+1) for i in range(N+1)]

for p in range(N):
    cnt = MW[p] - sum(MW[p0] < MW[p] for p0 in range(p))

    P[p][0] = cnt
    for q in range(N):
        if MB[q] < MW[p]:
            cnt -= 1
        P[p][q+1] = cnt

for q in range(N):
    cnt = MB[q] - sum(MB[q0] < MB[q] for q0 in range(q))

    Q[q][0] = cnt
    for p in range(N):
        if MW[p] < MB[q]:
            cnt -= 1
        Q[q][p+1] = cnt

dist = [[10**9]*(N+1) for i in range(N+1)]
dist[0][0] = 0
que = [(0, 0, 0)]
for i in range(N):
    dist[i+1][0] = dist[i][0] + P[i][0]
for i in range(N):
    dist[0][i+1] = dist[0][i] + Q[i][0]
for i in range(N):
    for j in range(N):
        dist[i+1][j+1] = min(dist[i][j+1] + P[i][j+1], dist[i+1][j] + Q[j][i+1])
print(dist[N][N])
### BUGGY CODE ###

n,k = map(int,input().split())
P = list(map(int,input().split()))

c=0
P.sort( reverse=True )

if k>len(P):
    k=len(P)
for i in range(k):
    if P.count==0 :
        break
    P.remove(P[0])

ans = sum(P)

print(ans)



### FIXED CODE ###

n,k = map(int,input().split())
P = list(map(int,input().split()))

c=0
P.sort( reverse=True )

if k>len(P):
    k=len(P)
for i in range(k):
    c+=1    

ans = sum(P[c:])

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

N = int(input())
X = input()
memo = [-1] * (N+1)
memo[0] = 0

def popcount(k):
    return bin(k).count('1')

def calc(k):
    pop = popcount(k)
    #print('  ', k, pop)
    key = k
    if memo[key] < 0:
        k %= pop
        if k == 0:
            memo[key] = 1
        else:
            memo[key] = calc(k) + 1
    return memo[key]

K = int(X, 2)
one = popcount(K)
if one == 0:
    K_MOD = K
elif one == 1:
    K_MOD   = 0
    K_MOD_M = K
else:
    K_MOD   = K % one
    K_MOD_M = K % (one-1)
K_MOD_P = K % (one+1)

T = 2**(N-1)
for i in range(N):
    if X[i] == '1':
        pop = one - 1
        k = K_MOD_M - T
    else:
        pop = one + 1
        k = K_MOD_P + T
    T //= 2

    if pop == 0:
        print(0)
    else:
        k %= pop
        print(calc(k)+1)


### FIXED CODE ###

N = int(input())
X = input()
memo = [-1] * (N+1)
memo[0] = 0

def popcount(k):
    return bin(k).count('1')

def calc(k):
    pop = popcount(k)
    #print('  ', k, pop)
    key = k
    if memo[key] < 0:
        k %= pop
        if k == 0:
            memo[key] = 1
        else:
            memo[key] = calc(k) + 1
    return memo[key]

K = int(X, 2)
one = popcount(K)
if one == 0:
    K_MOD = K
elif one == 1:
    K_MOD   = 0
    K_MOD_M = K
else:
    K_MOD   = K % one
    K_MOD_M = K % (one-1)
K_MOD_P = K % (one+1)

T_M = [1]*(N+1)
T_P = [1]*(N+1)
for i in range(1,N+1):
    if one > 1:
        T_M[i] = (T_M[i-1]*2) % (one-1)
    T_P[i] = (T_P[i-1]*2) % (one+1)

for i in range(N):
    if X[i] == '1':
        pop = one - 1
        k = K_MOD_M - T_M[N-i-1]
    else:
        pop = one + 1
        k = K_MOD_P + T_P[N-i-1]

    if pop == 0:
        print(0)
    else:
        k %= pop
        print(calc(k)+1)
### BUGGY CODE ###

N = int(input())
lst = [0]*N

for i in range(1,N+1):
    for j in range(1,i+1):
        if i % j == 0:
            lst[i-1] += i

print(sum(lst))

### FIXED CODE ###

# ABC172_D
N = int(input())
ans = 0

for i in range(1,N+1):
	ans += ((N//i)*(i+(N//i)*i))/2

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

k,s = map(int,input().split())
ans = 0
for i in range(k+1):
    for j in range(k+1):
        for k in range(k+1):
            if i + j + k ==s:
                ans += 1
print(ans)

### FIXED CODE ###

k,s = map(int,input().split())
ans = 0
for i in range(k+1):
    for j in range(k+1):
        z = s - i - j
        if 0 <= z <= k:
            ans += 1

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

import sys
input=sys.stdin.readline

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

    inf = 10**4*N
    dp = [inf]*N
    dp[0] = 0
    for i in range(1, N):
        m = max(0, i-K)
        for j in range(i-1, m-1, -1):
            dp[i] = min(dp[i], dp[j] + abs(H[i] - H[j]))
    print(dp[N-1])

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline

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

    inf = 10**4*N
    dp = [inf]*N
    dp[0] = 0
    for i,h in enumerate(H):
        if i == 0:
            continue
        m = max(0, i-K)
        # 普通なら j=i~m のループを回すが、高速化のためこうする（配列アクセスを減らす）
        dp[i] = min([dpj + abs(h - hj) for dpj, hj in zip(dp[m:i], H[m:i])])
    print(dp[N-1])

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

n = int(input())
p = list(map(float,input().split()))
dp = [[0] * (n+1) for i in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
    for j in range(i+1):
        if j > 0:
            dp[i][j] = dp[i-1][j]*(1-p[i-1])+dp[i-1][j-1]*p[i-1]
        else:
            dp[i][j] = dp[i-1][j]*(1-p[i-1])
ans = 0
for i in range(n//2+1,n+1):
    ans += dp[n][i]
print(ans)

### FIXED CODE ###

n = int(input())
p = list(map(float,input().split()))
dp = [[0] * (n+1) for i in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
    for j in range(i+1):
        if j > 0:
            dp[i][j] = dp[i-1][j]*(1-p[i-1])+dp[i-1][j-1]*p[i-1]
        else:
            dp[i][j] = dp[i-1][j]*(1-p[i-1])
ans = 0
for i in range(n//2+1,n+1):
    ans += dp[n][i]
print(ans)
### BUGGY CODE ###

import collections
n = int(input())
a = list(input())
b = collections.Counter(a)
ans =b['R']*b['G']*b['B']
for i in range(n-2):
    for j in range(i+1,n-1):
        if a[i] == a[j]:
            continue
        c = j*2 -i
        if c < n:
            if a[i] != a[j] and a[i] != a[c] and a[j] != a[c]:
                ans -= 1
print(ans)

### FIXED CODE ###

import collections
n = int(input())
a = input()
a = a.replace('R','1')
a = a.replace('G','2')
a = a.replace('B','3')
a = tuple(map(int,list(a)))
b = collections.Counter(a)
ans =b[3]*b[1]*b[2]
for i in range(n-2):
    for j in range(i+1,n):
        if a[i] == a[j]:
            continue
        c = j*2 -i
        if c < n:
            if a[i]+a[j]+a[c]==6:
                ans -= 1
        else:
            break
print(ans)
### BUGGY CODE ###

from copy import deepcopy

N, K = map(int, input().split())
V = tuple(map(int, input().split()))

all_score = sum(V)
memo = {}

def dfs(queue, hand, depth):
    # print(queue, hand, depth)
    if depth == K:
        score = all_score - sum(queue)
        memo[queue] = score
        # print('return', queue, score)
        return score
    if queue in memo:# and memo[queue] is not None:
        print('memo')
        return memo[queue]

    if queue not in memo:
        memo[queue] = None

    max_score = all_score - sum(queue)
    if len(queue) > 0:
        # A
        A_queue = queue[1:]
        if A_queue not in memo:
            A_hand = deepcopy(hand)
            A_hand.append(queue[0])
            score = dfs(A_queue, A_hand, depth + 1)
            if score > max_score:
                max_score = score
        # B
        B_queue = queue[:-1]
        if B_queue not in memo:
            B_hand = deepcopy(hand)
            B_hand.append(queue[-1])
            score = dfs(B_queue, B_hand, depth + 1)
            if score > max_score:
                max_score = score

    for i in range(len(hand)):
        # C
        C_queue = (hand[i],) + queue
        if C_queue not in memo:
            C_hand = deepcopy(hand)
            C_hand = C_hand[:i] + C_hand[i+1:]
            score = dfs(C_queue, C_hand, depth + 1)
            if score > max_score:
                max_score = score

        # D
        D_queue = queue + (hand[i],)
        if D_queue not in memo:
            D_hand = deepcopy(hand)
            D_hand = D_hand[:i] + D_hand[i + 1:]
            score = dfs(D_queue, D_hand, depth + 1)
            if score > max_score:
                max_score = score

    memo[queue] = max_score
    # print(queue, max_score)
    return max_score

ans = dfs(V, [], 0)
print('0' if ans < 0 else ans)

### FIXED CODE ###

from copy import deepcopy

N, K = map(int, input().split())
V = tuple(map(int, input().split()))
max_score = -1000000000
for i in range(K+1):
    for j in range(K - i + 1):
        if i + j > N:
            continue
        # 左からi個取る
        hand = list(V[:i])
        # 右からj個取る
        hand.extend(V[N-j:])
        # 最大(K - i - j)個戻せる
        # print(i, j, hand)
        score = sum(hand)
        counter = 0
        for h in sorted(hand):
            counter += 1
            if K - i - j - counter < 0:
                break
            if h < 0:
                score -= h
        if max_score < score:
            max_score = score
print(max_score)
### BUGGY CODE ###

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

u = list(set(A))
c = []
sum = 0
for j in u:
    _ = A.count(j)
    c.append(_)
    sum += int(_ * (_ - 1) / 2)

s = ""
for k in range(N):
    v = c[u.index(A[k])]
    s += str(sum - v + 1) + "\n"
print(s)

### FIXED CODE ###

import collections

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

u = collections.Counter(A)
sum = 0
for j, c in u.items():
    sum += int(c * (c - 1) / 2)

s = ""
for k in A:
    s += str(sum - u[k] + 1) + "\n"
print(s)
### BUGGY CODE ###

# coding: utf-8
import itertools
import sys
sys.setrecursionlimit(100000)
input=lambda : sys.stdin.readline().rstrip('\n')

n=int(input())
d=[0]+list(itertools.accumulate(map(int,input().split())))
memo=[[-1 for i in range(401)]for i in range(401)]
def split_slime(l,r):
    if l+1==r:
        return 0
    if memo[l][r]!=-1:
        return memo[l][r]
    mn=10**18
    for i in range(l+1,r):
        cost=(d[i]-d[l])+(d[r]-d[i])+split_slime(l,i)+split_slime(i,r)
        if mn>cost:
            mn=cost
    memo[l][r]=mn
    return memo[l][r]
print(split_slime(0,n))

### FIXED CODE ###

# coding: utf-8
import itertools
import sys
sys.setrecursionlimit(100000)
input=lambda : sys.stdin.readline().rstrip('\n')

n=int(input())
d=[0]+list(itertools.accumulate(map(int,input().split())))
memo=[[-1 for i in range(401)]for i in range(401)]
def split_slime(l,r):
    if l+1==r:
        return 0
    if memo[l][r]!=-1:
        return memo[l][r]
    mn=10**18
    for i in range(l+1,r):
        cost=(d[i]-d[l])+(d[r]-d[i])+split_slime(l,i)+split_slime(i,r)
        if mn>cost:
            mn=cost
    memo[l][r]=mn
    return memo[l][r]
print(split_slime(0,n))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

import networkx as nx

YES = "Yes"  # type: str
NO = "No"


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    G = nx.Graph()
    G.add_nodes_from([1+n for n in range(N)])

    G.add_edges_from([(a,b) for a,b in zip(A,B)])

    paths = nx.predecessor(G, 1)

    ans_list = []
    for key, val in sorted(paths.items()):
        if key != 1:
            ans_list.append((key,val[0]))

    print(YES)
    ans_list.sort(key=lambda x: x[0])
    for key, val in ans_list:
        print(val)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import deque

YES = "Yes"  # type: str


def solve(N: int, M: int, A: "List[int]", B: "List[int]"):
    dq = deque([])
    traversed = [False for _ in range(N+1)]
    ans = [None for _ in range(N+1)]

    G = {n : set([]) for n in range(1, N+1)}
    for a, b in zip(A,B):
        G[a].add(b)
        G[b].add(a)

    dq.append(1)
    traversed[1] = True

    while dq:
        s = dq.popleft()

        for node in G[s]:
            if not traversed[node]:
                dq.append(node)
                traversed[node] = True
                

                ans[node] = s

    print(YES)
    for s in ans:
        if s != None:
            print(s)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [int()] * (M)  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, M, A, B)

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

#!/usr/bin/env python3
import sys
import collections
import itertools

def main():
    input = sys.stdin.readline
    h, w = map(int, input().split())
    ch, cw = map(lambda x:int(x) - 1, input().split())
    dh, dw = map(lambda x:int(x) - 1, input().split())
    s = [list(input().rstrip()) for _ in range(h)]
    
    que = collections.deque()
    que.append((0, ch, cw))
    cost = [[-1] * w for _ in range(h)]
    cost[ch][cw] = 0
    
    while que:
        c, py, px = que.popleft()
        if cost[py][px] == -1:
            cost[py][px] = c
        
        for dy, dx in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
            ny, nx = py + dy, px + dx
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] == "." and cost[ny][nx] == -1:
                que.appendleft((c, ny, nx))
        
        for ny, nx in itertools.product(range(py - 2, py + 3), range(px - 2, px + 3)):
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] == "." and cost[ny][nx] == -1:
                que.append((c + 1, ny, nx))
    
    print(cost[dh][dw])

    
if __name__ == '__main__':
    main()


### FIXED CODE ###

import collections
import itertools

h, w = map(int, input().split())
sy, sx = map(lambda x:int(x) - 1, input().split())
gy, gx = map(lambda x:int(x) - 1, input().split())
maze = [list(input()) for _ in range(h)]

seen = [[-1] * w for _ in range(h)]
seen[sy][sx] = 0
que = collections.deque()
que.append((sy, sx))
tmp2 = [(sy, sx)]
cnt = 0
while True:
    tmp1 = []
    for sy, sx in tmp2:
        if maze[sy][sx] == ".":
            que.append((sy,sx))
            tmp1.append((sy, sx))
            while que:
                py, px = que.popleft()
                for dy, dx in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
                    ny = py + dy
                    nx = px + dx
                    if 0 <= ny < h and 0 <= nx < w and maze[ny][nx] == "." and seen[ny][nx] == -1:
                        seen[ny][nx] = cnt
                        que.append((ny, nx))
                        tmp1.append((ny, nx))
                        maze[sy][sx] = "#"
                        
    if seen[gy][gx] != -1:
        break

    flag = True
    d = [-2, -1, 0, 1, 2]
    tmp2 = []
    for py, px in tmp1:
        for i in range(5):
            for j in range(5):
                ny = py + d[i]
                nx = px + d[j]
                if 0 <= ny < h and 0 <= nx < w and maze[ny][nx] == "." and seen[ny][nx] == -1:
                    seen[ny][nx] = cnt + 1
                    que.append((ny, nx))
                    flag = False
                    tmp2.append((ny, nx))
    cnt += 1
    if flag:
        break
    if seen[gy][gx] != -1:
        break

print(seen[gy][gx])
### BUGGY CODE ###

import collections

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


def main(n: int, a: list):
    for i in range(N):
        b = a.copy()
        b.pop(i)

        counter = collections.Counter(b)

        # print(counter)

        pair_cnt = 0
        for k, v in counter.items():
            pair_cnt += v * (v - 1) / 2

        print(int(pair_cnt))


main(N, A)


### FIXED CODE ###

import collections

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


def main(n: int, a: list):
    counter = collections.Counter(a)
    pairs = {k: v * (v - 1) / 2 for k, v in counter.items()}
    pairs_all = sum(pairs.values())

    for i in range(N):
        k = a[i]
        v = counter[k] - 1
        pair_cnt = pairs_all - pairs[k] + (v * (v - 1) / 2)

        print(int(pair_cnt))


main(N, A)