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

from collections import deque
N=int(input())
M=N*(N-1)//2
D=[[]for i in range(M)]
F=[[]for i in range(M)]
for i in range(N):
  x=list(map(int,input().split()))
  for j in range(N-2):
    a,b,c=i+1,x[j],x[j+1]
    x1,x2=min(i+1,x[j]),max(i+1,x[j])
    y1,y2=min(i+1,x[j+1]),max(i+1,x[j+1])
    e=M-(N-x1)*(N-x1+1)//2
    f=e+(x2-x1-1)
    g=M-(N-y1)*(N-y1+1)//2
    h=g+(y2-y1-1)
    D[f].append(h)
    F[h].append(f)
P=[-1]*M
def bfs(u):
  P[u]=0
  queue=deque([u])
  while queue:
    v=queue.popleft()    
    for i in D[v]:
      P[i]=P[v]+1
      queue.append(i)
for i in range(M):
  if len(F[i])==0:
    bfs(i)
if min(P)==-1:
  print(-1)
else:
  print(max(P)+1)

### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10**7)

N=int(input())
M=N*(N-1)//2
D=[[]for i in range(M)]
F=[[]for i in range(M)]
for i in range(N):
  x=list(map(int,input().split()))
  for j in range(N-2):
    a,b,c=i+1,x[j],x[j+1]
    x1,x2=min(i+1,x[j]),max(i+1,x[j])
    y1,y2=min(i+1,x[j+1]),max(i+1,x[j+1])
    e=M-(N-x1)*(N-x1+1)//2
    f=e+(x2-x1-1)
    g=M-(N-y1)*(N-y1+1)//2
    h=g+(y2-y1-1)
    D[f].append(h)
    F[h].append(f)
    
q=deque()
P=[0]*M
for i in range(M):
  if len(F[i])==0:
    q.append((i,0))

r=[]
while q:
  v1,cnt=q.popleft()
  r.append((v1,cnt))
  for v2 in D[v1]:
    P[v2]+=1
    if P[v2]==len(F[v2]):
      q.append((v2,cnt+1))

if len(r)!=M:
  print(-1)
else:
  print(r[-1][-1]+1)
### BUGGY CODE ###

storeNum, canNum = input().split()
storeNum = int(storeNum)
canNum = int(canNum)
costs = [0] * storeNum
maxCanNumbers = [0] * storeNum

for i in range(storeNum):
    costs[i], maxCanNumbers[i] = input().split()
    costs[i] = int(costs[i])
    maxCanNumbers[i] = int(maxCanNumbers[i])

currentStoreHasMoreCans = False
totalPrice = 0

while canNum > 0 and not currentStoreHasMoreCans:
    currentStoreHasMoreCans = True
    minCostIndex = costs.index(min(costs))
    if canNum >= maxCanNumbers[minCostIndex]:
        totalPrice = totalPrice + costs[minCostIndex] * maxCanNumbers[minCostIndex]
        canNum = canNum - maxCanNumbers[minCostIndex]
    else:
        totalPrice = totalPrice + costs[minCostIndex] * canNum
        canNum = 0
    currentStoreHasMoreCans = False
    costs[minCostIndex] = 1000000001

print(totalPrice)

### FIXED CODE ###

storeNum, canNum = input().split()
storeNum = int(storeNum)
canNum = int(canNum)
costs = [0] * storeNum
maxCanNumbers = [0] * storeNum

for i in range(storeNum):
    costs[i], maxCanNumbers[i] = input().split()
    costs[i] = int(costs[i])
    maxCanNumbers[i] = int(maxCanNumbers[i])

currentStoreHasMoreCans = False
totalPrice = 0

costs, maxCanNumbers = (list(x) for x in zip(*sorted(zip(costs, maxCanNumbers))))

for i in range(storeNum):
    if canNum >= maxCanNumbers[i]:
        totalPrice = totalPrice + costs[i] * maxCanNumbers[i]
        canNum = canNum - maxCanNumbers[i]
        if canNum is 0:
            break
    else:
        totalPrice = totalPrice + costs[i] * canNum
        canNum = 0    
        break

print(totalPrice)
### BUGGY CODE ###

a, b = map(int, input().split())
large = max(a, b)
ans = 0

