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

def main():
    h,w = map(int,input().split())
    S = [[] for i in range(h)]
    B = []
    cnt = 0
    for i in range(h):
        s = input()
        for j in range(w):
            S[i].append(s[j])
            if s[j]=='#':
                B.append([i,j])
                cnt += 1
    ans = 0
    while cnt<h*w:
        ans += 1
        B_ = []
        while len(B)>0:
            b = B.pop(0)
            if b[0]>0:
                if S[b[0]-1][b[1]]=='.':
                    cnt += 1
                    S[b[0]-1][b[1]]='#'
                    B_.append([b[0]-1,b[1]])
            if b[0]<h-1:
                if S[b[0]+1][b[1]]=='.':
                    cnt += 1
                    S[b[0]+1][b[1]]='#'
                    B_.append([b[0]+1,b[1]])
            if b[1]>0:
                if S[b[0]][b[1]-1]=='.':
                    cnt+=1
                    S[b[0]][b[1]-1]='#'
                    B_.append([b[0],b[1]-1])
            if b[1]<w-1:
                if S[b[0]][b[1]+1]=='.':
                    cnt += 1
                    S[b[0]][b[1]+1]='#'
                    B_.append([b[0],b[1]+1])
        B = B_
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque
def main():
    h,w = map(int,input().split())
    S = [list(input()) for i in range(h)]
    q = [(i,j) for i,a in enumerate(S) for j,b in enumerate(a) if b=='#']
    q = deque(q)
    ans = 0
    s = h*w
    cnt = len(q)
    nxt = [(0,1),(1,0),(-1,0),(0,-1)]
    while cnt < s:
        ans += 1
        q_ = deque([])
        while q:
            a,b = q.pop()
            for x,y in nxt:
                X,Y = a+x,b+y
                if 0>X or X>h-1 or 0>Y or Y>w-1:
                    continue
                if S[X][Y]=='.':
                    S[X][Y]='#'
                    q_.append((X,Y))
        q = q_
        cnt += len(q_)
    print(ans)

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

n=int(input())
a=[[0]*n]*n
l=[]

for i in range(n):
  a[i]=[int(x)-1 for x in input().split()]

t=0
f=True
while f==True:
  f=False
  for i in range(n):
    if len(a[i])>0:
      f=True
      j=a[i][0]
      if i<j:
        if i==a[j][0]:
          l.append(i)
          l.append(j)

  if f==False:
    break

  t = t+1 if len(l)>0 else -1
  if len(l)==0:
    break;
  for i in range(len(l)):
    a[l.pop(0)].pop(0)

print(t)


### FIXED CODE ###

from collections import deque

def main():
  N=int(input())
  A=[deque(int(a)-1 for a in input().split()) for _ in range(N)]

  P,W=[0]*N,[-1]*N
  c=deque(range(N))

  while c:
    i=c.popleft()
    j=A[i].popleft()
    W[i]=j

    if W[j]==i:
      P[i]=P[j]=max(P[i],P[j])+1
      if A[i]:
        c.append(i)
      if A[j]:
        c.append(j)

  print(-1 if any(len(a) for a in A) else max(P))

main()
### BUGGY CODE ###

N, K = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]

inf = float("inf")
cost = [inf]*N

cost[0] = 0
for i in range(N):
  for step in range(1, K+1):
    if i + step < N:
      cost[i+step] = min(cost[i+step], cost[i] + abs(h[i] - h[i+step]))

print(cost[-1])

### FIXED CODE ###

def main_B1():
  N, K = [int(i) for i in input().split()]
  h = [int(i) for i in input().split()]

  inf = float("inf")
  cost = [inf]*N


  cost[0] = 0
  for i in range(1, N):
    cost[i] = min([cost[j] + abs(h[i] - h[j]) for j in range(max(0, i-K), i)])
  print(cost[-1])

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

n = int(input())

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

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

a = [0] + a

ans = 0

for i in range(1,n+1):
    for j in range(i):
        if a[i] - a[j] == 0:
            ans += 1

print(ans)

### FIXED CODE ###

from collections import defaultdict

n = int(input())

a = [0] + [int(x) for x in input().split()]

d = defaultdict(int)

tmp = 0

for x in a:
    tmp += x
    d[tmp] += 1

ans = 0

for k,v in d.items():
    if v >= 2:
        ans += v * (v - 1) // 2

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

