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

import sys
input = sys.stdin.readline

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

m = 1<<n
ans = [0]*m

for i in range(1, m):
    max1 = max2 = 0
    j = i
    while j >= 0:
        j &= i
        if a[j] >= max1:
            max1, max2 = a[j], max1
        elif a[j] > max2:
            max2 = a[j]
        j -= 1
    ans[i] = max(ans[i-1], max1+max2)

print(*ans[1:], sep="\n")

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [[i] for i in a]

for j in range(n):
    for i in range(1<<n):
        if i & (1<<j):
            b[i] = sorted(b[i]+b[i^1<<j], reverse=True)[:2]
ans = []
tmp = 0
for i in range(1, 1<<n):
    tmp = max(tmp, sum(b[i]))
    ans.append(tmp)
print(*ans, sep="\n")
### BUGGY CODE ###

#-*-coding:utf-8-*-
import sys
input=sys.stdin.readline

def main():
    numbers=[]
    n = int(input())
    numbers=list(map(int,input().split()))

    for i in range(n):
        if i==0:
            left=sum(numbers[:i])
            right=sum(numbers[i:])
            continue
        else:
            if abs(right-left) > abs(sum(numbers[i:]) -sum(numbers[:i])):
                left=sum(numbers[:i])
                right=sum(numbers[i:])
    print(abs(right-left))        


if __name__=="__main__":
    main()

### FIXED CODE ###

#-*-coding:utf-8-*-
import sys
input=sys.stdin.readline
import numpy as np

def main():
    N=[]
    n = int(input())
    N=np.array(list(map(int,input().split())))
    Ncum=N.cumsum()
    L=Ncum[:-1]
    R=Ncum[-1]-L
    ans=np.abs(L-R).min()
    print(ans)

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

N=int(input())
S=[ord(c) for c in input()]
def zalgo(S):
    a=[0]*len(S)
    c=0
    for i in range(1,len(S)):
        if i+a[i-c]<c+a[c]:
            a[i]=a[i-c]
        else:
            j=max(0,c+a[c]-i)
            while i+j<len(S) and S[j]==S[i+j]:
                j+=1
            a[i]=j
    a[0]=len(S)
    return a
r=0
for i in range(N):
    a=zalgo(S[i:])
    for j in range(N-i):
        r=max(r,min(a[j],j))
print(r)

### FIXED CODE ###

N=int(input())
S=input()
l,u=0,N
while l+1<u:
    m=(l+u)//2
    s=set()
    for i in range(N-m*2+1):
        s.add(S[i:i+m])
        if S[i+m:i+m*2] in s:
            l=m
            break
    if l!=m:
        u=m
print(l)
### BUGGY CODE ###

n = int(input())
arr = input("")
a = [int(n) for n in arr.split()]
ans = 1
for i in range(n):
    ans = ans * int(a[i])
if ans > int(1e18):
    print("-1")
else:
    print(ans)


### FIXED CODE ###

n = int(input())
a = list( map (int , input().split() ) )
a.sort()
ans = 1
for i in range(n):
    ans*=a[i]
    if ans>10**18:
      print(-1)
      exit()

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

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

fin = min(A) == N
for j in range(K):
    if fin:
        break
    T = [0] * (N + 1)
    for i in range(N):
        T[max(i - A[i], 0)] += 1
        T[min(i + A[i] + 1, N)] -= 1
    A[0] = T[0]
    fin = A[0] == N
    for i in range(1, N):
        A[i] = A[i - 1] + T[i]
        if A[i] < N:
            fin = False
print(' '.join(list(map(str, A))))


### FIXED CODE ###

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

fin = min(A) == N
for j in range(K):
    if fin:
        break
    T = [0] * (N + 1)
    for i in range(N):
        T[max(i - A[i], 0)] += 1
        T[min(i + A[i] + 1, N)] -= 1
    A[0] = T[0]
    fin = A[0] == N
    for i in range(1, N):
        A[i] = A[i - 1] + T[i]
        if A[i] < N:
            fin = False
print(' '.join(list(map(str, A))))
### BUGGY CODE ###

import operator
import collections

n, k = map(int, input().split())
sushies = []
for _ in range(n):
    t, d = map(int, input().split())
    sushies.append((t, d))

sushies.sort(key=operator.itemgetter(1), reverse=True)

