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

from sys import stdin
h,w = map(int,stdin.readline().rstrip().split())
li = [stdin.readline().rstrip() for _ in range(h)]
#各四方向のDPをつくる
L = [[0 for i in range(w)]for j in range(h)]
R = [[0 for i in range(w)]for j in range(h)]
D = [[0 for i in range(w)]for j in range(h)]
U = [[0 for i in range(w)]for j in range(h)]
ma = 0
for i in range(h):
    for j in range(w):
        if li[i][j] == "#":L[i][j] = 0
        elif j == 0:L[i][j] = 1
        else:L[i][j] = L[i][j-1]+1
for i in range(h):
    for j in range(w):
        if li[i][w-j-1] == "#":R[i][w-j-1] = 0
        elif w-j-1 == w-1:R[i][w-j-1] = 1
        else:R[i][w-j-1] = R[i][w-j]+1
for i in range(h):
    for j in range(w):
        if li[i][j] == "#":U[i][j] = 0
        elif i == 0:U[i][j] = 1
        else:U[i][j] = U[i-1][j]+1
for i in range(h):
    for j in range(w):
        if li[h-i-1][j] == "#":D[h-i-1][j] = 0
        elif h-i-1 == h-1:D[h-i-1][j] = 1
        else:D[h-i-1][j] = D[h-i][j]+1
for i in range(h):
    for j in range(w):
        point = L[i][j]+R[i][j]+D[i][j]+U[i][j]-3
        ma = max(ma,point)
print(ma)

### FIXED CODE ###

from sys import stdin
h,w = map(int,stdin.readline().rstrip().split())
li = [stdin.readline().rstrip() for _ in range(h)]
#各四方向のDPをつくる
L = [[0 for i in range(w)]for j in range(h)]
R = [[0 for i in range(w)]for j in range(h)]
D = [[0 for i in range(w)]for j in range(h)]
U = [[0 for i in range(w)]for j in range(h)]
ma = 0
for i in range(h):
    for j in range(w):
        if li[i][j] == "#":L[i][j] = 0
        elif j == 0:L[i][j] = 1
        else:L[i][j] = L[i][j-1]+1
for i in range(h):
    for j in range(w):
        if li[i][w-j-1] == "#":R[i][w-j-1] = 0
        elif w-j-1 == w-1:R[i][w-j-1] = 1
        else:R[i][w-j-1] = R[i][w-j]+1
for i in range(h):
    for j in range(w):
        if li[i][j] == "#":U[i][j] = 0
        elif i == 0:U[i][j] = 1
        else:U[i][j] = U[i-1][j]+1
for i in range(h):
    for j in range(w):
        if li[h-i-1][j] == "#":D[h-i-1][j] = 0
        elif h-i-1 == h-1:D[h-i-1][j] = 1
        else:D[h-i-1][j] = D[h-i][j]+1
for i in range(h):
    for j in range(w):
        point = L[i][j]+R[i][j]+D[i][j]+U[i][j]-3
        ma = max(ma,point)
print(ma)
### BUGGY CODE ###


from collections import Counter
from collections import defaultdict
from functools import lru_cache
import itertools
import random
import cProfile
import copy

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

X = [i for i in range(N+1)]

count = 0
for i in itertools.product(X,X,X):
	if sum(i) == M:
		count += 1
print(count)

### FIXED CODE ###

import itertools

N,M = map(int,input().split())
X = [i for i in range(N+1)]

count = 0
for x,y in itertools.product(X,X):
	if 0 <= M - x - y <= N:
		count += 1

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

import copy
n = int(input())
a = list(int(input()) for _ in range(n))

for i in range(n):
    # copy.copyを使用することで新しいオブジェクトを生成し、元のリストが影響を受けない
    b = copy.copy(a)
    b.pop(i)
    print(max(b))


### FIXED CODE ###

import copy
n = int(input())
a = [int(input()) for _ in range(n)]
 
b = copy.deepcopy(a)
b.sort()
max1 = b[-1]
max2 = b[-2]
 
for i in a:
    if i == max1:
        print(max2)
    else:
        print(max1)
### BUGGY CODE ###

K = int(input())

#a,bの最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

print(ans)


### FIXED CODE ###

K = int(input())

#a,bの最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

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