N, Q = map(int, input().split())
ruisekiwa = [0] * (N + 1)
lists = []
S = str(input())
for t in range(1, len(S)):
    if S[t - 1] == "A" and S[t] == "C":
        for k in range(t, len(ruisekiwa)):
            ruisekiwa[k] += 1
for i in range(Q):
    l, r = map(int, input().split())
    ans = ruisekiwa[r - 1] - ruisekiwa[l - 1]
    lists.append(ans)
for m in range(len(lists)):
    print(lists[m])


### FIXED CODE ###

N, Q = map(int, input().split())
ruisekiwa = [0]
lists = []
cnt = 0
S = str(input())
for t in range(1, N):
    if S[t - 1] == "A" and S[t] == "C":
        cnt += 1
    ruisekiwa.append(cnt)
ruisekiwa.append(cnt)
for i in range(Q):
    l, r = map(int, input().split())
    ans = ruisekiwa[r - 1] - ruisekiwa[l - 1]
    lists.append(ans)
for m in range(len(lists)):
    print(lists[m])
### BUGGY CODE ###

import math
num = int(input())
count = 0
for a in range(1,num+1):
    for b in range(1,num+1):
        for c in range(1,num+1):
            temp = math.gcd(a,b)
            count += math.gcd(temp,c)
print(count)

### FIXED CODE ###

import math
num = int(input())
count = 0
for a in range(1,num+1):
    for b in range(1,num+1):
        temp = math.gcd(a,b)
        for c in range(1,num+1):
            count += math.gcd(temp,c)
print(count)
### BUGGY CODE ###

from collections import deque

G = dict()
N, M = map(int, input().split())
color = [0]*(N+1)
for n in range(1, N+1):
    G[n] = []
for _ in range(M):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
Q = int(input())




for _ in range(Q):
    v, d, c = map(int, input().split())
    # BFS
    dist = dict()
    deq = deque([v])
    color[v] = c
    dist[v] = 0
    while len(deq) > 0:
        s = deq.popleft()
        if dist[s] >= d:
            break
        for t in G[s]:
            if t in dist.keys():
                pass
            else:
                dist[t] = dist[s] + 1
                color[t] = c
                deq.append(t)
                
for n in range(1, N+1):
    print(color[n])
                


### FIXED CODE ###

from collections import deque

G = dict()
N, M = map(int, input().split())
color = [0]*(N+1)
for n in range(1, N+1):
    G[n] = []
for _ in range(M):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
Q = int(input())




data = [list(map(int, input().split())) for _ in range(Q)]
data.reverse()
color_d = [-1]*(N+1)

for v, d, c in data:
    if color_d[v] >= d:
        pass
    # BFS
    deq = deque([v])
    if color[v] == 0:
        color[v] = c
    color_d[v] = d
    while len(deq) > 0:
        s = deq.popleft()
        for t in G[s]:
            if color_d[t] >= color_d[s] - 1:
                pass
            else:
                color_d[t] = color_d[s] - 1
                if color[t] == 0:
                    color[t] = c
                if color_d[t] > 0:
                    deq.append(t)
                
for n in range(1, N+1):
    print(color[n])
### BUGGY CODE ###

s = list(input())
q = int(input())
for i in range(q):
    x = list(input().split())
    if x[0]=='1':
        s.reverse()
    else:
        if x[1]=='1': s = [x[2]]+s
        else: s = s+[x[2]]
print(''.join(s))

### FIXED CODE ###

s = list(input())
q = int(input())
a = []
f = False #さかさま
for i in range(q):
    x = list(input().split())
    if x[0]=='1':
        f = not f
    else:
        if f:
            if x[1]=='1': s.append(x[2])
            else: a.append(x[2])
        else:
            if x[1]=='1': a.append(x[2])
            else: s.append(x[2])
a.reverse()
s = a+s
if f:s.reverse()
print(''.join(s))
### BUGGY CODE ###

import sys
S = input()
Q = int(input())
key = 1

for i in sys.stdin:
    if i[0] == '1':
        key = -key
    
    elif (i[2] == '1' and key == 1) or (i[2] == '2' and key == -1):
        S = i[4] + S
    else:
        S = S + i[4]


print(S[::key])

### FIXED CODE ###

import sys
S = input()
Q = int(input())
key = 1