for i in range(large):
	if abs(a - i) == abs(b - i):
		ans = i
		break

if ans == 0:
	print("IMPOSSIBLE")
else:
	print(ans)


### FIXED CODE ###

a, b = map(int, input().split())
large = max(a, b)
ans = ((a + b) / 2)

if ans.is_integer():
	print(int(ans))
else:
	print("IMPOSSIBLE")
### BUGGY CODE ###

#!/usr/bin/env python3

def solve(n,k,q,a):
    l = [(k+a.count(i+1)-q)>0 for i in range(n)] 
    return l


def main():
    N,K,Q = map(int,input().split())
    a = [int(input()) for _ in range(Q)]
    L = solve(N,K,Q,a)
    for i in range(N):
        print("Yes" if L[i] else "No")

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
from collections import Counter


def main():
    N,K,Q = map(int,input().split())
    a = [int(input()) for _ in range(Q)]
    d = Counter(a)
    L = [(K+d[i+1]-Q)>0 for i in range(N)] 
    for i in range(N):
        print("Yes" if L[i] else "No")

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

L, R = map(int, input().split())

R = min(R, L+(2019*2)) # 長さを制限しても同じ
MOD = 2019
ans = 2018

for i in range(L, R): # iはLからR-1まで
    for j in range(i+1, R+1): # jはi+1からRまで
        n = (i*j)%MOD
        ans = min(n, ans)

print(ans)



### FIXED CODE ###

L, R = map(int, input().split())

R = min(R, L+(2019)) # 長さを制限しても同じ
MOD = 2019
ans = 2018

for i in range(L, R): # iはLからR-1まで
    for j in range(i+1, R+1): # jはi+1からRまで
        n = (i*j)%MOD
        ans = min(n, ans)

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

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N, Q = iim()
    it = map(int, sys.stdin.read().split())

    N2 = N - 2
    cc = [N-1] * 2
    ans = (N-2)**2
    A = [[N2]*(N2) for i in range(2)]

    for q, i in zip(it, it):
        q -= 1; i -= 2
        #print(q, i, N2)
        val = A[q][i]
        ans -= val
        aa = A[q^1]
        for j in range(val):
            aa[j] = min(aa[j], i)
        #print(ans, A)
    print(ans)


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N, Q = iim()
    it = map(int, sys.stdin.read().split())

    M = N + 1if N & 1 else N
    NM = 1<<M.bit_length()
    ans = (N-2)**2
    A = [[N-2]*(NM+M) for i in range(2)]

    def set(a, i, j, x):
        i += NM; j += NM
        while i < j:
            a[i] = min(a[i], x)
            if i&1:
                i += 1
            a[j] = min(a[j], x)
            if j&1 == 0:
                j -= 1
            i >>= 1; j >>= 1
        a[i] = min(a[i], x)
    def get(a, i):
        i += NM
        ans = a[i]
        while i > 0:
            i >>= 1
            ans = min(ans, a[i])
        return ans

    for q, i in zip(it, it):
        q -= 1; i -= 2
        val = get(A[q], i)
        ans -= val
        set(A[q^1], 0, val, i)
    print(ans)


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

k, s = map(int, input().split())

ans = 0
for i in range(k+1):
  for j in range(k+1):
    for l in range(k+1):
      if i+j+l==s:
        ans += 1
        
print(ans)

### FIXED CODE ###

k , s = map(int, input().split())

ans = 0

for x in range(k+1):
  for y in range(k+1):
      if s-x-y <= k and s-x-y>=0:
        ans += 1
        
print(ans)
### BUGGY CODE ###