dishes = sushies[:k]
c = collections.Counter(t for t, d in dishes)
a = sum(d for t, d in dishes)
answer = a + len(c) ** 2

for t, d in sushies[k:]:
    if t in c:
        continue

    x = -1
    for i in reversed(range(k)):
        if c[dishes[i][0]] > 1:
            x = i
            break

    if x == -1:
        break

    a = a + d - dishes[x][1]
    c[t] += 1
    c[dishes[x][0]] -= 1
    del dishes[x]
    dishes.append((t, d))

    answer = max(answer, a + len(c) ** 2)

print(answer)


### FIXED CODE ###

import operator
import collections

n, k = map(int, input().split())
sushies = []
for _ in range(n):
    t, d = map(int, input().split())
    sushies.append((t, d))

sushies.sort(key=operator.itemgetter(1), reverse=True)

dishes = sushies[:k]
c = collections.Counter(t for t, d in dishes)
a = sum(d for t, d in dishes)
answer = a + len(c) ** 2
x = k - 1
for t, d in sushies[k:]:
    if t in c:
        continue

    while x >= 0:
        if c[dishes[x][0]] > 1:
            break
        x -= 1

    if x == -1:
        break


    a = a + d - dishes[x][1]
    c[t] += 1
    c[dishes[x][0]] -= 1
    del dishes[x]
    dishes.append((t, d))

    answer = max(answer, a + len(c) ** 2)

print(answer)
### BUGGY CODE ###



def main():
    N,T=map(int,input().split())
    A=[0 for i in range(0,N)]
    B=[0 for i in range(0,N)]
    for i in range(0,N):
        A[i],B[i]=map(int,input().split())
    C=[[A[i],B[i]] for i in range(0,N)]
    C.sort()
    B=[C[i][1] for i in range(0,N)]
    A=[C[i][0] for i in range(0,N)]
    dp=[[0 for j in range(0,T+1)] for i in range(0,N+1)]#i番目までの料理でT分までの注文での満足度最大値
    for i in range(0,N):
        for j in range(1,T+1):
            if j-A[N-1-i]<0:
                dp[i+1][j]=max(dp[i][j],B[N-1-i])
            else:
                dp[i+1][j]=max(dp[i][j],dp[i][j-A[N-1-i]]+B[N-1-i])
    print(dp[N][T])

if __name__ == '__main__':
    main()


### FIXED CODE ###



def main():
    N,T=map(int,input().split())
    A=[0 for i in range(0,N)]
    B=[0 for i in range(0,N)]
    for i in range(0,N):
        A[i],B[i]=map(int,input().split())
    C=[[A[i],B[i]] for i in range(0,N)]
    C.sort()
    B=[C[i][1] for i in range(0,N)]
    A=[C[i][0] for i in range(0,N)]
    dp=[[0 for j in range(0,T+1)] for i in range(0,N+1)]#i番目までの料理でT分までの注文での満足度最大値
    for i in range(0,N):
        for j in range(1,T+1):
            if j-A[N-1-i]<0:
                dp[i+1][j]=max(dp[i][j],B[N-1-i])
            else:
                dp[i+1][j]=max(dp[i][j],dp[i][j-A[N-1-i]]+B[N-1-i])
    print(dp[N][T])

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

import sys

(str_n,str_y) = input().split()
n = int(str_n)
y = int(str_y)

if y % 1000 != 0:
    print (-1,-1,-1)
    sys.exit()