for i in sys.stdin:
    if i[0] == '0':
        break

    if i[0] == '1':
        key = -key
    
    elif key == 1:
        if i[2] == '1':
            S = i[4] + S
        else:
            S = S + i[4]

    else:
        if i[2] == '2':
            S = i[4] + S
        else:
            S = S + i[4]


print(S[::key])
### BUGGY CODE ###

def comb(n):
    if n<=1:return 0
    r=1
    for i in range(n,n-2,-1):
       r*=i
    return r//2
stdin =open(0).read().split('\n')
N=int(stdin[0])
A=list(map(int,stdin[1].split()))
d=dict(zip(set(A), [0]*len(set(A))))
for i in set(A):
    d[i]=A.count(i)
for j in range(N):
    ans=0
    for k, v in d.items():
        if A[j]==k:
            ans+=comb(v-1)
        else:
            ans+=comb(v)
    print(ans)

### FIXED CODE ###

stdin =open(0).read().split('\n')
N=int(stdin[0])
A=list(map(int,stdin[1].split()))
from collections import Counter
C=Counter(A)
ans=0
for i in C.values():
    ans+=i*(i-1)//2
for a in A:
    num = C[a]
    print(ans-num*(num-1)//2+(num-1)*(num-2)//2)
### BUGGY CODE ###

from collections import defaultdict
import heapq


class Dijkstra:
    def __init__(self):
        self.e = defaultdict(list)

    def add(self, u, v, d, directed=False):
        if directed is False:
            self.e[u].append([v, d])
            self.e[v].append([u, d])
        else:
            self.e[u].append([v, d])

    def delete(self, u, v):
        self.e[u] = [_ for _ in self.e[u] if _[0] != v]
        self.e[v] = [_ for _ in self.e[v] if _[0] != u]

    def search(self, s):
        d = defaultdict(lambda: float('inf'))
        d[s] = 0
        q = []
        heapq.heappush(q, (0, s))
        v = defaultdict(bool)
        while len(q):
            k, u = heapq.heappop(q)
            if v[u]:
                continue
            for uv, ud in self.e[u]:
                if v[uv]:
                    continue
                vd = k + ud
                if d[uv] > vd:
                    d[uv] = vd
                    heapq.heappush(q, (vd, uv))
        return d


N, M, S, T = map(int, input().split())
UVAB = [list(map(int, input().split())) for i in range(M)]
graph1 = Dijkstra()
graph2 = Dijkstra()

for u, v, a, b in UVAB:
    graph1.add(u, v, a)
    graph2.add(u, v, b)

result_a = graph1.search(S)
result_b = graph2.search(T)

ans_list = [float('inf')]

for i in range(N, 0, -1):
    cur = result_a[i] + result_b[i]
    if cur > ans_list[-1]:
        cur = ans_list[-1]
    ans_list.append(cur)

for i in range(len(ans_list[1:])):
    print(10 ** 15 - ans_list[-(i + 1)])


### FIXED CODE ###

from collections import defaultdict
from heapq import heappop, heappush
import sys
input = sys.stdin.readline


class Dijkstra:
    def __init__(self):
        self.edge = defaultdict(list)

    def add(self, u, v, d):
        self.edge[u].append([v, d])
        self.edge[v].append([u, d])

    def search(self, start):
        distance = defaultdict(lambda: float("inf"))
        distance[start] = 0
        queue = []
        heappush(queue, (0, start))
        seen = set()
        while queue:
            k, u = heappop(queue)
            if u in seen:
                continue
            seen.add(u)

            for v, d in self.edge[u]:
                if v in seen:
                    continue
                new_d = k + d
                if distance[v] > new_d:
                    distance[v] = new_d
                    heappush(queue, (new_d, v))
        return distance


n, m, s, t = map(int, input().split())
uvab = [list(map(int, input().split())) for _ in range(m)]
graph1 = Dijkstra()
graph2 = Dijkstra()

for u, v, a, b in uvab:
    graph1.add(u, v, a)
    graph2.add(u, v, b)

result_a = graph1.search(s)
result_b = graph2.search(t)
ans_list = [float('inf')]

for i in range(n, 0, -1):
    cur = result_a[i] + result_b[i]
    if cur > ans_list[-1]:
        cur = ans_list[-1]
    ans_list.append(cur)

for ans in ans_list[n:0:-1]:
    print(10 ** 15 - ans)
### BUGGY CODE ###

n = int(input())
s = list(map(int, input().split()))
q = int(input())
t = list(map(int, input().split()))

count = 0
for item in t:
    middle = int((n - 1) / 2)
    upper = n - 1
    lower = 0
    while(True):
        if s[middle] == item:
            count += 1
            break
        elif upper == lower:
            break
        elif s[middle] > item:
            upper = middle
            middle = int((lower + middle) / 2)
        elif s[middle] < item:
            lower = middle
            middle = int((upper + middle) / 2)

print(count)

### FIXED CODE ###

n = int(input())
s = list(map(int, input().split()))
q = int(input())
t = list(map(int, input().split()))

count = 0
for item in t:
    middle = int((n - 1) / 2)
    upper = n - 1
    lower = 0
    while(True):
        if s[middle] == item:
            count += 1
            break
        elif lower >= upper:
            break
        elif s[middle] > item:
            upper = middle
            middle = int((lower + lower) / 2)
        elif s[middle] < item:
            lower = middle + 1
            middle = int((upper + lower) / 2)

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

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]