h, w = map(int, input().split())
S = [list(input()) for _ in range(h)]
L = [[0] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if S[i][j] == '#':
            L[i][j] = 0
        elif j == 0:
            L[i][j] = 1
        else:
            L[i][j] = L[i][j-1] + 1
R = [[0] * w for _ in range(h)]
for i in range(h):
    for j in reversed(range(w)):
        if S[i][j] == '#':
            R[i][j] = 0
        elif j == w-1:
            R[i][j] = 1
        else:
            R[i][j] = R[i][j+1] + 1
U = [[0] * w for _ in range(h)]
for j in range(w):
    for i in range(h):
        if S[i][j] == '#':
            U[i][j] = 0
        elif i == 0:
            U[i][j] = 1
        else:
            U[i][j] = U[i-1][j] + 1
D = [[0] * w for _ in range(h)]
for j in range(w):
    for i in reversed(range(h)):
        if S[i][j] == '#':
            D[i][j] = 0
        elif i == h-1:
            D[i][j] = 1
        else:
            D[i][j] = D[i+1][j] + 1
tmp = [[0] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        tmp[i][j] = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, tmp[i][j])
print(ans)


### FIXED CODE ###

h, w = map(int, input().split())
S = [list(input()) for _ in range(h)]
L = [[0] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        # if S[i][j] == '#':
        #     L[i][j] = 0
        if S[i][j] == '.':
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j-1] + 1
R = [[0] * w for _ in range(h)]
for i in range(h):
    for j in reversed(range(w)):
        # if S[i][j] == '#':
        #     R[i][j] = 0
        if S[i][j] == '.':
            if j == w-1:
                R[i][j] = 1
            else:
                R[i][j] = R[i][j+1] + 1
U = [[0] * w for _ in range(h)]
for j in range(w):
    for i in range(h):
        # if S[i][j] == '#':
        #     U[i][j] = 0
        if S[i][j] == '.':
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i-1][j] + 1
D = [[0] * w for _ in range(h)]
for j in range(w):
    for i in reversed(range(h)):
        # if S[i][j] == '#':
        #     D[i][j] = 0
        if S[i][j] == '.':
            if i == h-1:
                D[i][j] = 1
            else:
                D[i][j] = D[i+1][j] + 1
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)
print(ans)
### BUGGY CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
for i in range(N):
  if i==0:
    print(sorted(A[i+1:])[-1])
  if i!=0 and i!=N-1:
    li1=sorted(A[:i])[-1]
    li2=sorted(A[i+1:])[-1]
    print(max(li1,li2))
  if i==N-1:
    print(sorted(A[:i])[-1])
  

### FIXED CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
AA=sorted(A,reverse=True)
for i in range(N):
  if AA[0]!=A[i]:
    print(AA[0])
  else:
    print(AA[1])
### BUGGY CODE ###

###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

N, A, B, C, D = mi()
#S[0~N-1]でアクセス
cells = input()

if C > D:
  c = C
  C = D
  D = c
  a = A
  A = B
  B = a

#全部0~N-1ベースにする
A -= 1
B -= 1
C -= 1
D -= 1

#既にスタック済みの座標の組(visited[0~N-1][0~N-1]でアクセス)
visited = [[0]*N for _ in range(N)]

st = []
#初期座標
st.append((A,B))

#結果が出るまでループする
#スタックから座標の組を取り出し、F>Sの優先順位で動かしてスタックに入れる

while 1:
  #選択肢がなくなったら、駄目だったと分かる
  try:
    s, f = st.pop()
  except:
    print('No')
    exit()

  #ここがゴールかどうか
  if s==C and f==D:
    print('Yes')
    exit()
  #Fが動けるかどうか
  fok = 0
  try:
    if visited[s][f+2]==0 and cells[f+2]=='.' and s != f+2:
      st.append((s,f+2))
      visited[s][f+2] = 1
      fok = 1
  except:
    pass
  try:
    if visited[s][f+1]==0 and cells[f+1]=='.' and s != f+1:
      st.append((s,f+1))
      visited[s][f+1] = 1
      fok = 1
  except:
    pass
  #Fが動けなかった場合のみSが動く
  if fok == 0:
    try:
      if visited[s+2][f]==0 and cells[s+2]=='.' and s+2 != f:
        st.append((s+2,f))
        visited[s+2][f] = 1
        fok = 1
    except:
      pass
    try:
      if visited[s+1][f]==0 and cells[s+1]=='.' and s+1 != f:
        st.append((s+1,f))
        visited[s+1][f] = 1
        fok = 1
    except:
      pass

### FIXED CODE ###

###template###
import sys
def input(): return sys.stdin.readline().rstrip()
def mi(): return map(int, input().split())
###template###

N, A, B, C, D = mi()
#S[0~N-1]でアクセス
cells = input()

#全部0~N-1ベースにする
A -= 1
B -= 1
C -= 1
D -= 1

ans = '?'

