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

from collections import deque
h, w, k = map(int, input().split())
y1, x1, y2, x2 = map(int, input().split())
c = []
for _ in range(h):
    c.append(input())
q = deque([(x1-1, y1-1)])
dxdy = [(-1,0), (0,-1), (0,1), (1,0)]
dist = [[1000000]*w for _ in range(h)]
dist[y1-1][x1-1] = 0
while q:
    x, y = q.popleft()
    for ddx, ddy in dxdy:
        for i in range(1, k+1):
            dx = ddx*i
            dy = ddy*i
            if not (0<=x+dx<w and 0<=y+dy<h):
                break
            if c[y+dy][x+dx]=='@':
                break
            if x+dx==x2-1 and y+dy==y2-1:
                print(dist[y][x]+1)
                exit(0)
            if dist[y+dy][x+dx]>dist[y][x]+1:
                dist[y+dy][x+dx] = dist[y][x]+1
                q.append((x+dx, y+dy))
print(-1)

### FIXED CODE ###

from collections import deque
h, w, k = map(int, input().split())
y1, x1, y2, x2 = map(int, input().split())
c = []
for _ in range(h):
    c.append(input())
q = deque([(x1-1, y1-1)])
dxdy = [(-1,0), (0,-1), (0,1), (1,0)]
dist = [[1000000]*w for _ in range(h)]
dist[y1-1][x1-1] = 0
while q:
    x, y = q.popleft()
    for ddx, ddy in dxdy:
        for i in range(1, k+1):
            dx = ddx*i
            dy = ddy*i
            if not (0<=x+dx<w and 0<=y+dy<h):
                break
            if c[y+dy][x+dx]=='@' or dist[y+dy][x+dx]<=dist[y][x]:
                break
            if x+dx==x2-1 and y+dy==y2-1:
                print(dist[y][x]+1)
                exit(0)
            if dist[y+dy][x+dx]>dist[y][x]+1:
                dist[y+dy][x+dx] = dist[y][x]+1
                q.append((x+dx, y+dy))
print(-1)
### BUGGY CODE ###

import sys
from bisect import bisect_left, bisect_right, insort

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
S = list('-' + sr())
d = [[] for _ in range(26)]
for i in range(1, N+1):
    s = S[i]
    o = ord(s) - ord('a')
    insort(d[o], i)

Q = ir()
for _ in range(Q):
    q, a, b = sr().split()
    if q == '1':
        a = int(a)
        if S[a] == b:
            continue
        prev = ord(S[a]) - ord('a')
        d[prev].remove(a)
        next = ord(b) - ord('a')
        insort(d[next], a)
        S[a] = b
    else:
        a = int(a); b = int(b)
        ans = 0
        for alpha in range(26):
            if bisect_right(d[alpha], b) - bisect_left(d[alpha], a) >= 1:
                ans += 1
        print(ans)

# 17

### FIXED CODE ###

import sys
from bisect import bisect_left, bisect_right, insort

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
S = list('-' + sr())
d = [[] for _ in range(26)]
for i in range(1, N+1):
    s = S[i]
    o = ord(s) - ord('a')
    insort(d[o], i)

Q = ir()
for _ in range(Q):
    q, a, b = sr().split()
    if q == '1':
        a = int(a)
        if S[a] == b:
            continue
        prev = ord(S[a]) - ord('a')
        d[prev].remove(a)
        next = ord(b) - ord('a')
        insort(d[next], a)
        S[a] = b
    else:
        a = int(a); b = int(b)
        ans = 0
        for alpha in range(26):
            if bisect_right(d[alpha], b) - bisect_left(d[alpha], a) >= 1:
                ans += 1
        print(ans)

# 17
### BUGGY CODE ###

N,u,v = map(int, input().split())
G=[[] for i in range(N)]
for i in range(N-1):
    s,t = map(int, input().split())
    G[s-1].append(t-1)
    G[t-1].append(s-1)