A, B, K = map(int, input().split())
x=[]
for i in range(A, B+1):
    x.append(i)
a=x[:K]
b=x[-K:]
c=sorted(set(a)|set(b))
for i in c:
    print(i)

### FIXED CODE ###

A, B, K = map(int, input().split())
list=[]
for i in range(A, A+K):
    if i < A+K and i <= B:
        list.append(i)
for i in range(B-K, B+1):
    if i > (B-K) and i >= A:
        list.append(i)
for i in sorted(set(list)):
    print(i)
### BUGGY CODE ###

from collections import deque

def main():
    N, *AB = map(int, open(0).read().split())

    E = [[] for _ in range(N + 1)]

    memo = {}
    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
        E[a].append(b)
        E[b].append(a)
        memo[(a, b)] = i
        memo[(b, a)] = i

    K = max(len(e) for e in E)

    A = [0] * (N - 1)

    cand = {i for i in range(1, K + 1)}

    visited = [False] * (N + 1)

    Q = deque([(-1, 1)])
    visited[1] = True
    while Q:
        c, v = Q.popleft()
        C = cand - {c}
        for u in E[v]:
            if visited[u]:
                continue
            visited[u] = True
            c = C.pop()
            Q.append((c, u))
            A[memo[(v, u)]] = c

    print(K)
    for a in A:
        print(a)

main()


### FIXED CODE ###

from collections import deque

def main():
    N, *AB = map(int, open(0).read().split())

    E = [set() for _ in range(N + 1)]

    memo = {}
    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
        E[a].add(b)
        E[b].add(a)
        memo[(a, b)] = i
        memo[(b, a)] = i

    K = max(len(e) for e in E)

    A = [""] * (N - 1)

    visited = [False] * (N + 1)

    Q = deque([(-1, 1)])
    visited[1] = True
    while Q:
        a, v = Q.popleft()
        c = 0
        for u in E[v]:
            E[u].remove(v)
            c += 1
            if c == a:
                c += 1
            Q.append((c, u))
            A[memo[(v, u)]] = str(c)
        E[v] = set()
    print(K)
    print("\n".join(A))

main()
### BUGGY CODE ###

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

var = N % K
if var == 0:
        print(0)
elif var == K-1 or var == 1:
        print(1)