goal = max(C,D)


rockcheck = 0 #直前が岩なら1
for i, cell in enumerate(cells):
  if i < A or goal < i: continue
  if rockcheck == 1 and cell == '#':
    ans = 'No'
    break
  elif cell == '#': rockcheck = 1
  else: rockcheck = 0

#C<Dならflag=0, D<Cならflag=1
if C < D: flag = 0
else: flag = 1

if ans == 'No':
  print('No')
  exit()
elif flag == 0: #C<Dならこの時点で勝ち確
  print('Yes')
  exit()
#そうでなければ戦いは続く

ans = 'No'
#C<Dの場合決着がついているので、ここからは必ずD<C
#かつ、##は無いことが保証されている
blankcheck = 0 #直前が.なら1, 直前が..なら2
for i, cell in enumerate(cells):
  if i < (B-1) or (D+1) < i: continue
  if cell == '.': blankcheck += 1
  else: blankcheck = 0
  if blankcheck == 3:
    ans = 'Yes'
    break

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

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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    count = Counter(A)
    
    memo = dict()
    def dp(a, b, c):
        if (a, b, c) in memo:
            return memo[(a, b, c)]
        
        if a == b == c == 0:
            return 0
        
        if a < 0 or b < 0 or c < 0:
            return 0
        
        res = 1
        res += a/N*dp(a-1, b, c)
        res += b/N*dp(a+1, b-1, c)
        res += c/N*dp(a, b+1, c-1)
        res /= 1-(N-a-b-c)/N
        
        memo[(a, b, c)] = res
        return res
    
    a, b, c = count[1], count[2], count[3]
    ans = dp(a, b, c)
    
    print(ans)
        
        
    
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

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


N = int(input())
memo = [[[-1]*(N+1) for _ in range(N+1)] for _ in range(N+1)]

def dp(a, b, c):
    if a == b == c == 0: return 0
    if memo[a][b][c] != -1:
        return memo[a][b][c]
    
    res = N
    if a > 0: res += a*dp(a-1, b, c)
    if b > 0: res += b*dp(a+1, b-1, c)
    if c > 0: res += c*dp(a, b+1, c-1)
    res /= a+b+c
    
    memo[a][b][c] = res
    return res

def main():
    A = list(map(int, input().split()))
    
    count = Counter(A)
    for i in range(1, 4):
        if not i in count: count[i] = 0
    x, y, z = count[1], count[2], count[3]

    
    ans = dp(x, y, z)
    
    print(ans)
        

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

N = int(input())
A = list(map(int,input().split()))
ans = 0
while all( a%2 == 0 for a in A ):
        a = [ i/2 for i in A ]
        ans += 1
print(ans)


### FIXED CODE ###

import numpy as np
import sys

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

cnt = 1

if np.any(a%2==1):
    print(0)
    sys.exit()

while True:
    a2 = a % 2**cnt
    if np.all(a2==0):
        cnt += 1
        continue
    else:
        print(cnt-1)
        break
### BUGGY CODE ###

from bisect import bisect_left#(sorted_list,x)で昇順ソート位置

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

l.sort()
ans = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    s = l[i]+l[j]
    ans += bisect_left(l[j+1:],s)
print(ans)

### FIXED CODE ###

from bisect import bisect_left#(sorted_list,x)で昇順ソート位置

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

l.sort()
ans = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    s = l[i]+l[j]
    ans += bisect_left(l,s,j+1)-j-1
print(ans)
### BUGGY CODE ###

import sys
import numpy as np
import copy
from itertools import accumulate
input=sys.stdin.readline
def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    ans = copy.deepcopy(A)
    for _ in range(K):
        cumsum = [0]*N
        for i,a in enumerate(ans):
            l = max(0,i-a)
            r = min(N-1,i+a)
            cumsum[l] += 1
            if r+1 < N:
                cumsum[r+1] -= 1
        ans = list(accumulate(cumsum))
        if ans[0] == N:
            break
    print(*ans)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import copy
from itertools import accumulate
input=sys.stdin.readline
def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    ans = copy.deepcopy(A)
    for _ in range(K):
        cumsum = [0]*N
        for i,a in enumerate(ans):
            l = max(0,i-a)
            r = min(N-1,i+a)
            cumsum[l] += 1
            if r+1 < N:
                cumsum[r+1] -= 1
        ans = list(accumulate(cumsum))
        if ans[0] == N:
            break
    print(*ans)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