mod = 10**9+7

dp = [0] * -~n
dp[0] = 1
dp[1] = 0 + (1 not in a)

for i in range(2, -~n):
    if i in a:
        continue
    dp[i] = (dp[i - 1] + dp[i - 2]) % mod

print(dp[n])

### FIXED CODE ###

n, m = map(int, input().split())
a = set([int(input()) for _ in range(m)])

mod = 10**9+7

dp = [0] * -~n
dp[0] = 1
dp[1] = 0 + (1 not in a)

for i in range(2, -~n):
    if i in a:
        continue
    dp[i] = (dp[i - 1] + dp[i - 2]) % mod

print(dp[n])
### BUGGY CODE ###

from collections import deque
n=int(input())
a = [[0]*n for _ in range(n)]
visited = [0] * n
col = [1]*n
que = deque()

for i in range(n-1):
    u,v,d = map(int, input().split())
    a[u-1][v-1]=a[v-1][u-1]=d

#方針：貪欲に
for i in range(n):
    if a[0][i]!=0:
        que.append([i, a[0][i], 0])
        visited[i]=1

while que:
    x = que.pop()
    for i in range(n):
        if a[x[0]][i]!=0 and not visited[i]:
            que.append([i, a[x[0]][i], x[0]])
            visited[i]=1
    if x[1]%2 == 0:
        col[x[0]]=col[x[2]]
    else:
        col[x[0]]=(col[x[2]])*-1

for i in range(n):
    print(max(col[i], 0))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
n=int(input())
a = [[]*n for _ in range(n)]
visited = [0] * n
dist = [0]*n
col = [1]*n

def dfs(i:"int", c:"int"):
    for j in a[i]:
        if not visited[j[0]]:
            visited[j[0]]=1
            if j[1]%2==0:
                col[j[0]]=c
            else:
                col[j[0]]=c*-1
            dfs(j[0], col[j[0]])



if __name__ == '__main__':
    for i in range(n-1):
        u,v,d = map(int, input().split())
        a[u-1].append([v-1, d])
        a[v-1].append([u-1, d])
    visited[0]=1
    dfs(0, 1)
    for i in range(n):
        print(col[i] if col[i]>0 else 0)
### BUGGY CODE ###

N = int(input())
count = 0
for i in range(N):
    count += i
print(count)

### FIXED CODE ###

