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

N = int(input())

ans = 1

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

print(ans%(10**9+7))


### FIXED CODE ###

N = int(input())

ans = 1

for i in range(1,N+1):
    ans *= i
    ans %= (10**9+7)

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

n,k,q = map(int,input().split())
a = [int(input()) for i in range(q)]
ip = [k for i in range(n)]
for i in  range(q):
  ip = [i-1 for i in ip]
  ip[a[i]-1] += 1
for j in range(n):
  print('Yes' if ip[j] > 0 else 'No')

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,k,q = map(int,input().split())
a = [int(input()) for i in range(q)]
ip = [k-q]*(n+1)
for j in a:
  ip[j] += 1
ans = '\n'.join('Yes' if p > 0 else 'No' for p in ip[1:])
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
for i in range(1,N+1):
  print(A.count(i))


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = [0]*N
for i in A:
  ans[i-1] += 1
for i in range(N):
  print(ans[i])
### BUGGY CODE ###

R,G,B,n=map(int,input().split())
sum_rg=[]
for r in range(n+1):
	for g in range(n+1):
		Rr,Gg=R*r,G*g
		if Rr+Gg>n:
			break
		else:
			sum_rg.append(n-Rr-Gg)
count=0
for i in sum_rg:
	if not i%B:
		count+=1
print(count)

### FIXED CODE ###

R,G,B,n=map(int,input().split())
sum_rg=[0 for i in range(n+1)]
for r in range(n+1):
	for g in range(n+1):
		tmp=R*r+G*g
		if tmp>n:
			break
		else:
			#print(f'Bb:{n-tmp}')
			sum_rg[n-tmp]+=1