i=int(input())
nest=1
a=0
p=i
while True:
  nest+=1
  p=p//2
  if p==1:
    break
a=(2**nest)-1
print(a)


### FIXED CODE ###

i=int(input())
nest=1
a=0
p=i
if p==1:
  print(1)
else:
  for k in range(50):
    nest+=1
    p=p//2
    if p==1:
      break
  a=(2**nest)-1
  print(a)
### BUGGY CODE ###

h,w = map(int,input().split())
l = [input() for x in range(h)]
lis = [[x for x in S]for S in l]
ans=0
bk_lis=[]
def lis_Serch(lis):
    global bk_lis
    for x in range(h):
        for y in range(w):
            if lis[x][y] == '#':
                bk_lis.append([x,y])

def m_bfs(lis):
    global bk_lis
    ans = 0
    while True:
        for x in bk_lis:
            chc(x)
        if len(bk_lis) == h*w:
            return ans
        bk_lis=[]
        lis_Serch(lis)
        ans+=1

            
def chc(fili):
    vy = [0,0,1,-1]
    vx = [1,-1,0,0]
    for vx,vy in zip(vx,vy):
        now=[fili[0]+vy,fili[1]+vx]
        if 0<=now[0]<h and 0<=now[1]<w:
            lis[now[0]][now[1]] = '#'
lis_Serch(lis)
print(m_bfs(lis))


### FIXED CODE ###

#bfs 
#0#000  1#100 1#120 1#123
#00000  01010 21212 21212
#000#0  001#1 021#1 321#1
#000#0  001#1 021#1 321#1

from collections import deque

h,w = map(int,input().split())
lis = [input() for x in range(h)]

vy = [0,0,1,-1]
vx = [1,-1,0,0]

reached = [[-1]*w for x in range(h)]
def bfs(bk_lis):
    q = deque()
    for i in bk_lis:
        q.append(i)
        reached[i[0]][i[1]]=0
    while q:
        y,x = q.popleft()
        for dy,dx in zip(vy,vx):
            ny,nx = y+dy,x+dx
#                print(ny,nx)
            if not(0<=ny<h and 0<=nx<w):
                continue#範囲の確認
            if  reached[ny][nx]==-1 or reached[ny][nx]>reached[y][x]+1:
                reached[ny][nx] = reached[y][x]+1
                q.append([ny,nx])
#        print(reached)
bk_lis = []
ans=0
for y in range(h):
    for x in range(w):
        if lis[y][x] == '#':
            bk_lis.append([y,x])
#print(bk_lis)
bfs(bk_lis)
for y in reached:
    ans = max(max(y),ans)
#for x in reached:
#    print(x)
print(ans)
### BUGGY CODE ###

def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)

def lcm(a, b):
    return a * b // gcd(a, b)

mod = int(1e9 + 7)

while True:
    try:
        n = int(input())
        a = list(map(int, input().split()))
    except:
        break

    l = a[0]
    for i in range(1, n):
        l = lcm(l, a[i])

    ans = 0
    for i in range(n):
        ans = (ans + l // a[i]) % mod
    print(ans)

### FIXED CODE ###

mod = int(1e9 + 7)

def inv(x):
    return pow(x, mod - 2, mod)

def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)

def lcm(a, b):
    return a * b // gcd(a, b)

def mod_lcm(a, b):
    return a * b % mod * inv(gcd(a, b)) % mod


while True:
    try:
        n = int(input())
        a = list(map(int, input().split()))
    except:
        break

    l = a[0]
    for i in range(1, n):
        l = lcm(l, a[i])
    l %= mod

    ans = 0
    for i in range(n):
        ans = (ans + l * inv(a[i])) % mod
    print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 0
m0 = 10**9+7
for i in range(0,N-1):
    for j in range(i+1,N):
        ans = (ans + A[i]*A[j]) % m0
print(ans)

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int,input().split()))
    ans = 0
    m0 = 10**9+7
    Ar = [0]*N
    sum0 = 0
    for i in reversed(range(N)):
        sum0 = (sum0 + A[i]) % m0
        Ar[i] = sum0

    for i in range(N-1):
        ans = (ans + A[i] * Ar[i+1]) % m0
    print(ans)

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

# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(H) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

d=defaultdict(lambda: float("inf")) #スタート地点から各マスまでの距離

q=deque()
q.append((CH,CW))
d[(CH,CW)]=0

while q:
    fro_h, fro_w=q.popleft()
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and d[(fro_h, fro_w)]<d[(to_h, to_w)]:
            d[(to_h, to_w)]=d[(fro_h, fro_w)]
            q.appendleft((to_h, to_w))

    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and d[(fro_h, fro_w)]+1<d[(to_h, to_w)]:
            d[(to_h, to_w)]=d[(fro_h, fro_w)]+1
            q.append((to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(H) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

d=defaultdict(lambda: float("inf")) #スタート地点から各マスまでの距離

q=deque()
q.append((0,CH,CW))
d[(CH,CW)]=0

while q:
    kyori, fro_h, fro_w=q.popleft()
    if d[(fro_h, fro_w)]<kyori: continue
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            if kyori < d[(to_h, to_w)]:
                d[(to_h, to_w)]=kyori
                q.appendleft((kyori, to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            if kyori+1 < d[(to_h, to_w)]:
                d[(to_h, to_w)]=kyori+1
                q.append((kyori+1, to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]
### BUGGY CODE ###

N = int(input())
num = 10**12
for i in range(1, N+1):
  if N % i == 0:
    num = min(num, i + N // i - 2)
print(num)
  

### FIXED CODE ###

import math
N = int(input())
num = 10**12
for i in range(1, math.floor(math.sqrt(N)+2)):
  if N % i == 0:
    num = min(num, i + N // i - 2)
print(num)
### BUGGY CODE ###

from itertools import combinations

def resolve():
    N = int(input())
    S = str(input())
    ans = []
    for i in range(N):
        for j in range(N):
            for k in range(N):
                if i < j and j < k:
                    ans.append(S[i] + S[j] + S[k])

    print(len(set(ans)))
    return

resolve()

### FIXED CODE ###

def resolve():
    N = int(input())
    S = str(input())
    cnt = 0

    for i in range(1000):
        c = [int(i / 100), int(i / 10) % 10, int(i % 10)]
        f = 0

        for j in range(N):
            if S[j] == ('0' + str(c[f])) or S[j] == str(c[f]):
                f += 1
            if f == 3:
                break

        if f == 3:
            cnt += 1
    print(cnt)
    return

resolve()
### BUGGY CODE ###

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
INF = 1000000007

dp = [0] * (N + 1)
dp[0] = 1
if 1 not in a:
	dp[1] = 1
else:
	dp[1] = 0
for i in range(2, N + 1):
	if i in a:
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= INF

print(dp[N])


### FIXED CODE ###

from itertools import product

INF = 1000000007

def mat2_mul(X, Y):
	z = [[0, 0], [0, 0]]
	for (i, j, k) in product(range(2), range(2), range(2)):
		z[i][j] += X[i][k] * Y[k][j]
	return z

def mat2_pow(X, n):
	if n == 0:
		return [[1, 0], [0, 1]]
	elif n % 2:
		return mat2_mul(X, mat2_pow(X, n - 1))
	else:
		half_pow = mat2_pow(X, n / 2)
		return mat2_mul(half_pow, half_pow)

def fib(n):
	if n == 0:
		return 0
	else:
		f = [[0, 1], [1, 1]]
	return mat2_pow(f, n - 1)[1][1]


N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
ans, start = 1, 0
tmp = []

for i in range(len(a)):
	if a[i] - a[i - 1] == 1:
		print(0)
		exit()

for k in a:
	tmp.append(fib(k - start) % INF)
	start = k + 1

for j in tmp:
	ans *= j
	ans %= INF

ans *= fib(N - start + 1)
print(ans % INF)
### BUGGY CODE ###

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


for i in a:
  ans *= i
  if(0 in a):
    ans=0
    break
  if(ans > 10**18):
    ans = -1
    break

print(ans)

### FIXED CODE ###

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


if(0 in a):
    ans=0
else:
  for i in a:
    ans *= i
    if(ans > 10**18):
      ans = -1
      break

print(ans)