from decimal import *
N = int(input())
print(int((Decimal(N-1)*Decimal(N))/Decimal(2)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
  h, w, k = map(int, input().split())
  U = h*w
  G = [0]*U
  for _ in range(k):
    r, c, v = map(int, input().split())
    r -= 1
    c -= 1
    G[r*w+c] = v
  dp = [[0]*4 for _ in range(U)]
  dp[0][0] = 0
  dp[0][1] = G[0]
  for i in range(h):
    for j in range(w):
      if j:
        dp[i*w+j][0] = dp[i*w+j-1][0]
        for k in range(1, 4):
          dp[i*w+j][k] = max(dp[i*w+j][k], dp[i*w+j-1][k-1]+G[i*w+j], dp[i*w+j-1][k])
      if i:
        dp[i*w+j][0] = max(dp[i*w+j][0], max(dp[(i-1)*w+j]))
        dp[i*w+j][1] = max(dp[i*w+j][1], max(dp[(i-1)*w+j])+G[i*w+j])
  ans = max(dp[U-1])
  print(ans)
if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

h, w, k = map(int, input().split())
G = [[0]*w for _ in range(h)]
for _ in range(k):
  r, c, v = map(int, input().split())
  r -= 1
  c -= 1
  G[r][c] = v
dp = [[[0]*w for i in range(h)] for j in range(4)]
dp[0][0][0] = 0
dp[1][0][0] = G[0][0]
for i in range(h):
  for j in range(w):
    if j:
      dp[0][i][j] = dp[0][i][j-1]
      for k in range(1, 4):
        dp[k][i][j] = max(dp[k][i][j], dp[k-1][i][j-1]+G[i][j], dp[k][i][j-1])
    if i:
      dp[0][i][j] = max(dp[0][i][j], max(dp[0][i-1][j],dp[1][i-1][j],dp[2][i-1][j],dp[3][i-1][j]))
      dp[1][i][j] = max(dp[1][i][j], max(dp[0][i-1][j],dp[1][i-1][j],dp[2][i-1][j],dp[3][i-1][j])+G[i][j])
ans = max(dp[0][h-1][w-1],dp[1][h-1][w-1],dp[2][h-1][w-1],dp[3][h-1][w-1])
print(ans)
### BUGGY CODE ###

from collections import defaultdict
from collections import deque
import sys
sys.setrecursionlimit(10**6)

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

graph = defaultdict(deque)

for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

ans = [0] * (n + 1)

for i in range(q):
    p, x = map(int, input().split())
    ans[p] += x


def solve(graph, ans):
    curr, root = 1, -1

    def dfs(curr, root):
        stack = graph[curr]

        while stack:
            leaf = stack.pop()
            if leaf == root:
                continue
            ans[leaf] += ans[curr]
            dfs(leaf, curr)

        return ans

    return dfs(curr, root)


ans = solve(graph, ans)

print(*ans[1:])

### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

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

graph = defaultdict(set)

for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].add(b)
    graph[b].add(a)

arr = [0] * (n + 1)

for i in range(q):
    p, x = map(int, input().split())
    arr[p] += x


def solve():
    stack = [1]
    visited = [True] * 2 + [False] * (n - 1)

    while stack:
        curr = stack.pop()
        for leaf in graph[curr]:
            if visited[leaf]:
                continue
            stack.append(leaf)
            visited[leaf] = True
            arr[leaf] += arr[curr]

    return arr


arr = solve()

print(*arr[1:])
### BUGGY CODE ###

MOD = 10**9 + 7
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
dp = [[0] * (1 << N) for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
    for j in range(N):
        if A[i][j] != 1: continue
        bit = 1 << j
        for s in range(1 << N):
            if s & bit == 0:
                new_s = s | bit
                dp[i+1][new_s] += dp[i][s]
                dp[i+1][new_s] %= MOD
print(dp[N][(1 << N) - 1])

### FIXED CODE ###

MOD = 10**9 + 7
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
dp = [0] * (1 << N)
dp[0] = 1
bits = [1 << i for i in range(N)]
cands = [[] for _ in range(N+1)]
for s in range(1 << N):
    temp = 0
    for n in range(N):
        if s & (1 << n): temp += 1
    cands[temp].append(s)
for i, a in enumerate(A):
    for j in [k for k, v in enumerate(a) if v == 1]:
        bit = bits[j]
        for s in cands[i]:
            if s & bit == 0:
                new_s = s | bit
                dp[new_s] += dp[s]
                dp[new_s] %= MOD
print(dp[-1])
### BUGGY CODE ###

from collections import deque
 
n,k=map(int,input().split())
A=list(map(int,input().split()))
for i in range(min(k,50)):
    P=[]
    M=[]
    cnt=0
    for a in range(n):
        if A[a]==n:
            cnt+=1
            continue
        P.append(a-A[a])
        M.append(a+A[a]+1)
    P.sort()
    M.sort()
    P=deque(P)
    M=deque(M)
    C=[]
    m=n
    for j in range(n):
        if P:
            while P[0]<=j:
                P.popleft()
                cnt+=1
                if not P:
                    break
        if M:
            while M[0]<=j:
                M.popleft()
                cnt-=1
                if not M:
                    break
        C.append(cnt)
        m=min(cnt,m)
    A=C
    if m==n:
        break
print(*A)

### FIXED CODE ###

from collections import deque

n,k=map(int,input().split())
A=list(map(int,input().split()))
for i in range(min(k,50)):
    P=[]
    M=[]
    cnt=0
    for a in range(n):
        if A[a]==n:
            cnt+=1
            continue
        P.append(a-A[a])
        M.append(a+A[a]+1)
    P.sort()
    M.sort()
    P=deque(P)
    M=deque(M)
    C=[]
    m=n
    for j in range(n):
        if P:
            while P[0]<=j:
                P.popleft()
                cnt+=1
                if not P:
                    break
        if M:
            while M[0]<=j:
                M.popleft()
                cnt-=1
                if not M:
                    break
        C.append(cnt)
        m=min(cnt,m)
    A=C
    if m==n:
        break
print(*A)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
n = A.index(max(A))

for i in range(n):    
    print(max(A)) 
print(sorted(A)[-2])
for i in range(N-n-1):
    print(max(A))   

### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
n = A.index(max(A))
m = max(A)
A.remove(max(A))

for i in range(n):    
    print(m)
print(max(A))
for i in range(N-n-1):
    print(m)
### BUGGY CODE ###

import itertools

def main():
    N, M, R = map(int, input().split())
    RR = tuple(map(int, input().split()))
    ABC = {tuple(map(int, input().split())) for _ in range(M)}

    dist = [[float('inf') for i in range(N + 1)] for j in range(N + 1)]
    for a, b, c in ABC:
        dist[a][b] = dist[b][a] = c
    for k, i, j in itertools.product(range(1, N + 1), repeat=3):
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    ans = float('inf')
    for r in itertools.permutations(RR):
        move = 0
        for i in range(R - 1):
            a = r[i]
            b = r[i+1]
            move += dist[a][b]
        ans = min(ans, move)

    print(ans)

main()


### FIXED CODE ###

import itertools

def main():
    N, M, R = map(int, input().split())
    RR = tuple(map(int, input().split()))
    ABC = {tuple(map(int, input().split())) for _ in range(M)}

    dist = [[float('inf')] * (N + 1) for j in range(N + 1)]
    for a, b, c in ABC:
        dist[a][b] = dist[b][a] = c
        dist[a][a] = dist[b][b] = 0
    for k in range(1, N + 1):
        for i in range(1, N + 1):
            for j in range(1, N + 1):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    ans = float('inf')
    for r in itertools.permutations(RR):
        move = 0
        for i in range(R - 1):
            a = r[i]
            b = r[i+1]
            move += dist[a][b]
        ans = min(ans, move)

    print(ans)

main()
### BUGGY CODE ###

n = int(input())
tvote = 1
avote = 1

for i in range(n):
	t, a = [int(n) for n in input().split()]
	num = 1
	while True:
		tnow = num*t
		anow = num*a
		if tnow >= tvote and anow >= avote:
			tvote = tnow
			avote = anow
			break
		num += 1
	
print(tvote+avote)




### FIXED CODE ###

n = int(input())
tvote = 1
avote = 1

for i in range(n):
	t, a = [int(n) for n in input().split()]
	k = (tvote-1)//t + 1
	tnow = t * k
	anow = a * k
	if avote > anow:
		k = (avote-1)//a + 1
		tnow = t * k
		anow = a * k
	tvote = tnow
	avote = anow
	
print(avote+tvote)
### BUGGY CODE ###

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

loop_checker = [1]
before_loop_len = 0
loop_len = 0

now = 0
while True:
    if A[now] in loop_checker:
        before_loop_len = loop_checker.index(A[now])
        loop_slice = loop_checker[before_loop_len:]
        loop_len = len(loop_slice)
        break
    else:
        loop_checker.append(A[now])
        now = A[now] - 1
if K <= before_loop_len:
    print(loop_checker[K])
else:
    checkK_prep = (K - before_loop_len)
    checkK = checkK_prep % loop_len
    print(loop_slice[checkK])


### FIXED CODE ###

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

flag = [False] * N
counted = [1]

nextT = A[0]
flag[0] = True
for x in range(N):
    if flag[nextT - 1] is False:
        counted.append(nextT)
        flag[nextT - 1] = True
        nextT = A[nextT - 1]
    else:
        break
before_loop_len = counted.index(nextT)
loop_len = x - before_loop_len + 1

if K <= before_loop_len:
    print(counted[K])
else:
    checkK_prep = K - before_loop_len
    checkK = checkK_prep % loop_len
    print(counted[before_loop_len + checkK])