else:
        while N > K // 2:
                N = abs(N-K*(N//K))
        print(N)

### FIXED CODE ###

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

var = N % K
if var == 0:
        print(0)
elif var == K-1 or var == 1:
        print(1)
else:
        while N >= math.ceil(K / 2):
                N = abs(N-K*(N//K+1))
        print(N)
### BUGGY CODE ###

A, B, K = map(int, input().split())
c = 0
while True:
    if A % 2 == 0:
        pass
    else:
        A -= 1

    B += A / 2
    A -= A / 2
    c += 1

    if B % 2 == 0:
        pass
    else:
        B -= 1

    A += B / 2
    B -= B / 2
    c += 1

    if c == K:
        break

print(int(A), int(B))


### FIXED CODE ###

import numpy as np
A, B, K = map(int, input().split())
coo = np.array([A, B])
c = 0
for _ in range(K):
    if coo[0] % 2 == 0:
        pass
    else:
        coo[0] -= 1

    half = coo[0] / 2
    coo[1] += half
    coo[0] -= half
    coo = coo[::-1]

if K % 2 == 0:
    print(*coo)
else:
    print(*coo[::-1])
### BUGGY CODE ###

import re

N, Q = map(int, input().split())
S = input()
for x in range(Q):
    a, b = map(int, input().split())
    s = S[a-1:b]
    print(len(re.findall('AC', s)))

### FIXED CODE ###

from itertools import accumulate

N, Q = map(int, input().split())
S = input()
lst = [0]
idx = 0
for x in range(len(S) - 1):
    if S[x] == 'A' and S[x + 1] == 'C':
        lst.append(1)
    else:
        lst.append(0)

lst2 = list(accumulate(lst))
for x in range(Q):
    a, b = map(int, input().split())
    print(lst2[b-1] - lst2[a-1])
### BUGGY CODE ###

import re
n,q = map(int,input().split())
#s=list(input())	
s = input()



for i in range(q):
    l,r = map(int,input().split())
    s2 = s[l-1:r]
    a = re.findall("AC", s2)
    print(len(a))



### FIXED CODE ###

n,q = map(int,input().split())
#s=list(input())	
s = input()
index = -1
indexes = []
while True:
    index = s.find("AC", index + 1)
    if index == -1:
        break
    indexes.append(index)
dp = []

for i in range (n):
    dp.append(len(indexes))
    if len(indexes)> 0 and indexes[0] == i:
        indexes.pop(0)
for i in range(q):
    l,r = map(int,input().split())
    print(dp[l-1] - dp[r-1])
### BUGGY CODE ###

import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
from collections import defaultdict
def main():
    N, P = MI()
    S_ = S()
    mod_list = defaultdict(int)
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            num = int(S_[i])
            if num % P == 0:
                ans += i + 1

    else:
        for i in range(N):
            num = S_[i:N]
            mod = int(num) % P
            if mod == 0:
                ans += 1
            if mod_list[mod] >= 1:
                ans += mod_list[mod]
            mod_list[mod] += 1

    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
from collections import defaultdict
def main():
    N, P = MI()
    S_ = S()
    mod_list = defaultdict(int)
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            num = int(S_[i])
            if num % P == 0:
                ans += i + 1

    else:
        num = 0
        point = 1
        for i in S_[::-1]:
            num += int(i) * point
            mod = int(num) % P
            mod_list[mod] += 1
            point *= 10
            point %= P
    values_ = mod_list.values()
    ans += mod_list[0]
    for value in values_:
        ans += (value - 1) * value // 2

    print(ans)

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

# import queue
from collections import deque

h, w = map(int, input().split())

grid = [[True] * (w + 2)]
for _ in range(h):
    grid.append([True] + [x == '#' for x in input()] + [True])
grid.append([True] * (w + 2))

q = deque()

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if grid[i][j] is True:
            q.appendleft((i, j))

cnt = 0
while True:
    waiting = []
    while len(q) > 0:
        i, j = q.pop()
        if grid[i + 1][j] is False:
            grid[i + 1][j] = True
            waiting.append((i + 1, j))
        if grid[i - 1][j] is False:
            grid[i - 1][j] = True
            waiting.append((i - 1, j))
        if grid[i][j + 1] is False:
            grid[i][j + 1] = True
            waiting.append((i, j + 1))
        if grid[i][j - 1] is False:
            grid[i][j - 1] = True
            waiting.append((i, j - 1))

    if not waiting:
        break
    cnt += 1
    q.extendleft(waiting)

print(cnt)


### FIXED CODE ###

h, w = map(int, input().split())

grid = [[True] * (w + 2)]
for _ in range(h):
    grid.append([True] + [x == '#' for x in input()] + [True])
grid.append([True] * (w + 2))

q = []

for i in range(1, h + 1):
    for j in range(1, w + 1):
        if grid[i][j] is True:
            q.append((i, j))

cnt = 0
while q:
    qq = []
    for i, j in q:
        if not grid[i + 1][j]:
            grid[i + 1][j] = True
            qq.append((i + 1, j))
        if not grid[i - 1][j]:
            grid[i - 1][j] = True
            qq.append((i - 1, j))
        if not grid[i][j + 1]:
            grid[i][j + 1] = True
            qq.append((i, j + 1))
        if not grid[i][j - 1]:
            grid[i][j - 1] = True
            qq.append((i, j - 1))

    cnt += 1
    q = qq

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

N, K = map(int, input().split())
a = list(map(int, input().split()))
if N == K:
    print(0)
else:
    l = set(a)
    bucket = sorted([a.count(i) for i in l])
    print(sum(bucket[0:len(bucket) - K:]))

### FIXED CODE ###

from collections import Counter
N, K = map(int, input().split())
a = Counter(list(map(int, input().split())))
if N == K:
    print(0)
else:
    num = list(a.values())
    if len(num) <= K:
        print(0)
    else:
        print(sum(sorted(num)[:-K]))
### BUGGY CODE ###

N = int(input())
a = 0
s = 0
ans = 10000000000000000
for x in range(1,N):
    s=N//x
    if N%x==0:
        a = (x-1)+(s-1)
        if ans > a:
            ans = a
print(ans)


### FIXED CODE ###

N = int(input())
a = 0
ans = N-1
s = 0
for x in range(1,1000001):
    s=N//x
    if N%x==0:
        a = (s-1)+(x-1)
        if ans>a:
             ans = a
print(ans)
### BUGGY CODE ###

import os
import sys
from collections import defaultdict, Counter
from itertools import product, permutations,combinations, accumulate
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush,heapify
from math import ceil, floor, sqrt, gcd
from copy import deepcopy


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    num = 1000000000000000000
    ans = 1
    for i in a_list:
        ans *= i

    if ans <= num:
        print(ans)
    else:
        print(-1)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import os
import sys
from collections import defaultdict, Counter
from itertools import product, permutations,combinations, accumulate
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush,heapify
from math import ceil, floor, sqrt, gcd
from copy import deepcopy


def main():
    n = int(input())
    a_list = tuple(map(int, input().split()))
    num = 1e18
    ans = 1
    if (0 in a_list):
        print(0)
        sys.exit()
    for i in range(n):
        ans *= a_list[i]
        if ans > num:
            print(-1)
            sys.exit()

    
    if ans <= num:
        print(ans)
    else:
        print(-1)

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

import bisect

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

l = [[int(x) for x in input().split()] for _ in range(M)]



def do(l):
    

    count = 1

    l.sort()

    while True:

        # l2 = [v2 for (_,v2) in l]
        # l2.sort()
        

        nx = min(l,key=lambda x:x[1])[1]

        for i in range(len(l)):
            #print(l)
            
            if l[i][0] >= nx:
                #print("i")
                #print(i)
                #print(count)
                # h+=1
                # if i > 0:
                l = l[i:]
                count+=1
                break
            if i >= len(l)-1:
                return count
        if l == []:
            return count



result = do(l)
print(result)

### FIXED CODE ###

import bisect

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

l = [[int(x) for x in input().split()] for _ in range(M)]



def do(l):

    count = 1

    l.sort()
    right = l[0][1]


    for i in range(len(l)):
        if l[i][0] >= right:
            right = l[i][1]
            count+=1
            continue
        if l[i][1] < right:
            right = l[i][1]
    return count

testl = [[x,x+1] for x in range(1)]

result = do(l)
print(result)
### BUGGY CODE ###

mod = 10**9+7
n = int(input())
A = tuple(tuple(map(int, input().split())) for _ in range(n))
dp = [[0]*(1<<n) for _ in range(n+1)]
dp[0][(1<<n)-1] = 1
for i in range(n):
  for j in range(n):
    for k in range(1<<n):
      if A[i][j] and (k>>j & 1):
        dp[i+1][k^(1<<j)] += dp[i][k]
        dp[i+1][k^(1<<j)] %= mod
ans = dp[n][0]
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

mod = 10**9+7
n = int(input())
A = tuple(tuple(map(int, input().split())) for _ in range(n))
dp = [[-1]*(1<<n) for _ in range(n+1)]
def f(i, k):
  if i == n:
    return 1
  if dp[i][k] != -1:
    return dp[i][k]
  res = 0
  for j in range(n):
    if A[i][j] and ((k>>j)&1):
      res += f(i+1, k^(1<<j))
      res %= mod
  dp[i][k] = res
  return res
ans = f(0, (1<<n)-1)
print(ans)
### BUGGY CODE ###

from collections import deque

N,X,Y = map(int,input().split())
X -= 1
Y -= 1

d = {i:set() for i in range(N)}
for i in range(0,N):
  if i-1>=0:
    d[i-1].add(i)
  if i+1<=N-1:
    d[i+1].add(i)
  if i==X:
    d[Y].add(X)
    d[X].add(Y)

ans = {i+1:0 for i in range(N-1)}


for i in range(0,N):
  dist = [-1]*N
  q = deque([i])
  dist[i] = 0
  while q:
    v = q.popleft()
    for j in d[v]:
      if dist[v] + 1 < dist[j] or dist[j]==-1:
        dist[j] = dist[v] + 1
        q.appendleft(j)
  for k in dist:
    if k in ans:
      ans[k] += 1

for l in ans.values():
  print(l//2)
  

### FIXED CODE ###

from collections import deque

N,X,Y = map(int,input().split())
X -= 1
Y -= 1

d = {i:set() for i in range(N)}
for i in range(0,N):
  if i-1>=0:
    d[i-1].add(i)
  if i+1<=N-1:
    d[i+1].add(i)
  if i==X:
    d[Y].add(X)
    d[X].add(Y)

ans = {i+1:0 for i in range(N-1)}

for i in range(0,N):
  dist = [-1]*N
  q = deque([i])
  dist[i] = 0
  while q:
    v = q.popleft()
    for j in d[v]:
      if  dist[j] == -1:
        dist[j] = dist[v] + 1
        ans[dist[j]] += 1
        q.appendleft(j)
      elif dist[v] + 1 < dist[j]:
        ans[dist[j]] -= 1
        dist[j] = dist[v] + 1
        ans[dist[j]] += 1
        q.appendleft(j)

for l in ans.values():
  print(l//2)
### BUGGY CODE ###

import math

import math
def Sieve_of_Eratosthenes(N):
    if N<2: return set()
    prime=set(i for i in range(2,N+1))
    for i in range(2,math.ceil(N**0.5)+1):
        tmp=set()
        for j in prime:
            if j>i and j%i==0: tmp.add(j)
        for j in tmp:
            prime.remove(j)

    return prime

def gcd(a,b):
    if b>a:
        a,b=b,a
    while b:
        a,b=b, a%b
    return a

a,b=map(int,input().split())
n=gcd(a,b)
prime=Sieve_of_Eratosthenes(int(math.sqrt(n))+2)

dic={}
ans=1
x=n
for p in prime:
    if x%p==0:
        ans+=1
        while x%p==0:
            x=x//p

if x!=1: ans+=1
print(ans)

### FIXED CODE ###

import math
def gcd(a,b):
    if b>a:
        a,b=b,a
    while b:
        a,b=b, a%b
    return a

a,b=map(int,input().split())
x=gcd(a,b)
s=set()
for i in range(2, min(x+1,int(math.sqrt(x))+2) ):
    while x%i==0:
        x=x//i
        s.add(i)
    if x==1: break
if x>1: s.add(x)
print(len(s)+1)
### BUGGY CODE ###

S = input()
N = len(S)
K = int(input())
cnt = {i: [] for i in range(N)}
for i in range(N):
    for j in range(N - i):
        s = S[j:j+i+1]
        idx = cnt[len(s)-1]
        if s not in idx:
            idx.append(s)
ttl = []
for k, v in cnt.items():
    ttl.extend(v)
ttl.sort()
print(ttl[K-1])

### FIXED CODE ###

S = input()
N = len(S)
K = int(input())
cnt = {i: [] for i in range(N)}
for i in range(N):
    for j in range(N - i):
        s = S[j:j+i+1]
        l = len(s)
        if s not in cnt[l-1]:
            cnt[l-1].append(s)
    if i > K:
        break
ttl = []
for k, v in cnt.items():
    ttl.extend(v)
ttl.sort()
print(ttl[K-1])
### BUGGY CODE ###

import math
K = int(input())

def gcd_plus(a,b,c):
  num_list = [a,b,c]
  ans = num_list[0]
  for i in range(1,3):
    ans = math.gcd(ans,num_list[i])
  return ans

sum = 0
for a in range(1,K+1):
  for b in range(1,K+1):
    for c in range(1,K+1):
      sum += gcd_plus(a,b,c)
      
print(sum)

### FIXED CODE ###

import math
K = int(input())

sum = 0
gcd_a_b = 0
for a in range(1,K+1):
  for b in range(1,K+1):
    gcd_a_b = math.gcd(a,b)
    for c in range(1,K+1):
      sum += math.gcd(gcd_a_b,c)
      
print(sum)
### BUGGY CODE ###

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

N = int(input().strip())
from itertools import combinations
nodes = list(combinations(range(N), 2))
graph = {i:[] for i in nodes}
for x in range(N):
  l = list(map(int,input().split()))
  y = l[0]-1
  prev = (min(x,y),max(x,y))
  for y in l[1:]:
    y -= 1
    now = (min(x,y),max(x,y))
    graph[prev].append(now)
    prev = now

d = {k:1 for k in nodes}
in_cnt = {k:0 for k in nodes}
for x in nodes:
  for y in graph[x]:
    in_cnt[y] += 1
q = deque([i for i in nodes if not in_cnt[i]])
if not q:
  print(-1)
  exit()
ans = 0
while q:
  x = q.popleft()
  for y in graph[x]:
    d[y] = max(d[y],d[x]+1)
    ans = max(ans,d[y])
    in_cnt[y] -= 1
    if not in_cnt[y]:
      q.append(y)
if [i for i in nodes if in_cnt[i]]:
  print(-1)
  exit()

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input().strip())
M = N*(N-1)//2

graph = [[] for i in range(M)]
in_cnt = [0 for i in range(M)]
for x in range(1,N+1):
  l = list(map(int,input().split()))
  y = l[0]
  b,s = max(x,y),min(x,y)
  prev = (b-1)*(b-2)//2+s-1
  for y in l[1:]:
    b,s = max(x,y),min(x,y)
    now = (b-1)*(b-2)//2+s-1
    graph[prev].append(now)
    in_cnt[now] += 1 
    prev = now

d = [1 for k in range(M)]
q = [i for i in range(M) if not in_cnt[i]]

if not q:
  print(-1)
  exit()
ans = 0
while q:
  x = q.pop()
  for y in graph[x]:
    d[y] = max(d[y],d[x]+1)
    ans = max(ans,d[y])
    in_cnt[y] -= 1
    if not in_cnt[y]:
      q.append(y)
if [i for i in range(M) if in_cnt[i]]:
  print(-1)
  exit()

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

import numpy as np

# リストからある値に最も近い値を返却する関数
def getNearestValue(list, num):
    idx = np.abs(np.asarray(list) - num).argmin()
    return list[idx]

def main():
    A, B, Q = map(int, input().split())  #複数数値入力
    S = [0] * A
    T = [0] * B
    X = [0] * Q
    for i in range(A):
        S[i] = int(input())
    for i in range(B):
        T[i] = int(input())
    for i in range(Q):
        X[i] = int(input())

    for i in range(Q):
        ans = 0

        # 1:神社先
        basyo1 = getNearestValue(S, X[i])
        dist1 = abs(basyo1 - X[i])
        dist1 += abs(getNearestValue(T, basyo1) -basyo1)

        # 2:寺先
        basyo2 = getNearestValue(T, X[i])
        dist2 = abs(basyo2 - X[i])
        dist2 += abs(getNearestValue(S, basyo2) -basyo2)

        ans += min(dist1, dist2)
        print(ans)


main()

### FIXED CODE ###

import bisect

A, B, Q = map(int, input().split())  # 複数数値入力
S = [0] * A
T = [0] * B
X = [0] * Q
for i in range(A):
    S[i] = int(input())
for i in range(B):
    T[i] = int(input())
for i in range(Q):
    X[i] = int(input())

S.insert(0, -float("inf"))
S.append(float("inf"))
T.insert(0, -float("inf"))
T.append(float("inf"))

for i in range(Q):
    b = bisect.bisect_right(S, X[i])
    d = bisect.bisect_right(T, X[i])
    res = float("inf")
    for s in [S[b - 1], S[b]]:
        for t in [T[d - 1], T[d]]:
            d1 = abs(s - X[i]) + abs(t - s)  # 先に神社
            d2 = abs(t - X[i]) + abs(t - s)  # 先に寺
            res = min(res, d1, d2)

    print(res)
### BUGGY CODE ###

def main():
    n, k = tuple([int(e) for e in input().split()])
    arr = [0] + [int(e) for e in input().split()]

    seen = set()
    actual = 1
    seen.add(1)
    while k > 0:
        actual = arr[actual]
        k -= 1
        if actual in seen:
            break
        seen.add(actual)

    c = 1
    ac = arr[actual]
    while actual != ac:
        ac = arr[ac]
        c += 1

    k = k % c
    while k > 0:
        actual = arr[actual]
        k -= 1
    print(actual)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n, k = tuple([int(e) for e in input().split()])
    arr = [0] + [int(e) for e in input().split()]

    seen = set()
    actual = 1
    seen.add(1)
    pos = [1]
    mp = {1:1}
    while k > 0:
        actual = arr[actual]
        k -= 1
        if actual in seen:
            break
        seen.add(actual)
        pos.append(actual)
        mp[actual] = len(pos)

    c = 1 + len(pos) - mp[actual]
    k = k % c
    print(pos[mp[actual] + k - 1])

if __name__ == '__main__':
    main()