for i in range(min(n,y//10000),-1,-1):
    left = y - 10000*i
    
    for j in range(min(n-i,left//5000),-1,-1):
        left = y - 10000*i - 5000*j
        
        for k in range(min(n-i-j,left//1000),-1,-1):
            left = y - 10000*i - 5000*j - 1000*k
            if left == 0:
                if i+j+k == n:
                    print (i,j,k)
                    sys.exit()

print (-1,-1,-1)

### FIXED CODE ###

import sys

(str_n,str_y) = input().split()
n = int(str_n)
y = int(str_y)

if y % 1000 != 0:
    print (-1,-1,-1)
    sys.exit()

i_max = min(n,y//10000)
for i in range(i_max,-1,-1):
    left = y - 10000*i
    
    j_max = min(n-i,left//5000)
    for j in range(j_max,-1,-1):
        left = y - 10000*i - 5000*j
        
        k = left // 1000
        if i+j+k == n:
            print (i,j,k)
            sys.exit()

print (-1,-1,-1)
### BUGGY CODE ###

X = int(input())
for i1 in range(1000000):
  for i2 in range(1000000):
    for i3 in range(1000000):
      for i4 in range(1000000):
        for i5 in range(1000000):
          for i6 in range(1000000):
            if 100 * i1 + 101 * i2 + 102 * i3 + 103 * i4 + 104 * i5 + 105 * i6 == X:
              print("1")
            else:
              print("0")
  


### FIXED CODE ###

X = int(input())
a = X // 100
r = X % 100
if r <= 5 * a:
  print("1")
else:
  print("0")
### BUGGY CODE ###

S = input()
mod = 10**9+7

N = len(S)
A1,A2,C1,C2 = [1]*N,[1]*N,[1]*N,[1]*N
a,aa = 0,0
c,cc = 0,0
for i in range(1,N):
    if S[i-1]=="A":
        a += 1
    elif S[i-1]=="?":
        aa += 1
    A1[i],A2[i] = a,aa
for i in range(1,N):
    if S[N-1-i+1]=="C":
        c += 1
    elif S[N-1-i+1]=="?":
        cc += 1
    C1[N-1-i] = c
    C2[N-1-i] = cc

Ans = 0
for i in range(1,N-1):
    if S[i] in ("B","?"):
        ta,tc = 0,0
        if A2[i]==0:
            ta = A1[i]
        else:
            ta = (3**A2[i])*A1[i] + 3**(A2[i]-1)*A2[i]
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = (3**C2[i])*C1[i] + 3**(C2[i]-1)*C2[i]
        Ans += ta*tc
        Ans %= mod

print(Ans)

### FIXED CODE ###

S = input()
mod = 10**9+7

N = len(S)
A1,A2,C1,C2 = [1]*N,[1]*N,[1]*N,[1]*N
a,aa = 0,0
c,cc = 0,0
for i in range(1,N):
    if S[i-1]=="A":
        a += 1
    elif S[i-1]=="?":
        aa += 1
    A1[i],A2[i] = a,aa
for i in range(1,N):
    if S[N-1-i+1]=="C":
        c += 1
    elif S[N-1-i+1]=="?":
        cc += 1
    C1[N-1-i] = c
    C2[N-1-i] = cc

Ans = 0
for i in range(1,N-1):
    if S[i] in ("B","?"):
        ta,tc = 0,0
        if A2[i]==0:
            ta = A1[i]
        else:
            ta = pow(3,A2[i],mod)*A1[i] + pow(3,A2[i]-1,mod)*A2[i]
        if C2[i]==0:
            tc = C1[i]
        else:
            tc = pow(3,C2[i],mod)*C1[i] + pow(3,C2[i]-1,mod)*C2[i]
        Ans += ta*tc
        Ans %= mod

print(Ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
result = 1
for i in range(N):
    result = result * A[i]
if result > 10**18:
    print(-1)
else:
    print(result)

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

N = int(input())
A = list(map(int,input().split()))
A.sort()
result = 1
for i in range(N):
    result = result * A[i]
    if result > 1e18:
        result = -1
        break
print(result)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import functools
INF = float("inf")

MOD = 2  # type: int


def power(b, p):
    if p == 0:
        return 1
    elif p == 1:
        return b
    elif p % 2 == 1:
        return b*power(b, p-1)
    else:
        return power(b*b, p//2)


def solve(p: int, a: "List[int]"):
    kaijo = [1]*p
    kaijo_inv = [1]*p

    for i in range(2, p):
        kaijo[i] = (kaijo[i-1]*i) % p
        kaijo_inv[i] = power(kaijo[i], p-2) % p

    @functools.lru_cache(maxsize=None)
    def cmb(n, r):
        return (kaijo[n]*kaijo_inv[n-r]*kaijo_inv[r]) % p

    b = [0]*p
    for ai, av in enumerate(a):
        if av == 1:
            for i in range(p):
                b[i] += -cmb(p-1, i) * power(-ai, p-i-1)
                b[i] %= p
            b[0] += 1
            b[0] %= p
    print(*b, sep=" ")
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    p = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(p-1-0+1)]  # type: "List[int]"
    solve(p, a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import functools
INF = float("inf")


def solve(p: int, a: "List[int]"):
    N = p+1
    MOD = p

    inv = [0]*N
    inv[1] = 1
    for i in range(2, N):
        inv[i] = -inv[MOD % i]*(MOD//i) % MOD

    b = [0]*p
    for ai, av in enumerate(a):
        if av == 0:
            continue

        c = 1
        d = 1
        for i in range(p-1, -1, -1):
            b[i] += - c * d
            b[i] %= p
            c = c * i * inv[p-i] % p
            d = -d*ai % p
        b[0] += 1
        b[0] %= p
    print(*b, sep=" ")
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    p = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(p-1-0+1)]  # type: "List[int]"
    solve(p, a)


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

import sys
input = sys.stdin.readline

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

################################
N = int(input()) # 頂点数
W = N - 1 # 辺の数

cost = [[float("inf") for _ in range(N)] for _ in range(N)] 
#cost[u][v] : 辺uvのコスト(存在しないときはinf この場合は10**10)
for i in range(W):
    x, y, z = [int(x) for x in input().split()]
    cost[x - 1][y - 1] = z
    cost[y - 1][x - 1] = z
Q, K = [int(x) for x in input().split()]

K_costs = dijkstra(K - 1, N, W, cost) # Kから各頂点へのコスト
ans = [] # クエリごとの答え

for _ in range(Q):
    x, y = [int(x) for x in input().split()]
    ans.append(K_costs[x - 1] + K_costs[y - 1])

for i in ans:
    print(i)

### FIXED CODE ###

import sys
input = sys.stdin.readline

import heapq
def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * N
    used = [True] * N #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

################################
N = int(input()) # 頂点数
W = N - 1 # 辺の数

edge = [[] for i in range(N)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(W):
    x, y, z = [int(x) for x in input().split()]
    edge[x - 1].append([z, y - 1])
    edge[y - 1].append([z, x - 1])
Q, K = [int(x) for x in input().split()]

K_costs = dijkstra_heap(K - 1) # Kから各頂点へのコスト

for _ in range(Q):
    x, y = [int(x) for x in input().split()]
    print(K_costs[x - 1] + K_costs[y - 1])
### BUGGY CODE ###

S=input()
N=len(S)
dp=[0 for i in range(N)]
check=[0 for i in range(N)]

List=[]
moji = ''
kireme=False
for i in range(N):
    moji+=S[i]
    dp[i]=dp[i-1]
    l=len(moji)
    for j in range(l):
        if int(moji[l-j-1:])%2019==0:
            List.append((i-j,i,int(moji[l-j-1:])))
            check[i]+=1+check[i-j-1]
            dp[i]+=1
            """
            if check[max(i-j-1,0)]:
                #check[i-j-1]+=1
                dp[i]+=check[i-j-1]
            """
            
#print(List)
#print(check)
#print(dp) 
print(dp[N-1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)


S = input()
N, P = len(S),2019

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

num = [0] * P
num[0] = 1
now, ans = 0, 0
_10 = 1
for i in range(N-1, -1, -1):
    now = (now + int(S[i]) * _10) % P
    _10 *= 10
    _10 %= P
    ans += num[now]
    num[now] += 1

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

N, M = [int(x) for x in input().split(" ")]
L, R = [], []
for i in range(M):
    l, r = [int(x) for x in input().split(" ")]
    L.append(l - 1)
    R.append(r - 1)

pass_key = set([i for i in range(N)])
for i in range(M):
    if len(pass_key) == 0:
        print(0)
        exit(0)
    else:
        pass_key = pass_key & set([ID for ID in range(L[i], R[i] + 1)])

print(len(pass_key))


### FIXED CODE ###

N, M = [int(x) for x in input().split(" ")]
L, R = [], []

for i in range(M):
    l, r = [int(x) for x in input().split(" ")]
    L.append(l - 1)
    R.append(r - 1)

L_max = max(L)
R_min = min(R)

count = R_min - L_max + 1 if R_min - L_max >= 0 else 0
print(count)
### BUGGY CODE ###

N,D,A = map(int,input().split())
XH = [list(map(int,input().split())) for i in range(N)]
XH.sort()
from math import ceil
times = ceil(XH[0][1]/A)
ans = times
damege = [times*A]
coor = [XH[0][0]+2*D]
start = 0
end = 1
for i in range(1,N):
    while start < end and coor[start] < XH[i][0]:
        start += 1
    H = XH[i][1] - sum(damege[start:end])
    if H > 0:
        times = ceil(H/A)
        ans += times
        damege.append(times*A)
        coor.append(XH[i][0]+2*D)
        end += 1
print(ans)

### FIXED CODE ###

N,D,A = map(int,input().split())
XH = [list(map(int,input().split())) for i in range(N)]
XH.sort()
from math import ceil
times = ceil(XH[0][1]/A)
ans = times
damege = [times*A]
coor = [XH[0][0]+2*D]
start = 0
end = 1
dam = sum(damege[start:end])
for i in range(1,N):
    st = start
    while start < end and coor[start] < XH[i][0]:
        start += 1
    dam -= sum(damege[st:start])
    H = XH[i][1] - dam
    if H > 0:
        times = ceil(H/A)
        ans += times
        damege.append(times*A)
        dam += times*A
        coor.append(XH[i][0]+2*D)
        end += 1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
P = list(map(int, input().split()))
max_total = 0

for i in range(N-K+1):
    max_total = max(max_total, sum(P[i:i+K]))

ans = (max_total + K) / 2

print(ans)

### FIXED CODE ###

from itertools import accumulate

N, K = map(int, input().split())
P = map(int, input().split())
acc_P = list(accumulate(P))
ans = (acc_P[K-1] + K) / 2

for i in range(N-K):
    ans = max(ans, (acc_P[i+K] - acc_P[i] + K) / 2)

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

N=int(input())
A=list(map(int,input().split()))
counts=0
limit=0
for i in range(1,N+1):
  a=A.count(i)
  counts+=1
  limit+=a
  print(a)
  if a==N:
    quit()
for j in range(N-counts):
  print(0)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
a={}
for i in range(1,N+1):
  a.update({i:0})
for j in A:
  a[j]+=1
for k,l in a.items():
  print(l)
### BUGGY CODE ###

import collections
n,m = map(int,input().split())
r = []
ans = 0
for i in range(m):
    ll,rr = map(int,input().split())
    for j in range(ll-1,rr):
        r.append(j)
cnt = collections.Counter(r)
for i in cnt.values():
    if i == m:
        ans += 1
print(ans)

### FIXED CODE ###

import collections
n,m = map(int,input().split())
r = []
l = []
for i in range(m):
    ll,rr = map(int,input().split())
    r.append(rr)
    l.append(ll)
ans = min(r) - max(l) +1
if ans > 0:
    print(ans)
else :
    print(0)
### BUGGY CODE ###

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

N = int(input())
A = [deque([int(i)-1 for i in input().split()]) for _ in range(N)]

def solve() :
    q = list(range(N))
    count = 0
    ret = 0
    while count != N * (N - 1) :
        if len(q) == 0 :
            return -1
        
        done = [False] * N
        schedule = []
        for i in q :
            j = A[i][0]
            if done[i] or done[j]:
                continue
                
            if i == A[j][0] :
                schedule.append(i)
                schedule.append(j)
                done[i] = done[j] = True
                
        ret += 1
        q = []
        for i in schedule :
            A[i].popleft()
            if len(A[i]) > 0 :
                q.append(i)
        count += len(schedule)
        
    return ret
    
print(solve())

### FIXED CODE ###

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

N = int(input())
A = [deque([int(i)-1 for i in input().split()]) for _ in range(N)]

def solve() :
    q = list(range(N))
    count = 0
    ret = 0
    while count != N * (N - 1) :
        if len(q) == 0 :
            return -1
        
        schedule = set()
        for i in q :
            j = A[i][0]
            if i in schedule or j in schedule :
                continue
                
            if i == A[j][0] :
                schedule.add(i)
                schedule.add(j)
                
        ret += 1
        q = []
        for i in schedule :
            A[i].popleft()
            if len(A[i]) > 0 :
                q.append(i)
        count += len(schedule)
        
    return ret
    
print(solve())
### BUGGY CODE ###

from sys import stdin
def solve():
    import collections
    readline = stdin.readline
    h,w = map(int,readline().split())
    si,sj = map(int,readline().split())
    gi,gj = map(int,readline().split())
    si,sj,gi,gj = si-1,sj-1,gi-1,gj-1
    grid = []
    for _ in [0]*h:
        grid.append(readline()[:-1])
    INF = float("inf")
    dist = [[INF]*w for _ in range(h)]
    q = collections.deque([(si,sj)])
    dist[si][sj] = 0
    while q:
        i,j = q.popleft()
        if (i,j) == (gi,gj):
            return dist[i][j]
        for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
            if 0 <= ni and ni < h and 0 <= nj and nj < w and grid[ni][nj] == ".":
                if dist[ni][nj] > dist[i][j]:
                    dist[ni][nj] = dist[i][j]
                    q.appendleft((ni,nj))
        listj = range(j-2,j+3)
        for ni in range(i-2,i+3):
            if not (0 <= ni and ni < h): continue
            for nj in listj:
                if not (0 <= nj and nj < w): continue
                if grid[ni][nj] == "." and dist[ni][nj] > dist[i][j] + 1:
                    dist[ni][nj] = dist[i][j] + 1
                    q.append((ni,nj))

    return -1

print(solve())

### FIXED CODE ###

from sys import stdin
def solve():
    import collections
    readline = stdin.readline
    h,w = map(int,readline().split())
    si,sj = map(int,readline().split())
    gi,gj = map(int,readline().split())
    si,sj,gi,gj = si-1,sj-1,gi-1,gj-1
    grid = []
    for _ in [0]*h:
        grid.append(readline()[:-1])
    INF = float("inf")
    dist = [[INF]*w for _ in range(h)]
    q = collections.deque([(si,sj)])
    dist[si][sj] = 0
    while q:
        i,j = q.popleft()
        if (i,j) == (gi,gj):
            return dist[i][j]
        for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
            if 0 <= ni and ni < h and 0 <= nj and nj < w and grid[ni][nj] == ".":
                if dist[ni][nj] > dist[i][j]:
                    dist[ni][nj] = dist[i][j]
                    q.appendleft((ni,nj))
        listj = range(j-2,j+3)
        for ni in range(i-2,i+3):
            if not (0 <= ni and ni < h): continue
            for nj in listj:
                if not (0 <= nj and nj < w): continue
                if grid[ni][nj] == "." and dist[ni][nj] > dist[i][j] + 1:
                    dist[ni][nj] = dist[i][j] + 1
                    q.append((ni,nj))

    return -1

print(solve())
### BUGGY CODE ###

N = int(input()) #1行目のNを取得する
i = list(map(int, input().split()))

result = 1

for x in range(N):
  result *= i[x]

  
if(result>pow(10,18)):
   result = -1
print(result)



### FIXED CODE ###

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

result = 1
flag = 0
zero_flag = False
for x in range(N):
  if(i[x]==0):
    zero_flag = True
    result = 0

if(zero_flag==False):
  for x in range(N):
    result *= i[x]
    if(result>pow(10,18)):
      flag = 1
      break

if(flag==1):
  print('-1')
else:
  print(result)
### BUGGY CODE ###

s=[2]
a=[int(i) for i in range(2,100000000) if pow(2 ,int(i)-1, int(i)) ==1]

while a!=[]:
    t=a[0]
    a=[i for i in a if i % t !=0]
    s.append(t)
 
n=int(input())
x=0
for i  in range(n):
    if int(input()) in s:
        x+=1
print(x)
 

### FIXED CODE ###

s=[2]
a=[int(i) for i in range(2,10000) if pow(2 ,int(i)-1, int(i)) ==1]

while a!=[]:
    t=a[0]
    a=[i for i in a if i % t !=0]
    s.append(t)

n=int(input())
x=0
for i  in range(n):
    y=0
    t = int(input())
    for j in s:
        if t % j ==0 and t !=j:
           break
    else:
        x+=1
print(x)
### BUGGY CODE ###

import math

N=int(input())
count=[0]*(N+1)
for i in range(N):
  for x in range(1,N+1):
    for y in range(1,N+1):
      for z in range(1,N+1):
        if(x**2+y**2+z**2+x*y+y*z+z*x==i):
          count[i]+=1
for j in range(1,N+1):
  print(count[j])

### FIXED CODE ###

N=int(input())
count=[0]*(N+1)
for x in range(1,100):
  for y in range(1,100):
    for z in range(1,100):
      n=x*x+y*y+z*z+x*y+y*z+z*x
      if(n<=N):
        count[n]+=1
for i in range(1,N+1):
  print(count[i])