"""
for i in range(len(G[u])):
    k=G[u][i]
    D[k]=1
"""
def expro(u):
    D=[0]*N
    D[u]=0
    S=[]
    S.append(u)
    L=[]
    while(len(S)!=0):
        l=S[0]
        for i in range(len(G[l])):
            m=G[l][i]
            if(len(G[l])==1 and l!=u):
                L.append(l)
            if(D[m]==0 and m!=u):
                D[m]=D[l]+1
                S.append(m)
        S.remove(l)
    return L,D
L,D = expro(u-1)
M,E = expro(v-1)
k=0
ans=0
#print(G)
#print(D)
#print(L)
for i in M:
    if D[i]<E[i]:
        if k<E[i]:
            k=E[i]
            ans=E[i]-1
print(ans)


### FIXED CODE ###

N,u,v = map(int, input().split())
G=[[] for i in range(N)]
for i in range(N-1):
    s,t = map(int, input().split())
    G[s-1].append(t-1)
    G[t-1].append(s-1)


def expro(u):
    D=[0]*N
    D[u]=0
    S=[]
    S.append(u)
    L=[]
    q=0
    while(q<N):
        l=S[q]
        for i in range(len(G[l])):
            m=G[l][i]
            if(len(G[l])==1 and l!=u):
                L.append(l)
            if(D[m]==0 and m!=u):
                D[m]=D[l]+1
                S.append(m)
        #S.remove(l)
        q+=1
    return L,D
L,D = expro(u-1)
M,E = expro(v-1)
k=0
ans=0
#print(G)
#print(D)
#print(L)
for i in M:
    if D[i]<E[i]:
        if k<E[i]:
            k=E[i]
            ans=E[i]-1
print(ans)
### BUGGY CODE ###

def road(n):
  for _ in range(n):
    A,B = map(int,input().split())
    yield A,B
  
def main():
  N,M = map(int,input().split())
  h = list(map(int,input().split()))
  num = list(range(1,N+1))
  X = list(road(M))
  for A,B in X:
    if h[A-1] > h[B-1] and B in num:
      num.remove(B)
    elif h[A-1] < h[B-1] and A in num:
      num.remove(A)
    elif h[A-1] == h[B-1]:
      if A in num and B in num:
        num.remove(A)
        num.remove(B)
      elif A in num and not B in num:
        num.remove(A)
      elif B in num and not A in num:
        num.remove(B)
  return len(num)

print(main())

### FIXED CODE ###

n,m = map(int,input().split())
h = list(map(int,input().split()))
cnt = [0]*n
chk = [0]*n
ans = 0

for i in range(m):
  a,b = map(int, input().split())
  if h[a-1] > h[b-1]:
    cnt[a-1] += 1
  elif h[a-1] < h[b-1]:
    cnt[b-1] += 1
  chk[a-1] += 1
  chk[b-1] += 1
  
for i in range(n):
  if cnt[i] == chk[i]:
    ans += 1
    
print(ans)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
s = []
for _ in range(h):
    s.append(list(input()))
from collections import deque
def bfs(x, y):
    ans = 0
    d = [[float('inf')]*w for _ in range(h)]
    d[x][y] = 0
    queue = deque([(x, y)])

    while queue:
        x, y = queue.popleft()
        for i in range(-2, 3):
            for j in range(-2, 3):
                u = x + i
                v = y + j

                if 0 <= u < h and 0 <= v < w and s[u][v] == '.' and d[u][v] > d[x][y]:
                    if abs(i) + abs(j) <= 1:
                        d[u][v] = min(d[x][y], d[u][v])
                    else:
                        d[u][v] = min(d[u][v], d[x][y] + 1)
                    queue.append((u, v))
    return d

d = bfs(ch, cw)
if d[dh][dw] == float('inf'):
    print(-1)
else:
    print(d[dh][dw])

    


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
s = []
for _ in range(h):
    s.append(list(input()))