#print(sum_rg)
count=0
for i in range(n//B+1):
	count+=sum_rg[i*B]
print(count)
### BUGGY CODE ###

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

P = [1e9]*N
P[0] = 0

for i in range(1,N):
  for j in range(1,min(K+1,i+1)):
    P[i] = min(P[i], abs(A[i]-A[i-j])+P[i-j])
  
print(P[N-1])


### FIXED CODE ###

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

P = [1e9]*N
P[0] = 0

for i in range(1,N):
  for j in range(1,min(K+1,i+1)):
    P[i] = min(P[i], abs(A[i]-A[i-j])+P[i-j])
  
print(P[N-1])
### BUGGY CODE ###

n = int(input())
A = tuple(map(lambda x:int(x)-1, input().split()))

paired = [0] * n
c = 0
for i in range(n-1):
    if paired[i]:
        continue

    for j in range(i+1, n):
        if A[i] == j and A[j] == i:
            paired[j] = 1
            paired[i] = 1
            c += 1
            break
print(c)


### FIXED CODE ###

n = int(input())
A = tuple(map(lambda x:int(x)-1, input().split()))

paired = [0] * n
c = 0
for i in range(n-1):
    if paired[i]:
        continue

    if A[A[i]] == i:
        c += 1
        paired[A[i]] = 1

print(c)
### BUGGY CODE ###

N, K = input().split()
N = int(N)
K = int(K)

array = input().split()
for i in range(len(array)):
    array[i] = int(array[i])

now = 1

history = []
start_number = -1

for i in range(K):
    history.append(now)
    now = array[now - 1]
    if(now in history):
        start_number = now
        break

if not(start_number == -1):
    start_ind = history.index(start_number)
    length = len(history) - start_ind
    mod = (K - start_ind) % length
    now = history[start_ind + mod]

print(now)


### FIXED CODE ###

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

array = input().split()
for i in range(len(array)):
    array[i] = int(array[i])

now = 1

history = []
sethistory = set()
start_number = -1

for i in range(K):
    history.append(now)
    sethistory.add(now)
    now = array[now - 1]
    if(now in sethistory):
        start_number = now
        break

if not(start_number == -1):
    start_ind = history.index(start_number)
    length = len(history) - start_ind
    mod = (K - start_ind) % length
    now = history[start_ind + mod]

print(now)
### BUGGY CODE ###

n=int(input())
li=list(map(int,input().split()))
d={}
dif={-1}
ans={}
for i in range(n):
    if li[i] not in dif:
        dif|={li[i]}
    if d.get(li[i])!=None:
        d[li[i]]+=1
    else:
        d[li[i]]=1
dif.remove(-1)
for i in dif:
    g=0
    for j in dif:
        if i!=j:
            g+=d[j]*(d[j]-1)//2
        else:
            g+=(d[j]-2)*(d[j]-1)//2
    ans[i]=g
for i in li:
    print(ans[i])

### FIXED CODE ###

n=int(input())
li=list(map(int,input().split()))
d={}
dif={-1}
ans={}
for i in range(n):
    if li[i] not in dif:
        dif|={li[i]}
    if d.get(li[i])!=None:
        d[li[i]]+=1
    else:
        d[li[i]]=1
dif.remove(-1)
g=0
for i in dif:
    g+=d[i]*(d[i]-1)//2
for i in dif:
    ans[i]=g-(d[i]-1)*d[i]//2+(d[i]-2)*(d[i]-1)//2
for i in li:
    print(ans[i])
### BUGGY CODE ###

from pprint import pprint
import queue

def solve(n, a, b):
        
    state = queue.Queue()
    state.put((0, b[:]))
    while not state.empty():
        count, b_tmp = state.get()
        # print("next:" + str(count))
        # pprint(b_tmp)
        for i, b_i in enumerate(b_tmp):
            i_a = (i - 1 + n) % n
            i_c = (i + 1) % n
            b_cand = b_i - b_tmp[i_a] - b_tmp[i_c]
            if b_cand >= a[i]:
                b_next = b_tmp[:]
                b_next[i] = b_cand
                if b_next == a:
                    return count + 1
                # print(count + 1)
                state.put((count + 1, b_next))
    
    return -1


if __name__ == '__main__':

    n = int(input().strip())
    a = list(map(int, input().strip().split(" ")))
    b = list(map(int, input().strip().split(" ")))
    print(solve(n, a, b))

### FIXED CODE ###

from pprint import pprint
import heapq

def solve(n, a, b):
    b_pq = []
    b_rev = {}
    delete = []
    for i, b_i in enumerate(b):
        if b_i == a[i]:
            continue
        heapq.heappush(b_pq, (-1 * b_i, i))

    count = 0
    while b_pq:
        tmp = heapq.heappop(b_pq)
        # pprint(tmp)
        b_i = tmp[0] * -1
        i_b = tmp[1]
        # print(i_b, b_i)
        i_a = (i_b - 1 + n) % n
        i_c = (i_b + 1) % n
        b_cand = b_i
        if b_cand - b[i_a] - b[i_c] < a[i_b]:
            continue

        #while b_cand - b[i_a] - b[i_c] >= a[i_b]:
        #    b_cand = b_cand - b[i_a] - b[i_c]
        #    count += 1
        tmp_count =  (b_cand - a[i_b]) // (b[i_a] + b[i_c])
        b_cand -= (b[i_a] + b[i_c]) * tmp_count
        count += tmp_count

        b[i_b] = b_cand
        if b_cand != a[i_b]:
            heapq.heappush(b_pq, (-1 * b_cand, i_b))
        # print("count: ", count)
        # pprint(b)
         

        if b_cand == a[i_b] and b == a:
            return count
    
    return -1


if __name__ == '__main__':

    n = int(input().strip())
    a = list(map(int, input().strip().split(" ")))
    b = list(map(int, input().strip().split(" ")))
    print(solve(n, a, b))
### BUGGY CODE ###

N,K = map(int,input().split())
S = [tuple(map(int,input().split())) for _ in range(K)]
MOD=998244353
dp=[0]*N
dp[0]=1
for i in range(N-1):
    x = dp[i]
    dp[0]=0
    for k in range(K):
        l,r = S[k]
        if i+l < N:
            dp[i+l]+=x
            dp[i+l]%MOD
        if i+r+1 < N:
            dp[i+r+1]-=x
            dp[i+r+1]%MOD
    dp[i+1]+=dp[i]
    dp[i+1]%MOD
print(dp[-1]%MOD)

### FIXED CODE ###

N,K = map(int,input().split())
S = [tuple(map(int,input().split())) for _ in range(K)]
MOD=998244353
dp=[0]*N
dp[0]=1
for i in range(N-1):
    x = dp[i]
    dp[0]=0
    for k in range(K):
        l,r = S[k]
        if i+l < N:
            dp[i+l]+=x
            dp[i+l]%=MOD
        if i+r+1 < N:
            dp[i+r+1]-=x
            dp[i+r+1]%=MOD
    dp[i+1]+=dp[i]
    dp[i+1]%=MOD
print(dp[-1]%MOD)
### BUGGY CODE ###

n = int(input())
s_list = [sorted(list(input())) for nesya in range(n)]
c = 0
for s in s_list:
  for a in s_list:
    if s == a:
      c += 1
print((c-n)//2)

### FIXED CODE ###

n = int(input())
sl = [input() for nesya in range(n)]
sm = []
for s in sl:
  t = list(s)
  t.sort()
  sm.append(''.join(t))
d = dict()
for m in sm:
  if m in d:
    d[m] += 1
  else:
    d[m] = 1
c = 0
for v in d.values():
  c += v*(v-1)//2
print(c)
### BUGGY CODE ###

#!/usr/bin/env python3

from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


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

s = [1] * (N+1)
for i in range(N):
    s[i+1] = s[i] * A[i]
# pprint(s)

prev = s[K]
for i in range(K+1, N+1):
    # print(f'i = {i}')
    # print(f's[i] = {s[i]}, s[i-K] = {s[i-K]}')
    score = s[i] // s[i-K]
    # print(f'score = {score}')
    if prev < score:
        print('Yes')
    else:
        print('No')
    prev = score


### FIXED CODE ###

#!/usr/bin/env python3

from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


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

s = [0] * (N+1)
for i in range(N):
    s[i+1] = s[i] + A[i]
# pprint(s)

prev = s[K]
for i in range(K+1, N+1):
    # print(f'i = {i}')
    # print(f's[i] = {s[i]}, s[i-K] = {s[i-K]}')
    score = s[i] - s[i-K]
    # print(f'score = {score}')
    if prev < score:
        print('Yes')
    else:
        print('No')
    prev = score
### BUGGY CODE ###

n, *a = map(int, open(0).read().split())
b = []
for i in a:
  b.append(int(i))
  b.reverse()

for i in b:
  print(i, end=" ")

### FIXED CODE ###

n = int(input())
a = input().split()
print(' '.join(a[::-2] + a[n%2::2]))
### BUGGY CODE ###

import math
from functools import reduce

K = int(input())

# K = 2


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


ans = 0
for a in range(1, K + 1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            ans += gcd(a, b, c)

print(ans)


### FIXED CODE ###

import math
from functools import reduce
import itertools

K = int(input())

# K = 2


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


ans = 0
for i in range(1, K + 1):
    # i = 1
    ans += gcd(i, i, i)

    for j in range(i + 1, K + 1):
        ans += gcd(i, i, j) * 3

    for j, k in itertools.product(range(i + 1, K + 1), range(i + 1, K + 1)):
        ans += gcd(i, j, k) * 3

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

N,M = map(int,input().split(" "))
isbr = []
for i in range(M):
  isbr.append(list(map(int,input().split(" "))))
isbr = list(sorted(isbr,key = lambda x: x[1]))
rem = []
i = 0
while i < M:
  a = isbr[i][0]
  b = isbr[i][1]
  flag = 0
  while a <= b:
    if b in rem:
      flag = 1
      break
    else:
      b-=1
  if flag == 0:
    rem.append(isbr[i][1]-1)
  i+=1
print(len(rem))

### FIXED CODE ###

#D問題
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
AB=sorted(AB, key=lambda x: x[1])
bridges=[]
for i in range(M):
    if len(bridges) == 0:
        bridges.append(AB[i][1]-1)
    elif max(bridges)>=AB[i][0]:
        pass
    else:
        bridges.append(AB[i][1]-1)
print(len(bridges))
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
all=0
for i in range(N):
    all += a.count(i+1)*(a.count(i+1)-1)//2
for i in range(N):
    print(all-(a.count(a[i])-1))

### FIXED CODE ###

from collections import Counter
N = int(input())
a = list(map(int, input().split()))
c = Counter(a)
#print(c.items())
all=0
for i,j in c.items():
    all += j*(j-1)//2
for i in range(N):
    print(all-(c[a[i]]-1))
### BUGGY CODE ###

N,M=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ls.sort(reverse=True)
#print(ls)
for i in range(M):
  x=ls[0]>>1
  for j in range(N-1):
    if ls[j+1]>x:
      ls[j]=ls[j+1]
    else:
      ls[j]=x
      break
#    print(ls,j,x)
  else:
    ls[N-1]=x
#  print(ls)
print(sum(ls))


### FIXED CODE ###

import math
N,M=[int(s) for s in input().split()]
ls=[int(s) for s in input().split()]
ls.sort(reverse=True)
x=ls[0]
L=int(math.log2(x))
#2**L より大きいものをわける
def cut(lst,exp):
    for ii in range(len(lst)):
        if ii+1==len(lst):
            break
        if lst[ii+1]<exp:
           break
    return ii
m=M #残り回数
b=-1
ls3=[]
while True:
    if m==0:
        break
    a=b+1
    b=cut(ls,2**L)
    ls2=ls[a:b+1]
    ls3=ls3+ls2
    ls3.sort(reverse=True)
    for j in range(len(ls3)):
        ls3[j]=ls3[j]//2
        m-=1
        if m==0:
            break
    L-=1
#    print(ls3,m,b)
#print(ls3,ls[b+1:])
s=sum(ls3)+sum(ls[b+1:])
print(s)
### BUGGY CODE ###

a, b, k = map(int, input().split())
count = 0
for i in range(a, b+1):
  count += 1
  if count <= k or count > b-a-k+1:
    print(i)

### FIXED CODE ###

a, b, k = map(int, input().split())
ans = []
for i in range(a, a+k):
  if i >= a and i <= b:
    ans.append(i)

for i in range(b-k+1, b+1):
  if not i in ans and i >= a and i <= b:
    ans.append(i)

for i in ans:
  print(i)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
d={1:0,2:0,3:0}
for a in A:
    d[a]+=1
dp={(0,0,0):0}
import sys
sys.setrecursionlimit(10**9)
def f(i,j,k):
    if (i,j,k) in dp:
        return dp[(i,j,k)]
    dp[(i,j,k)]=N
    if i>0:
        dp[(i,j,k)]+=f(i-1,j+1,k)*i
    if j>0:
        dp[(i,j,k)]+=f(i,j-1,k+1)*j
    if k>0:
        dp[(i,j,k)]+=f(i,j,k-1)*k
    dp[(i,j,k)]/=i+j+k
    return dp[(i,j,k)]
print(f(d[3],d[2],d[1]))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
d={1:0,2:0,3:0}
for a in A:
    d[a]+=1
dp=[[[0]*(N+1) for j in range(d[2]+d[3]+1)] for i in range(d[3]+1)]
for i in range(d[3]+1):
    for j in range(d[2]+d[3]-i+1):
        for k in range(N-i-j+1):
            if i+j+k==0:continue
            dp[i][j][k]=N
            if i>0:
                dp[i][j][k]+=dp[i-1][j+1][k]*i
            if j>0:
                dp[i][j][k]+=dp[i][j-1][k+1]*j
            if k>0:
                dp[i][j][k]+=dp[i][j][k-1]*k
            dp[i][j][k]/=i+j+k
print(dp[d[3]][d[2]][d[1]])
### BUGGY CODE ###

import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    al = [0]*(max(a)+1)
    for i in a:
        na = i
        if al[i] > 0:
            al[na] += 1
            continue
        while na <= max(a):
            al[na] += 1
            na += i

    ans = 0
    for i in a:
        if al[i] == 1:
            ans += 1
    print(ans)

    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n = int(ipt())
    a = [int(i) for i in ipt().split()]
    a.sort()
    ma = max(a)+1
    al = [True]*ma
    ans = 0
    pi = 0
    for i in a:
        if al[i]:
            ans += 1
            for j in range(i,ma,i):
                al[j] = False
            pi = i
        else:
            if i == pi:
                ans -= 1
                pi = 0

    print(ans)

    return

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

def main():
    import sys
    input=sys.stdin.readline
    n = int(input())
    hp = sorted([tuple(map(int, input().split()))
                 for _ in [0]*n], key=lambda x: sum(x))
    dp = [10**10]*(n+1)
    dp[0] = 0
    for c, (h, p) in enumerate(hp):
        for k in range(c, -1, -1):
            if dp[k] <= h:
                dp[k+1] = min(dp[k+1], dp[k]+p)
    for i in range(n, -1, -1):
        if dp[i] != 10**10:
            print(i)
            break


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input=sys.stdin.readline
    n=int(input())
    hp=sorted([list(map(int,input().split())) for _ in [0]*n],key=lambda x:sum(x))
    dp=[10**10]*(n+1)
    dp[0]=0
    for c,[h,p] in enumerate(hp):
        for k in range(c,-1,-1):
            if dp[k]<=h:
                dp[k+1]=min(dp[k+1],dp[k]+p)
    for i in range(n,-1,-1):
        if dp[i]!=10**10:
            print(i)
            break
if __name__=='__main__':
    main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
import math
mod = 10**9 + 7
def I(): return int(input())
def II(): return map(int, input().split())
def L(): return list(map(int, input().split()))
def TWO(M):
  L=[0]*M
  R=[0]*M
  for i in range(M):
    L[i],R[i] = II()
  return L, R

N = I()
A = [0]*N
for i in range(N):
  A[i] = I()

counter = 0
all_counter = 0
not_used = [i for i in range(N)]
while 1:
  temp = -1
  for i in not_used[:]:
    if temp<A[i]:
      temp = A[i]
      all_counter += 1
      not_used.remove(i)
  counter += 1
  if all_counter==N:
    break
  
print(counter)

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

from bisect import bisect_left

N = I()
A = [0]*N
for i in range(N):
    A[i] = I()

val = [-1]*N
for i in range(N):
    temp = bisect_left(val,A[i])
    val[temp-1] = A[i]

ans = 0
for i in range(N):
    if val[i]!=-1:
        ans += 1

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

S = list(input())
Q = int(input())

for i in range(Q):
    a = list(map(str, input().split()))
    if a[0] == '1':
        S = S[::-1]
    elif a[0] == '2':
        if a[1] == '1':
            S.insert(0, a[2])
        else:
            S.append(a[2])

print(''.join(S))

### FIXED CODE ###

from collections import deque
S = deque(list(input()))
Q = int(input())

count = 0
for i in range(Q):
    a = list(map(str, input().split()))
    if a[0] == '1':
        count += 1
    elif a[0] == '2':
        if count % 2 == 0 and a[1] == '1':
            S.appendleft(a[2])
        elif a[1] == '1':
            S.append(a[2])
        elif count % 2 == 0:
            S.append(a[2])
        else:
            S.appendleft(a[2])


if count % 2 == 0:
    print(''.join(S))
else:
    S.reverse()
    print(''.join(S))
### BUGGY CODE ###

mod = 998244353

def bi(x):
    o = []
    while x != 0:
        o.append(x%2)
        x //= 2
    return o

def modpow(m,n):
    o = 0
    leo = 0
    if n == 1000000005:
        o = [1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1]
        leo = 30
    else:
        o = bi(n)
        leo = len(o)
    p = [m] + [0] * (leo - 1)
    for i in range(1,leo):
        a = p[i-1]
        a *= a
        a %= mod
        p[i] = a
    b = 1
    for i in range(leo):
        if o[i]:
            b *= p[i]
            b %= mod
    return b

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

C = [1]*(K+1)
for i in range(1,K+1):
    C[i] = C[i-1] * (N-i) // i

M1 = [1]*N
for i in range(1,N):
    M1[i] = M1[i-1] * (M-1)
    M1[i] %= mod

ans = 0
for k in range(0,K+1):
    ans += C[k] * M * M1[N-k-1]
    ans %= mod

print(ans)


### FIXED CODE ###

def a():
    mod = 998244353

    def bi(x):
        o = []
        while x != 0:
            o.append(x%2)
            x //= 2
        return o

    o = bi(mod - 2)
    leo = len(o)
    p = [0] * leo

    def modinv(m):
        p[0] = m
        for i in range(1,leo):
            a = p[i-1]
            a *= a
            a %= mod
            p[i] = a
        b = 1
        for i in range(leo):
            if o[i]:
                b *= p[i]
                b %= mod
        return b

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

    C = [1]*(K+1)
    for i in range(1,K+1):
        C[i] = (C[i-1] * (N-i) * modinv(i))%mod

    M1 = [1]*N
    for i in range(1,N):
        M1[i] = M1[i-1] * (M-1)
        M1[i] %= mod

    ans = 0
    for k in range(0,K+1):
        ans += C[k] * M * M1[N-k-1]
        ans %= mod

    print(ans)

a()
### BUGGY CODE ###

dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

dst = [[-1]*W for _ in range(H)]

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if dst[h][w] == -1 or d < dst[h][w]: dst[h][w] = d
    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh or nw < 0 or W <= nw: continue
        if S[nh][nw] == '#' or 0 <= dst[nh][nw]: continue
        dq.appendleft((nh, nw, d))
    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh or nw < 0 or W <= nw: continue
        if S[nh][nw] == '#' or 0 <= dst[nh][nw]: continue
        dq.append((nh, nw, d+1))

print(dst[eh][ew])


### FIXED CODE ###

dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

dst = [[-1]*W for _ in range(H)]

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
    else:
        continue
    for i in range(4): dq.appendleft((h + dhw[i][0], w + dhw[i][1], d))
    for i in range(4, 24): dq.append((h + dhw[i][0], w + dhw[i][1], d+1))

print(dst[eh][ew])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
B = sorted(A)
B.append(0)
p = B[0]
y = dict()
u = 0
for k in range(N+1):
    q = B[k]
    if p != q:
        y[p] = u
        u=0
    u += 1
    p = q
for j in range(N):
    g = 0
    x = A[j]
    y[x] -= 1
    va = list(y.values())
    for l in va:
        g += l*(l-1)//2
    print(g)
    y[x] += 1

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = sorted(A)
B.append(0)
p = B[0]
y = dict()
u = 0
for k in range(N+1):
    q = B[k]
    if p != q:
        y[p] = u
        u = 0
    u += 1
    p = q
All = 0
for l in y.values():
    All +=l*(l-1)//2
for j in range(N):
    x = A[j]
    print(All+(y[x]-1)*(y[x]-2)//2-y[x]*(y[x]-1)//2)
### BUGGY CODE ###

s = input()
k = int(input())


list_pair = []
i = 0
while i <= len(s):
    for j in range(i+1,len(s)+1):
        list_pair.append(s[i:j])
    i = i + 1

list_pair = list(set(list_pair))

list_pair.sort()
print(list_pair[k-1])


### FIXED CODE ###

s = input()
k = int(input())


list_pair = []
i = 0
while i <= len(s):
    for j in range(1,min(len(s)-i+1,k+1)):
#        print(j,s[i:i+j])
        list_pair.append(s[i:i+j])
    i = i + 1

list_pair = list(set(list_pair))

list_pair.sort()
print(list_pair[k-1])
### BUGGY CODE ###

n = int(input())
array = [int(x) for x in input().split()]

for i in range(n):
    tmp = list(array)
    tmp.remove(tmp[i])
    res = 0
    ichi = 0
    for j in tmp:
        res += abs(ichi-j)
        ichi = j

    print(res+abs(ichi))


### FIXED CODE ###

n = int(input())
array = [int(x) for x in input().split()]

tmp_res = 0
tmp_ici = 0
tmp_array = []
for i in array:
    tmp_array.append(abs(tmp_ici-i))
    tmp_ici = i
tmp_array.append(abs(tmp_ici-0))
tmp_sum = sum(tmp_array)

array = [0] + array + [0]
for i in range(n):
    c = array[i]
    cc = array[i+2]
    a = sum(tmp_array[i:i+2])
    print(tmp_sum-a+abs(c-cc))