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

n,k=map(int,input().split())
A=[int(i) for i in input().split()]
AA=[0]*n
B=[2*n+1]*(2*(10**5)+1)
for i in reversed(range(n)):
  B[A[i]]=n+i+1
for i in reversed(range(n)):
  AA[i]=B[A[i]]-(i+1)
  B[A[i]]=i+1
count,index,inc=0,0,0
while count<n*k:
  index=(index+inc)%n
  inc=AA[index]+1
  count+=inc  
  if count%n==0:
    count*=(n*k)//count

count-=inc
d=n*k-count
Ans1=A+A
Ans1=Ans1[index:index+d]
Ans2=AA+AA
Ans2=Ans2[index:index+d]
Ans=[]
i=0
while i<d:
  if i+Ans2[i]>=d:
    Ans.append(Ans1[i])
    i+=1
  else:
    i+=Ans2[i]+1
print(*Ans)


### FIXED CODE ###

n,k=map(int,input().split())
A=[int(i) for i in input().split()]
AA=[0]*n
B=[2*n+1]*(2*(10**5)+1)
for i in reversed(range(n)):
  B[A[i]]=n+i+1
for i in reversed(range(n)):
  AA[i]=B[A[i]]-(i+1)
  B[A[i]]=i+1
count,index,inc=0,0,0
Chk=[0]*n
flag=False
while count<n*k:

  inc=AA[index]+1
  count+=inc  
  index=(index+inc)%n
  if Chk[index]!=0 or index==0:
    if flag==False:
      dd=count-Chk[index]
      count+=(((n*k)-count)//dd)*dd
      flag=True
  Chk[index]=count

count-=inc
index=(index+n-inc)%n

d=n*k-count
Ans1=A+A
Ans2=AA+AA
Ans=[]
i=index
while i<d+index:
  if i+Ans2[i]>=d+index:
    Ans.append(Ans1[i])
    i+=1
  else:
    i+=Ans2[i]+1
print(*Ans)
### BUGGY CODE ###

#input
N, P = map(int, input().split())
S = list(map(int, input()))

# process
ans = 0
if P == 2 or P == 5:
    # 1桁目がPで割り切れる数をカウント
    for i in range(N):
        if S[i] % P == 0:
            ans += i+1

else:
    cnt = [0]*P # S[i:N]%Pの結果をカウント
    num = 0
    for i in range(N):
        num += S[N-i-1]*10**i
        cnt[num%P] += 1

    ans += cnt[0]
    for c in cnt:
        ans += c*(c-1)//2 # c=0,1のときは0加算

# output
print(ans)


### FIXED CODE ###

#input
N, P = map(int, input().split())
S = input()

# process
ans = 0
if P == 2 or P == 5:
    # 1桁目がPで割り切れる数をカウント
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += i+1

else:
    cnt = [0]*P # S[i:N]%Pの結果をカウント
    num = 0
    tenPow = 1
    for i in reversed(range(N)):
        num = (num + int(S[i])*tenPow)%P
        tenPow = tenPow*10%P
        cnt[num] += 1

    ans += cnt[0]
    for c in cnt:
        ans += c*(c-1)//2 # c=0,1のときは0加算

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

import heapq

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

uvab = [list(map(int, input().split())) for _ in range(M)]
cd = [list(map(int, input().split())) for _ in range(N)]

for i in range(M):
    uvab[i][0] -= 1
    uvab[i][1] -= 1

railways = [[] for _ in range(N)]
max_a = 0
for u, v, a, b in uvab:
    railways[u].append((v, a, b))
    railways[v].append((u, a, b))
    max_a = max(max_a, a)
del uvab

max_silver = max_a * (N - 1)

d = [-1] * N
d[0] = 0
sum_reached = 1
reached = [False] * N
reached[0] = True

Q = [(0, S, 0)]  # (time, silver, station)
visited = set(Q)

while True:
    t, silver, s = Q[0]

    if not reached[s]:
        d[s] = t
        reached[s] = True
        sum_reached += 1
        if sum_reached == N:
            break

    new_state = (t + cd[s][1], silver + cd[s][0], s)
    if new_state in visited:
        heapq.heappop(Q)
    else:
        heapq.heapreplace(Q, new_state)
        visited.add(new_state)

    for dist, a, b in railways[s]:
        if silver >= a:
            new_state = (t + b, silver - a, dist)
            if new_state not in visited:
                heapq.heappush(Q, new_state)
                visited.add(new_state)

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

### FIXED CODE ###

import heapq

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

uvab = [list(map(int, input().split())) for _ in range(M)]
cd = [list(map(int, input().split())) for _ in range(N)]

for i in range(M):
    uvab[i][0] -= 1
    uvab[i][1] -= 1

railways = [[] for _ in range(N)]
max_a = 0
for u, v, a, b in uvab:
    railways[u].append((v, a, b))
    railways[v].append((u, a, b))
    max_a = max(max_a, a)
del uvab

max_silver = max_a * (N - 1)

ans = [-1] * N
d = dict()
d[(S, 0)] = 0  # silver, station
Q = [(0, S, 0)]  # time, silver, station
sum_reached = 0
reached = [False] * N

while Q:
    t, sv, st = heapq.heappop(Q)
    if not reached[st]:
        ans[st] = t
        reached[st] = True
        sum_reached += 1
        if sum_reached == N:
            break

    new_key = (min(max_silver, sv + cd[st][0]), st)
    new_value = t + cd[st][1]
    if new_key not in d or d[new_key] > new_value:
        d[new_key] = t + cd[st][1]
        heapq.heappush(Q, (new_value, *new_key))

    for dist, a, b in railways[st]:
        if sv >= a:
            new_key = (sv - a, dist)
            new_value = t + b
            if new_key not in d or d[new_key] > new_value:
                d[new_key] = new_value
                heapq.heappush(Q, (new_value, *new_key))

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

import itertools

MAX_DIS = 10**10
N,M,R = map(int,input().split(" "))
r_list = list(map(int,input().split(" ")))
roads = [[MAX_DIS]*N for i in range(N)]
for i in range(N):
    roads[i][i] = 0
for i in range(M):
    A,B,C = map(int,input().split(" "))
    roads[A-1][B-1] = C
    roads[B-1][A-1] = C
for k in range(N):
    for i in range(N):
        for j in range(N):
            roads[i][j] = min(roads[i][j],roads[i][k]+roads[k][j])
min_dis = MAX_DIS
for directions in itertools.permutations(r_list):
    distance  = 0
    for dir in range(1,len(directions)):
        distance += roads[directions[dir-1]-1][directions[dir]-1]
    if distance < min_dis:
        min_dis =distance
print(min_dis)


### FIXED CODE ###

import itertools

MAX_DIS = 10**10
N,M,R = map(int,input().split(" "))
r_list = list(map(int,input().split(" ")))
roads = [[MAX_DIS]*N for i in range(N)]
for i in range(N):
    roads[i][i] = 0
for i in range(M):
    A,B,C = map(int,input().split(" "))
    roads[A-1][B-1] = C
    roads[B-1][A-1] = C
for k in range(N):
    for i in range(N):
        for j in range(N):
            roads[i][j] = min(roads[i][j],roads[i][k]+roads[k][j])
min_dis = MAX_DIS
for directions in itertools.permutations(r_list):
    distance  = 0
    for dir in range(1,len(directions)):
        distance += roads[directions[dir-1]-1][directions[dir]-1]
    if distance < min_dis:
        min_dis =distance
print(min_dis)
### BUGGY CODE ###

from itertools import chain

H, W, D = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
exam = [list(map(int, input().split())) for _ in range(Q)]

Ai = list(chain.from_iterable(A))

def search(x):
    tmp = Ai.index(x)
    return (tmp%W+1,tmp//W+1)

for L, R in exam:
    cost = 0
    nw = L
    nt = L + D
    for _ in range((R-L)//D):
        il, jl = search(nw)
        ir, jr = search(nt)
        nw = nt
        nt = nw + D
        cost += abs(il - ir) + abs(jl - jr)
    print(cost)



### FIXED CODE ###

from itertools import chain

H, W, D = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
exam = [list(map(int, input().split())) for _ in range(Q)]

x_a = [0] * (H*W)
y_a = [0] * (H*W)

for i, ax in enumerate(A):
    for j, ay in enumerate(ax):
        x_a[ay-1] = i
        y_a[ay-1] = j

S = [0] * (H*W)
for i in reversed(range(H*W-D)):
    S[i] = abs(x_a[i] - x_a[i+D]) + abs(y_a[i] - y_a[i+D]) + S[i + D]

for L, R in exam:
    print(S[L-1] - S[R-1])
### BUGGY CODE ###

from collections import deque
N, M = map(int, input().split())
ab_list = [ list(map(int, input().split())) for i in range(N)]

score_list = [[] for i in range(M+1)]


for ab in ab_list:
    if ab[0] <= M:
        score_list[ab[0]].append(ab[1])

ans = 0
for i in range(0, M+1):
    if len(score_list[i]) == 0:
        continue
    scores = deque(sorted(score_list[i]))
    ans += scores.pop()
    if i < M and len(scores) > 0:
        score_list[i+1].extend(scores)

print(ans)

### FIXED CODE ###

import heapq


N, M = map(int, input().split())
ab_list = [ list(map(int, input().split())) for i in range(N)]

score_list = [[] for i in range(M+1)]


for ab in ab_list:
    if ab[0] <= M:
        score_list[ab[0]].append(ab[1])


ans = 0
candidates = []

for i in range(0, M+1):

    for s in score_list[i]:
        heapq.heappush(candidates, -s)
    if len(candidates) == 0:
        continue
    ans -= heapq.heappop(candidates)


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

K=int(input())
add=0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            a=[i,j,k]
            a.sort(reverse=True)
            while a[1]>0:
                u=a[1]
                v=a[0]%a[1]
                a[0]=u
                a[1]=v
            A=max(a[0],a[2])
            B=min(a[0],a[2])
            while B>0:
                u=B
                v=A%B
                A=u
                B=v
            add +=A
           
print(add)
            
        

### FIXED CODE ###

import math
K=int(input())
add=0
for i in range(1,K+1):
    for j in range(1,K+1):
        B=math.gcd(i,j)
        for k in range(1,K+1):
            add += math.gcd(B,k)
           
print(add)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = sorted(a)
c = []

for i in b:
    c.append(a.index(i)+1)

print(' '.join(map(str, c)))


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
index=[0]*n

for i in range(n):
    index[a[i]-1] = i+1

print(' '.join(map(str, index)))
### BUGGY CODE ###

import sys
import numpy as np
readline = sys.stdin.buffer.readline

N,K = map(int,readline().split())
people = np.array(readline().split(),np.int64)
food = np.array(readline().split(),np.int64)
 
people.sort()
food.sort()
food=food[::-1]

#2分探索　Kの値で
_max = max(people)*max(food)
_min = 0

while _max>_min:
  mean = (_max+_min)//2
  # 各人が修行をする回数の配列　負の値もでる
  K_arr = np.maximum(0,people - mean//food)
  # 総修行回数
  _K = sum(K_arr)
  if _K > K:
    _min = mean+1
  else:
    _max = mean
    
print(_max)
  

### FIXED CODE ###

import sys
import numpy as np
readline = sys.stdin.buffer.readline

N,K = map(int,readline().split())
people = np.array(readline().split(),np.int64)
food = np.array(readline().split(),np.int64)
 
people.sort()
food.sort()
food=food[::-1]

#2分探索　Kの値で
_max = max(people)*max(food)
_min = 0

while _max>_min:
  mean = (_max+_min)//2
  # 各人が修行をする回数の配列　負の値もでる
  _K = np.maximum(0,people - mean//food).sum()
  if _K > K:
    _min = mean+1
  else:
    _max = mean
    
print(_max)
### BUGGY CODE ###

n,m = map(int,input().split())
uv = [[] for _ in range(n)]
for i in range(m):
  u,v = map(lambda x:int(x)-1,input().split())
  uv[u].append(v)
s,t = map(lambda x:int(x)-1,input().split())
time = 0
now = [s]
flag = 0
while time < 3*n:
  time += 1
  tmp = []
  for x in now:
    for y in uv[x]:
      tmp.append(y)
  now = tmp
  if time % 3 == 0:
    if t in now:
      flag = 1
      break
if flag == 1:
  print(time//3)
else:
  print(-1)

### FIXED CODE ###

n,m = map(int,input().split())
pst = [[] for _ in range(n)]
for _ in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  pst[a].append(b)
s,t = map(int,input().split())
s -= 1
t -= 1
cnt = [[0,0,0] for _ in range(n)]
cnt[s][0] = 1
now = [s]
time = 0
while now:
  time += 1
  last = now
  now = []
  for x in last:
    for y in pst[x]:
      if cnt[y][time%3] == 0:
        cnt[y][time%3] = 1
        now.append(y)
  #print(time,cnt,now)
  if cnt[t][0] == 1:
    print(time//3)
    break
else:
  print(-1)
### BUGGY CODE ###

while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  H = range(h)
  A = [0]*h
  for i in H:
    x = raw_input().replace(".", "1").replace("*", "0")
    A[i] = map(int, list(x))
  B = A[:]
  C = [0]*h
  for j in H[1:]:
    M = ["1","11","111"]
    for i in H[j:]:
      x = [e1 & e2 for e1, e2 in zip(B[i-j], A[i])]
#      B[i-j] = x
#      M.append(sorted("".join(map(str, x)).split("0"))[-1])
    C[j] = len(sorted(M)[-1])*(j+1)
  print max(C)

### FIXED CODE ###

while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  M = [0]*(h+1)
  a=[0]*w
  for i in range(h):
    x = raw_input()
    b=[0]*w
    sp=-1
    C = [-1]*(h+1)
    for j in range(w):
      if x[j]=="*": c=0
      else: c=a[j]+1
      b[j]=c
      dw=c-sp
      if dw>0: C[sp+1:c+1]=[j]*dw
      elif dw<0:
        for k in range(c+1,sp+1): M[k]=max(M[k],j-C[k])
        C[c+1:sp+1]=[-1]*(-dw)
      sp=c
    for k in range(1,sp+1):
      if C[k]>=0: M[k]=max(M[k],w-C[k])
    a=b
  s=max([a*b for a,b in zip(M, range(h+1))])
  print s
### BUGGY CODE ###

H,W,D = map(int,input().split())

link = [0]*(H*W)
for j in range(H):
  A = list(map(int,input().split()))
  for i in range(W):
    link[A[i]-1] = (i,j)
#print(link)

Q = int(input())
for _ in range(Q):
  L,R = map(int,input().split())
  L -= 1
  R -= 1
  #print(L,R)
  
  ans = 0
  for x in range(L+D,R+1,D):
    i,j = link[x-D][0],link[x-D][1]
    u,v = link[x  ][0],link[x  ][1]
    #print(i,j,u,v)
    ans += abs(i-u)+abs(j-v)
  print(ans)


### FIXED CODE ###

H,W,D = map(int,input().split())

pos = [0]*(H*W)
for j in range(H):
  A = list(map(int,input().split()))
  for i in range(W):
    pos[A[i]-1] = (i,j)
#print(link)

memo = [0]*(H*W)
for x in range(H*W):
  if x<D:
    continue
  i,j = pos[x-D][0],pos[x-D][1]
  u,v = pos[x  ][0],pos[x  ][1]
  memo[x] = memo[x-D]+abs(i-u)+abs(j-v)

Q = int(input())
for _ in range(Q):
  L,R = map(int,input().split())
  print(memo[R-1]-memo[L-1])
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
for _ in range(m):
    b, c = map(int, input().split())
    a += [c] * b
a.sort(reverse=True)
print(sum(a[:n]))


### FIXED CODE ###

n, m = map(int, input().split())
A = list(map(int, input().split()))
d = {}
for a in A:
    d[a] = 1 if a not in d else d[a] + 1
for _ in range(m):
    b, c = map(int, input().split())
    d[c] = b if c not in d else d[c] + b
ans = 0
cnt = 0
L = sorted(d, reverse=True)
for k in L:
    if d[k] + cnt < n:
        ans += k * d[k]
        cnt += d[k]
    else:
        ans += k * (n - cnt)
        break
print(ans)
### BUGGY CODE ###

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

a  = [0]*n

a = [int(s) for s in input().split()]

nxt = a[0]

seen = [0]*n
seen[0] = 1
#load = []
res = 0
flag = 0
for i in range(k-1):
    #print(seen)
    #print(nxt)
    if not(nxt in seen):
        seen[i+1] = nxt
        nxt = a[nxt-1]
    else:
        root = i - seen.index(nxt) + 1
        #print(root)
        #print(k-1-i)
        zansa = (k-1-i)%root
        res = seen[seen.index(nxt)+zansa]
        flag = 1
        break


if(flag == 1):
    print(res)
else:
    print(nxt)

### FIXED CODE ###

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

a  = [0]*n

a = [int(s) for s in input().split()]

nxt = a[0]

seen = [1]
load = set()
load.add(1)
res = 0
flag = 0
for i in range(k-1):
    #print(seen)
    #print(nxt)
    if not(nxt in load):
        seen.append(nxt)
        load.add(nxt)
        nxt = a[nxt-1]
    else:
        root = i - seen.index(nxt) + 1
        #print(root)
        #print(k-1-i)
        zansa = (k-1-i)%root
        res = seen[seen.index(nxt)+zansa]
        flag = 1
        break


if(flag == 1):
    print(res)
else:
    print(nxt)
### BUGGY CODE ###

def main():
    footing, next_range = map(int, input().split())
    height = list(map(int, input().split()))
    result = abs(height[-1] - height[0])
    if next_range < footing:
        answer = [float("inf")] * footing
        answer[0] = 0
        answer[1] = abs(height[1] - height[0])
        for i in range(footing):
            for j in range(1, next_range + 1):
                answer[i] = min(answer[i], answer[i - j] + abs(height[i] - height[i - j]))
        result = answer[-1]
    print(result)


if __name__ == '__main__':
    main()



### FIXED CODE ###

def main():
    footing, next_range = map(int, input().split())
    height = list(map(int, input().split()))
    result = abs(height[-1] - height[0])
    if next_range < footing:
        answer = [float("inf")] * footing
        answer[0] = 0
        answer[1] = abs(height[1] - height[0])
        for i in range(footing):
            for j in range(1, next_range + 1):
                answer[i] = min(answer[i], answer[i - j] + abs(height[i] - height[i - j]))
        result = answer[-1]
    print(result)


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

import collections

n = int(input())
a = list(map(int,input().split()))
q = int(input())
b = []
c = []
for i in range(q):
    tmpb,tmpc = map(int,input().split())
    b.append(tmpb)
    c.append(tmpc)

dic = collections.Counter(a)
val = 0
for i in range(q):
    if b[i] in dic:
        if c[i] not in dic:
            dic[c[i]] = 0
        dic[c[i]] += dic[b[i]]
        dic[b[i]] = 0
    for key, value in dic.items():
        val +=key*value
    print(val)
    val=0

### FIXED CODE ###

import collections

n = int(input())
a = list(map(int,input().split()))
q = int(input())
b = []
c = []
for i in range(q):
    tmpb,tmpc = map(int,input().split())
    b.append(tmpb)
    c.append(tmpc)

dic = collections.Counter(a)
val = 0
for key, value in dic.items():
    val +=key * value
for i in range(q):
    tmp = 0
    if b[i] in dic:
        if c[i] not in dic:
            dic[c[i]] = 0
        tmp = (c[i] - b[i]) * dic[b[i]]
        dic[c[i]] += dic[b[i]]
        dic[b[i]] = 0
        val = val + tmp
    print(val)
### BUGGY CODE ###

n = int(input())
s = str(input())
cnt = 0
def f(x):
	tgt = [ x[0], x[1], x[2] ]
	now = 0
	global n
	for i in range(n):
		if s[i] == tgt[now]: now += 1
		if now == 3: return True
	return False
for i in range(1000):
	if len(str(i)) == 1: t = "00"+str(i)
	elif len(str(i)) == 2: t = "0"+str(i)
	else: t = str(i)
	if f(t): cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
s = str(input())
cnt = 0
def f(x):
	tgt = [ x[0], x[1], x[2] ]
	now = 0
	global n
	for i in range(n):
		if s[i] == tgt[now]: now += 1
		if now == 3: return True
	return False
for i in range(1000):
	if len(str(i)) == 1: t = "00"+str(i)
	elif len(str(i)) == 2: t = "0"+str(i)
	else: t = str(i)
	if f(t): cnt += 1
print(cnt)
### BUGGY CODE ###

from operator import mul
from functools import reduce

N = int(input())
A=list(map(int,input().split()))
s = reduce(mul, A)
if s > 10**18:
  s = -1
print(s)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
if 0 in A:
  print(0)
  exit()
prod = 1
for i in A:
  prod *= i
  if prod > 10**18:
    print(-1)
    exit()
print(prod)
### BUGGY CODE ###

s=input()

ans=0

for i in range(len(s)):
    if(s[i]=='W'):
        ans+=list(s[:i]).count('B')
print(ans)

### FIXED CODE ###

s=input()

ans=0
b_count=0
for i in range(len(s)):
    if(s[i]=='W'):
        ans+=b_count
    else:
        b_count+=1
print(ans)
### BUGGY CODE ###

A, B, C, K = map(int,input().split())

ans = 0

for i in range(K):
    if i+1 <= A:
        ans += 1
    if A < i+1 <= A + B:
        ans +=0
    if A + B < i+1 <= A + B + C:
        ans = ans - 1
        
print(ans)

### FIXED CODE ###

A, B, C, K = map(int,input().split())

if K < A:
    print(K)
if A <= K < A + B:
    print(A)
if A + B <= K <= A + B + C:
    print(2*A + B - K)
### BUGGY CODE ###

N, x = map(int, input().split())
num_list = [int(x) for x in input().split()]
count = 0
if x == 0:
  print(sum(num_list))
else:
  while True:
    mark = 0
    for i, num in enumerate(num_list[0:-1]):
      if (num_list[i] + num_list[i+1] > x):
        if num_list[i+1] != 0:
          num_list[i+1] = num_list[i+1] - 1
          count+=1
          mark = 1
    if mark == 0:
      break

  print(count)

### FIXED CODE ###

N, x = map(int, input().split())
num_list = [int(x) for x in input().split()]
count = 0

for i in range(N-1):
  n = num_list[i] + num_list[i+1]
  if n > x:
    if n - num_list[i+1] > x:
      count += n - x
      num_list[i+1] = 0
    else:
      count += n - x
      num_list[i+1] -= (n-x)

print(count)
### BUGGY CODE ###

import itertools
import sys


sys.setrecursionlimit(10**7)


def main():
    INF = 10 ** 7
    H, W = list(map(int, input().split()))
    CH, CW = list(map(lambda x: int(x) - 1, input().split()))
    DH, DW = list(map(lambda x: int(x) - 1, input().split()))
    S = [input() for _ in range(H)]
    if S[DH][DW] == '#':
        print(-1)
        return
    # 使うワープの最小回数
    cnt = [[INF for _ in range(W)] for _ in range(H)]

    def dfs(h=DH, w=DW, c=0):
        if c >= cnt[h][w]:
            return
        cnt[h][w] = c
        for dh, dw in itertools.product(range(-2, 3), repeat=2):
            nh, nw = h + dh, w + dw
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                # 上下左右なら回数据え置き
                if [dh, dw] in [[1, 0], [-1, 0], [0, -1], [0, 1]]:
                    dfs(nh, nw, c)
                # それ以外はワープ
                else:
                    dfs(nh, nw, c + 1)

    dfs()
    if cnt[CH][CW] == INF:
        print(-1)
    else:
        print(cnt[CH][CW])


if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import deque


def main():
    INF = 10 ** 7
    H, W = list(map(int, input().split()))
    CH, CW = list(map(lambda x: int(x) - 1, input().split()))
    DH, DW = list(map(lambda x: int(x) - 1, input().split()))
    S = [input() for _ in range(H)]
    if S[DH][DW] == '#':
        print(-1)
        return
    # 歩き
    walk_list = [[1, 0], [-1, 0], [0, -1], [0, 1]]
    # ワープ
    warp_list = [[-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]]
    # 使うワープの最小回数
    cnt = [[INF for _ in range(W)] for _ in range(H)]

    warp_checked = [[0 for _ in range(W)] for _ in range(H)]
    warp_que = deque([(DH, DW)])
    c = 0
    while len(warp_que) > 0:
        # warp_queから歩きのみでいける範囲の探索
        walk_que = deque()
        while len(warp_que) > 0:
            h, w = warp_que.pop()
            cnt[h][w] = c
            walk_que.append((h, w))
            tmp_walk_que = deque([(h, w)])
            while len(tmp_walk_que) > 0:
                h, w = tmp_walk_que.pop()
                for dh, dw in walk_list:
                    nh, nw = h + dh, w + dw
                    if 0 <= nh < H and 0 <= nw < W and \
                        S[nh][nw] == '.' and cnt[nh][nw] == INF:
                        cnt[nh][nw] = c
                        tmp_walk_que.append((nh, nw))
                        walk_que.append((nh, nw))
        # ワープでしかいけない範囲の探索
        while len(walk_que) > 0:
            h, w = walk_que.pop()
            for dh, dw in warp_list:
                nh, nw = h + dh, w + dw
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and \
                    warp_checked[nh][nw] == 0 and cnt[nh][nw] == INF:
                    warp_checked[nh][nw] = 1
                    warp_que.append((nh, nw))
        c += 1

    if cnt[CH][CW] == INF:
        print(-1)
    else:
        print(cnt[CH][CW])


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

M = 10 ** 6 + 3
HASH_MAP = [None for i in range(M)]


def hash1(key):
    return key % M


def hash2(key):
    return 1 + (key % M-1)


def my_hash(key, i):
    return (hash1(key)+i*hash2(key)) % M


def make_num(s):
    return len(s) + ord(s[0])


def insert(key):
    i = 0
    key_n = make_num(key)
    while True:
        j = my_hash(key_n, i)
        if HASH_MAP[j] is None:
            HASH_MAP[j] = key
            return j

        i += 1


def search(key):
    i = 0
    key_n = make_num(key)
    while True:
        j = my_hash(key_n, i)
        if HASH_MAP[j] == key:
            return j
        elif HASH_MAP[j] is None or i >= M:
            return None

        i += 1


def main():
    n = int(input())

    for i in range(n):
        order = input().split()
        if order[0] == "insert":
            insert(order[1])
        else:
            if search(order[1]) is None:
                print("no")
            else:
                print("yes")


if __name__ == '__main__':
    main()



### FIXED CODE ###

def main():
    n = int(input())

    s_set = set()
    for i in range(n):
        order = input().split()
        if order[0] == "insert":
            s_set.add(order[1])
        else:
            if order[1] in s_set:
                print("yes")
            else:
                print("no")


if __name__ == '__main__':
    main()