from collections import deque, defaultdict
def bfs(x, y):
    wp = defaultdict(list)
    d = [[-1] * w for _ in range(h)]
    d[x][y] = 0
    queue = deque([(x, y)])
    while queue:
        u, v = queue.popleft()
        wp[0].append((u, v))
        next_grid = [(u - 1, v), (u + 1, v), (u, v - 1), (u, v + 1)]
        for x, y in next_grid:
            if 0 <= x < h and 0 <= y < w and s[x][y] != '#' and d[x][y] < 0:
                d[x][y] = d[u][v]
                queue.append((x, y))
    for i in range(10**6):
        if len(wp[i]) == 0:
            break
        queue = deque([])
        for x, y in wp[i]:
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    u, v = x + dx, y + dy
                    if 0 <= u < h and 0 <= v < w and s[u][v] == '.' and d[u][v] < 0:
                        d[u][v] = i + 1
                        queue.append((u, v))
        while queue:
            u, v = queue.popleft()
            wp[i + 1].append((u, v))
            next_grid = [(u - 1, v), (u + 1, v), (u, v - 1), (u, v + 1)]
            for x, y in next_grid:
                if 0 <= x < h and 0 <= y < w and s[x][y] != '#' and d[x][y] < 0:
                    d[x][y] = d[u][v]
                    queue.append((x, y))
    return d

d = bfs(ch, cw)
print(d[dh][dw])
### BUGGY CODE ###

mod = 10**9+7
import sys
sys.setrecursionlimit(1000000)

N,M = [int(x) for x in input().split()]
a = [int(input()) for _ in range(M)]
di = {}
for i in a:
    di[i] = 1
dp = [0 for _ in range(N+1)]
dp[0] = 1

def dfs(num):
    if(num<0):
        return 0
    if(num==0):
        return 1
    if(num in di):
        return 0
    if(dp[num]==0):
        dp[num] = (dfs(num-1)+dfs(num-2))%mod
    return dp[num]

print(dfs(N))


### FIXED CODE ###

mod = 10**9+7
import sys
sys.setrecursionlimit(10000000)

N,M = [int(x) for x in input().split()]
a = [int(input()) for _ in range(M)]
di = {}
for i in a:
    di[i]=1
dp = [0 for _ in range(N+1)]
dp[0] = 1
for i in range(N+1):
    if(i in di):
        continue
    if(i<N-1):
        if(i+2 not in di):
            dp[i+2]+=dp[i]
            dp[i+2]%=mod
    if(i<N):
        if(i+1 not in di):
            dp[i+1]+=dp[i]
            dp[i+1]%=mod
print(dp[N])
### BUGGY CODE ###


class Solution:

    def solve(self, S: str, Q: int, Query) -> int:

        num_reverse = 0
        for q in Query:
            if int(q[0]) == 1:
                num_reverse += 1
            else:
                if (num_reverse + int(q[1])) % 2 == 0:
                    S = S + q[2]
                else:
                    S = q[2] + S

        if num_reverse % 2 == 1:
            S = S[::-1]

        return S


if __name__ == '__main__':

    # standard input
    S = input()
    Q = int(input())
    Query = []
    for _ in range(Q):
        Query.append(tuple(input().split()))

    # solve
    solution = Solution()
    print(solution.solve(S, Q, Query))


### FIXED CODE ###

# standard input
S = input()
Q = int(input())
Query = []
num_reverse = 0

L = ''
R = ''

rev = False

for _ in range(Q):

    q = tuple(map(str, input().split()))

    if q[0] == '1':
        rev = (not rev)

    else:
        if (rev and q[1] == '1') or (not rev and q[1] == '2'):
            R = R + q[2]
        else:
            L = q[2] + L 

if rev:
    print( R[::-1] + S[::-1] + L[::-1])
else:
    print( L + S + R )
### BUGGY CODE ###

###
n = int(input())
s = input()
ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            t1 = n-1
            u1 = n-1
            v1 = n-1
            for t in range(n):
                if i == int(s[t]):
                    t1 = t
                    break
            for u in range(t1+1,n):
                if j == int(s[u]):
                    u1 = u
                    break
            for v in range(u1+1,n):
                if k == int(s[v]):
                    v1 = v
                    break
            if int(s[t1]) == i and int(s[u1]) == j and int(s[v1]) == k and t1<u1 and u1<v1:
                #print(i,j,k,t1,u1,v1)
                ans += 1
print(ans) 
            
    

### FIXED CODE ###

#dp[i]:i+1桁目-n桁目で1桁の数字は/2桁の数字は/何通りあるか
n = int(input())
s = input()
ans = 0
for i in range(10):
    for j in range(10):
        t1 = n-1
        u1 = n-1
        for t in range(n):
            if i == int(s[t]):
                t1 = t
                break
        for u in range(t1+1,n):
            if j == int(s[u]):
                u1 = u
                break
        if int(s[t1]) == i and int(s[u1]) == j and t1<u1:
            #print(i,j,k,t1,u1,v1)
            ans += len(set(s[u1+1:]))
print(ans)
### BUGGY CODE ###

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

d = M//N
while d >= 1:
    if M%d == 0:
        print(d)
        break
    else:
        d -= 1

### FIXED CODE ###

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

d = int(M**(1/2))
div_list = []
while d >= 1:
    if M%d == 0:
        div_list.append(d)
        div_list.append(M//d)
    d -= 1

div_list.sort(reverse = True)
for i in range(len(div_list)):
    if div_list[i] <= M//N:
        print(div_list[i])
        break
### BUGGY CODE ###

MOD = int(1e9)+7
#nCr
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

n,k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
ans = 0
for i in range(k+1):
    if n-1-i<k-1:
        break
    b = cmb(n-1-i,k-1)
    ans += b*a[n-1-i]
    ans -= b*a[i]
    ans = ans%MOD
print(ans)

### FIXED CODE ###

import math
n_ = 10**5 + 3
mod = 10**9+7
fun = [1]*(n_+1)
for i in range(1,n_+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n_+1)
rev[n_] = pow(fun[n_],mod-2,mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod
def nCr(n,r):
    if n <= 0 or r < 0 or r > n: return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
count=0
for i in range(N-K+1):
    count=(count+((A[i]-A[N-1-i])*nCr(N-i-1,K-1)))%(10**9+7)
print(count)
### BUGGY CODE ###

from itertools import combinations
N = int(input())
A = list(map(int, input().split()))
memo = [0]*(N+1)
for i in range(1, N+1):
    memo[i] = memo[i-1] + A[i-1]

cnt = 0
for c in combinations(memo, 2):
    if c[0] == c[1]:
        cnt += 1

print(cnt)

### FIXED CODE ###

from collections import Counter
from math import factorial

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

cnt = 0
C = Counter(memo)

for c in C.values():
    if c > 1:
        cnt += (factorial(c)/(2*factorial(c-2)))

print(int(cnt))
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
dp=[0]*61
for i in range(N):
  a=len(bin(A[i]))-2
  for j in range(a):
    if A[i]&1==1:
      dp[j]+=1
    A[i]=A[i]>>1
ans=0
mod=10**9+7
for i in range(60,-1,-1):
  ans+=pow(2,i)*dp[i]*(N-dp[i])
  ans%=mod
print(ans)

### FIXED CODE ###

def main():
  N=int(input())
  A=list(map(int,input().split()))
  mod=10**9+7
  ans=0
  for i in range(60):
    c=0
    for j in A:
      if j>>i&1:
        c+=1
    ans+=pow(2,i,mod)*c*(N-c)
    ans%=mod
  print(ans)
if __name__=='__main__':
  main()
### BUGGY CODE ###

def solve(n, a):
    a = sorted(a)
    return max(f(n, a), f(n, a[::-1]))

def f(n, a):
    a = a.copy()
    b = []
    for i in range(n):
        if (i-1) % 4 < 2:
            v = a.pop(0)
        else:
            v = a.pop()
        if i % 2 == 0:
            b = [v] + b
        else:
            b = b + [v]
    return sum([abs(b[i+1]-b[i]) for i in range(n-1)])

n = int(input())
a = [int(input()) for i in range(n)]
print(solve(n, a))

### FIXED CODE ###

from collections import deque

def solve(n, a):
    a = sorted(a)
    return max(f(n, a), f(n, a[::-1]))

def f(n, a):
    a = deque(a)
    b = deque([])
    for i in range(n):
        if (i-1) % 4 < 2:
            v = a.popleft()
        else:
            v = a.pop()
        if i % 2 == 0:
            b.appendleft(v)
        else:
            b.append(v)
    return sum([abs(b[i+1]-b[i]) for i in range(n-1)])

n = int(input())
a = [int(input()) for i in range(n)]
print(solve(n, a))
### BUGGY CODE ###

from numba import jit

N=int(input())
S=input()
R=0
G=0
B=0
for i in range(N):
    s=S[i]
    if s=="R":
        R+=1
    elif s=="G":
        G+=1
    else:
        B+=1
ans=R*G*B

@jit
def calc(ans):
    for i in range(N-2):
        for j in range(i+1, N-1):
            if 0<=j+j-i<N:
                si=S[i]
                sj=S[j]
                sk=S[2*j-i]
                if si!=sj and sj!=sk and sk!=si:
                    ans-=1
    return ans
print(calc(ans))


### FIXED CODE ###

N=int(input())
S=input()
count=0
R=0
G=0
B=0
for i in range(N):
  if S[i]=="R":
    R+=1
  if S[i]=="G":
    G+=1
  if S[i]=="B":
    B+=1
count=0
for i in range(N-2):
  for j in range(i,N-1):
    k=j+j-i
    try:
      if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
        count+=1
    except:
      pass
    
print(R*G*B-count)
### BUGGY CODE ###

n = int(input())
for a in range(n):
    breaked = True
    for b in range(-n, n):
        if a**5 - b**5 == n:
            print(a, b)
            break;
    else:
        breaked = False
    if breaked:
        break


### FIXED CODE ###

n = int(input())
for a in range(n):
    breaked = True
    for b in range(-1000, 1000):
        if a**5 - b**5 == n:
            print(a, b)
            break;
    else:
        breaked = False
    if breaked:
        break
### BUGGY CODE ###

import itertools

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

mod = 10**9 + 7

ans=0
for i,j in itertools.combinations(l, 2):
  num=i*j
  ans+=num
  
print(ans%mod)


### FIXED CODE ###

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

sum_l=sum(l)
ans=0
mod=10**9+7

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

from itertools import combinations
from decimal import Decimal
import math
from functools import lru_cache


@lru_cache(maxsize=None)
def solve(a, b):
    x = a * b
    return int(x) == math.ceil(x)


n = int(input())
arr = [Decimal(input()) for _ in range(n)]


ans = []
for x, y in combinations(arr, 2):
    ans.append(solve(x, y))

print(sum(ans))

### FIXED CODE ###

def div(n, d):
    cnt = 0
    while n % d == 0 and cnt < 18:
        n //= d
        cnt += 1
    return cnt


n = int(input())
dp = [[0]*19 for _ in range(19)]

ans = 0
for _ in range(n):
    x = round(float(input()) * pow(10, 9))
    two = div(x, 2)
    five = div(x, 5)
    ans += dp[18 - two][18 - five]
    for i in range(two + 1):
        for j in range(five + 1):
            dp[i][j] += 1

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

import math
from heapq import heapify, heappop, heappush

LI = lambda: list(map(int, input().split()))

N, K = LI()
A = LI()


def main():
    hq = [(-a, -a, 1) for a in A]
    heapify(hq)
    for _ in range(K):
        x = heappop(hq)
        t = (x[1] / (x[2] + 1), x[1], x[2] + 1)
        heappush(hq, t)
    
    ans = math.ceil(-heappop(hq)[0])
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import math

LI = lambda: list(map(int, input().split()))

N, K = LI()
A = LI()


def judge(x):
    k = 0
    for a in A:
        if a <= x:
            continue
        if a % x == 0:
            k += a // x - 1
        else:
            k += a // x
    if k <= K:
        return True
    else:
        return False


def solve():
    left, right = 0, max(A)
    while right - left > 1:
        x = (left + right) // 2
        if judge(x):
            right = x
        else:
            left = x
    return right


def main():
    ans = solve()
    print(ans)


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

s = input()
N = len(s)

def f(c):
    for i in range(N):
        for j in range(i, N):
            if int(s[i:j+1])%2019 == 0:
                c += 1 
    print(c)
f(0)


### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d %= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

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

ans = int(A[N])

while N > 0:
    ans = ans * A[N-1]
    N = N-1

if ans > 10 ** 18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

ans = int(A[N])

if 0 in A:
    ans = 0
else:
    while N > 0:
        ans = ans * A[N-1]
        N = N-1
        if ans > 10 ** 18:
            N = 0
        else:
            N = N

if ans > 10 ** 18:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

n = int(input())
res = 1
a = map(int, input().split())
for x in a:
    res *= x
if res > 1e18:
    res = -1
print(res)


### FIXED CODE ###

def solve():
    _ = int(input())
    a = list(map(int, input().split()))
    res = 1
    for x in a:
        if x == 0:
            print(0)
            return
    for x in a:
        res *= x
        if res > int(1e18):
            print(-1)
            return
    print(res)


solve()
### BUGGY CODE ###

n = int(input())

num_list = list(map(int, input().split()))

ans = 1;
for num in num_list:
    ans = ans * num

if ans > 1000000000000000000:
    ans = -1

print(ans)


### FIXED CODE ###

n = int(input())

num_list = list(map(int, input().split()))

ans = 1;
for num in num_list:
    ans *= num
    if ans > 1000000000000000000:
        ans = -1
        break

if 0 in num_list:
    ans = 0

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

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

now=1
visited=[1]

for i in range(k):
  now=a[now-1]
  if now in visited:
    for j in range(1,len(visited)+1):
      if visited[-j]==now:
        t=j
        for i in range((k-(len(visited)-j)%t)):
          now=a[now-1]
        print(now)
        exit()
  
  visited.append(now)
        
print(now)

### FIXED CODE ###

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

now=0
visited=set()
visited.add((0))
visited2=[0]


while True:
  k-=1
  now=a[now]-1

  if k==0:
    print(now+1)
    exit()

  
  if now in visited:
    visited.add((now))
    visited2.append(now)
    break

  visited.add((now))
  visited2.append(now)


xxx=visited2[-1]
cnt=[]
for i in range(len(visited2)):
  if visited2[i]==xxx:
    cnt.append(i)


k%=cnt[1]-cnt[0]


if k!=0:
  for i in range(k):
    now=a[now]-1
  

print(now+1)
### BUGGY CODE ###

N,Q=[int(i) for i in input().rstrip().split()]
S = input().strip()
lr_list=[[int(j) for j in input().split()] for i in range(Q)]

for l,r in lr_list:
    
    cnt=0
    for i in range((l-1),r-1):
        if S[i]+S[i+1] == "AC":
            cnt += 1
        
    print(cnt)


### FIXED CODE ###

N,Q=[int(i) for i in input().rstrip().split()]
S = input().strip()
lr_list=[[int(j) for j in input().split()] for i in range(Q)]

calc_cnt=[0]
for i in range(1,len(S)):
    sub_str = S[(i-1):(i+1)]
    
    if sub_str == "AC":
        calc_cnt += [calc_cnt[i-1] + 1]
    else:
        calc_cnt += [calc_cnt[i-1]]
        

for l,r in lr_list:
    ans = calc_cnt[r-1] - calc_cnt[l-1]
    print(ans)