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

import itertools

n, k = map(int, input().split())
alist = sorted(list(map(int, input().split())))
mod = 10**9 + 7
memo = [[None]*k for _ in range(n)]

def comb(n, k, memo):
    if memo[n][k]:
        return memo[n][k]
    n1 = n+1
    r = min(k, n-k)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i)%mod
        denom = denom * i % mod
    
    memo[n][k] = numer * pow(denom, mod - 2, mod) % mod
    return memo[n][k]

    #return math.factorial(n) // (math.factorial(n-k) * math.factorial(k))

amax = 0
i = n-1
while i >= k-1:
    amax += alist[i] * comb(i, k-1, memo)
    i -= 1

amin = 0
i = 0
while i <= n-k:
    amin += alist[i] * comb(n-i-1, k-1, memo)
    i += 1
print((amax - amin) % mod)

### FIXED CODE ###

n, k = map(int, input().split())
alist = sorted(map(int, input().split()))
mod = 10**9 + 7

def comb(n, r, p=mod):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
p = mod
N = n
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

amax = 0
amin = 0
i = 0
while i <= n-k:
    cnt = comb(n-i-1, k-1)
    amax += (alist[n-i-1] * cnt)%mod
    amin += (alist[i] * cnt)%mod
    i += 1

print((amax - amin) % mod)
### BUGGY CODE ###

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

j = 0

for i in range(1,n+1):
  lii = sorted(li[0:i])
  if lii[0] == li[i-1]:
    j = j + 1
  if lii[0] == 1:
    break

print(j)

### FIXED CODE ###

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

i = 0
j = 0
a = 10**6
for i in range(i,n):
  a = min(a,li[i])
  if a == li[i]:
    j = j + 1

print(j)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, K: int, A: "List[int]"):
    score = 1
    for i in range(K):
        score *= A[i]

    prev_score = score
    for i in range(N-K):
        score = score // A[i] * A[i+K]
        if score>prev_score:
            print(YES)
        else:
            print(NO)
        prev_score = score
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, K: int, A: "List[int]"):
    for i in range(N-K):
        if A[i]<A[i+K]:
            print(YES)
        else:
            print(NO)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

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

a,b,n=map(int,input().split())

c=[]
m=0

for x in range(n+1):

    c.append(int(a*x/b)-a*int((x/b)))

    if int(c[x])>=m:

        m=int(c[x])

print(m)


### FIXED CODE ###

a,b,n=map(int,input().split())
#0<=x<=b-1でfloor(x/b)は0となるので単調増加になる
#単調増加なのでb-1とnの小さいほうがxの最大値
x=min(b-1,n)

print(a*x//b)
### BUGGY CODE ###

import math
import copy
import sys
import fractions
# import numpy as np
# import statistics
import decimal
import heapq
import collections
import itertools
import bisect

# from operator import mul

sys.setrecursionlimit(100001)


# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputIntList():
    outputDataList = []
    inputData = input().split()
    outputDataList = [int(n) for n in inputData]

    return outputDataList


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

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

n = int(input())


ans = 0
tmp_gcd={}
for i in range(1, n+1):
    for j in range(1, n+1):
        for k in range(1, n+1):
            ans += gcd(i,j,k)

print(ans)

### FIXED CODE ###

import math
import copy
import sys
import fractions
# import numpy as np
# import statistics
import decimal
import heapq
import collections
import itertools
import bisect

# from operator import mul

sys.setrecursionlimit(100001)


# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputIntList():
    outputDataList = []
    inputData = input().split()
    outputDataList = [int(n) for n in inputData]

    return outputDataList


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===


n = int(input())


ans = 0
dic = {}

for i in range(1, n+1):
    for j in range(1, n+1):
        tmp = math.gcd(i,j)
        if tmp in dic:
            dic[tmp] += 1
        else:
            dic[tmp] = 1

for key in dic:
    for i in range(1, n+1):
        ans += math.gcd(key, i) * dic[key]

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

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

rootGroups = []

for i in range(m):
  a, b = map(int, input().split())

  flag = False
  for j in range(len(rootGroups)):
    if a in rootGroups[j]:
      rootGroups[j].append(b)
      flag = True
    if b in rootGroups[j]:
      rootGroups[j].append(a)
      flag = True
  if not flag:
    rootGroups.append([a, b])

result = []

for i in range(len(rootGroups)):
  rootGroups[i] = list(dict.fromkeys(rootGroups[i]))

count = 0
for v in rootGroups:
  count += len(v)


print((len(rootGroups) - 1) + (n - count))



### FIXED CODE ###

import numpy as np

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
  n, m = map(int, input().split())

  union = UnionFind(n)

  for _ in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    union.union(a, b)

  print(union.group_count()-1)



main()
### BUGGY CODE ###

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

[n,m] = [int(i) for i in input().split()]
if n == 1:
    print(m)
else:
    ans = -1
    #a1は高々この値
    a1_max = m // n
    for i in range(a1_max,0,-1):
        ls = make_divisors(i)
        for j in ls:
            if (m - i) % j == 0 and (m - i)//j >= (n-1):
                ans = max(ans,j)
    print(ans)


### FIXED CODE ###

[n,m] = [int(i) for i in input().split()]
if n == 1:
    print(m)
else:
    ans = -1
    #a1は高々この値
    a1_max = m // n
    for i in range(a1_max,0,-1):
        if (m - i) % i == 0 and (m - i)//i >= (n-1):
            ans = max(ans,i)
    print(ans)
### BUGGY CODE ###

# coding: utf-8

import sys
import math
import collections
import itertools
from functools import lru_cache
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")

H, W = LI()
S = RS(H)

@lru_cache()
def dfs(x, y):
    stack = [[x, y-1, 1], [x+1, y, 2], [x, y+1, 3], [x-1, y, 4]]
    ret = 1

    while stack:
        x, y, dist = stack.pop()

        if not(0 <= x < W) or not(0 <= y < H) or S[y][x] == "#":
            continue

        ret += 1

        if dist == 1:
            stack.append([x, y-1, 1])
        elif dist == 2:
            stack.append([x+1, y, 2])
        elif dist == 3:
            stack.append([x, y+1, 3])
        else:
            stack.append([x-1, y, 4])
    
    return ret


ans = 0
for x in range(W):
    for y in range(H):
        if S[y][x] == ".":
            ans = max(ans, dfs(x, y))

print(ans)


### FIXED CODE ###

# coding: utf-8

import sys
import math
import collections
import itertools
from functools import lru_cache
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def gcd(x, y) : return y if x % y == 0 else gcd(y, x % y)
def lcm(x, y) : return (x * y) // gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")

H, W = LI()
S = RS(H)

L = [[0] * W for _ in range(H)]
R = [[0] * W for _ in range(H)]
U = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]

for i in range(H):
    lf = 0
    rf = 0
    for j in range(W):
        if S[i][j] == ".":
            lf += 1
            L[i][j] = lf
        else:
            lf = 0

        if S[i][W-1-j] == ".":
            rf += 1
            R[i][W-1-j] = rf
        else:
            rf = 0

for i in range(W):
    uf = 0
    df = 0
    for j in range(H):
        if S[j][i] == ".":
            df += 1
            D[j][i] = df
        else:
            df = 0

        if S[H-1-j][i] == ".":
            uf += 1
            U[H-1-j][i] = uf
        else:
            uf = 0

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            ans = max(ans, U[i][j]+D[i][j]+L[i][j]+R[i][j]-3)

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

import queue
import sys

sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline


def m():
    n, q = map(int, input().split())
    tree = [[] for _ in range(n + 1)]
    for i in range(1, n):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
    counter = [0] * (n + 1)
    for _ in range(q):
        p, x = map(int, input().split())
        counter[p] += x

    ans = [0] * (n + 1)
    que = queue.Queue()
    visited = []

    def bfs(root, base):
        base += counter[root]
        visited.append(root)
        for e in tree[root]:
            if e in visited:
                continue
            que.put(e)
            counter[e] += base

        while not que.empty():
            x = que.get()
            point = counter[x]
            visited.append(x)
            for e in tree[x]:
                if e in visited:
                    continue
                que.put(e)
                counter[e] += point

    bfs(1, 0)
    for i in range(1, n + 1):
        print(counter[i], '', end='')
    return ans


m()


### FIXED CODE ###

import queue
import sys
def input(): return sys.stdin.readline().rstrip()

def m():
    n, q = map(int, input().split())
    tree = [[] for _ in range(n + 1)]
    for i in range(1, n):
        a, b = map(int, input().split())
        tree[a].append(b)
        tree[b].append(a)
    counter = [0] * (n + 1)
    for _ in range(q):
        p, x = map(int, input().split())
        counter[p] += x

    que = queue.Queue()
    visited = [False] * (n+1)

    def bfs(root, base):
        base += counter[root]
        visited[root] = True
        for e in tree[root]:
            if visited[e]:
                continue
            que.put(e)
            counter[e] += base

        while not que.empty():
            x = que.get()
            point = counter[x]
            visited[x] = True
            for e in tree[x]:
                if visited[e]:
                    continue
                que.put(e)
                counter[e] += point

    bfs(1, 0)
    print(*counter[1:])
    return


m()
### BUGGY CODE ###

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

for i in range(M//N):
#    n = N-i
    n = M//N-i
    if M % n == 0:
#        if M//n >= N:
        print(n)
        break


### FIXED CODE ###

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

if N >= 1000:
    for i in range(M//N):
        n = (M//N)-i
        if M % n == 0:
            print(n)
            break
else:
    x = M//(M//N)
    for i in range(M):
        i = x +i
        if M % i == 0:
            print(M//i)
            break
### BUGGY CODE ###

N = int(input())
anser = 1
for a in input().split(" "):
    anser = anser * int(a)

if anser > 1000000000000000000:
    print(-1)
else:
    print(anser)


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))

    if 0 in A:
        print(0)
        return

    anser = 1
    for a in A:
        anser *= a
        if anser > 1000000000000000000:
            print(-1)
            return

    print(anser)

main()
### BUGGY CODE ###

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

def npsk_1(N, W):
    w, v = [0]*N, [0]*N 
    for _ in range(N):
        w[_], v[_] = map(int, input().split())
    
    dp = [[0]*(W+1) for _ in range(N+1)]
    
    for i in range(N):
        for j in range(W+1):
            if j - w[i] >= 0:
                dp[i+1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i])
            else:
                dp[i+1][j] = dp[i][j]
    
    print(dp[-1][-1])

npsk_1(N, W)

### FIXED CODE ###

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

w, v = [0] * N, [0] * N

for i in range(N):
	w[i], v[i] = map(int, input().split())

dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(N):
	for j in range(W + 1):
		if j - w[i] >= 0:
			dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i])
		else:
		    dp[i + 1][j] = dp[i][j] 

print(dp[N][W])
### BUGGY CODE ###

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


def ex(list):
    ans = 0
    for i in list:
        ans += (i+1)/2
    return(float(ans))


ans = 0
for i in range(N-K+1):
    p = pn[i:i+K]
    if ans < sum(p):
        maxlist = p
        ans = sum(p)

print('{:.12f}'.format(ex(maxlist)))


### FIXED CODE ###

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

pn_t = [0]
for i in range(N):
    pn_t.append(pn[i]+pn_t[i])

l = 0
for i in range(N-K+1):
    l = max(l, pn_t[K+i]-pn_t[i])
ans = (l+K)/2
print(ans)
### BUGGY CODE ###

N = int(input())
P_list = list(map(int,input().split()))
i_num = 0
for i in range(N):
    if P_list[i] <= min(P_list[:i+1]):
        i_num += 1
print(i_num)

### FIXED CODE ###

N = int(input())
P_list = list(map(int,input().split()))
i_num = 0
min_P = P_list[0]
for p in P_list:
    if p <= min_P:
        min_P = p
        i_num += 1
print(i_num)
### BUGGY CODE ###

from functools import lru_cache
def sub():
    N, W = [int(e) for e in input().split()]
    ww = []
    vv = []
    for _ in range(N):
        w, v = [int(e) for e in input().split()]
        ww.append(w)
        vv.append(v)
     
    @lru_cache(maxsize=None) 
    def dp(a_index, a_cum):
        if a_index == N:
            return 0
        w_next = a_cum+ww[a_index]
        if w_next <= W:
            a = dp(a_index+1, a_cum+ww[a_index]) + vv[a_index]
            b = dp(a_index+1, a_cum)
            return max(a,b)
        else:
            return dp(a_index+1, a_cum)

    print(dp(0, 0))

sub()


### FIXED CODE ###

def sub():
    N, W = [int(e) for e in input().split()]
    ww = []
    vv = []
    for _ in range(N):
        w, v = [int(e) for e in input().split()]
        ww.append(w)
        vv.append(v)
    
    # dp_table = [[0]*(W+1)]*(N+1)
    dp_table = [[0 for _ in range(W+1)] for _ in range(N+1)]
    # print(len(dp_table), len(dp_table[0]))
    for i in range(N):
        for j in range(W):
            w_next = j+ww[i]
            v_next = vv[i]
            if w_next <= W:
                dp_table[i+1][w_next] = max(dp_table[i+1][w_next], dp_table[i][j] + v_next)
            dp_table[i+1][j] = max(dp_table[i+1][j], dp_table[i][j])


    print(max(dp_table[-1]))
    # print(max(dp_table))

sub()
### BUGGY CODE ###

from functools import reduce
import fractions

def lcm_base(a, b):
    return a * b / fractions.gcd(a, b)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7

ll = lcm_list(A)
ans = 0
for i in A:
    ans += ll // i
print(int(ans%mod))


### FIXED CODE ###

from fractions import gcd

def lcm(c,d):
    return c//gcd(c,d)*d
mod=10**9+7
n=int(input())
a=[int(i) for i in input().split()]
l=a[0]
for i in range(1,n):
    l=lcm(l,a[i])
ans=0
for i in range(n):
    ans+=l//a[i]
    #ans%=mod
print(ans%mod)
### BUGGY CODE ###

s=list(input())
for i in range(int(input())):
  a=input().split()
  if a[0]=="1":
    s=s[::-1]
  elif a[1]=="2":
    s.append(a[2])
  else:
    s.insert(0,a[2])
print("".join(s))

### FIXED CODE ###

from collections import deque
s=deque(input().split())
f=False
for i in range(int(input())):
  _=input().split()
  if _[0]=='1':
    f=not f
  elif _[1]=='1':
    if f:
      s.append(_[2])
    else:
      s.appendleft(_[2])
  else:
    if f:
      s.appendleft(_[2])
    else:
      s.append(_[2])
print("".join(s)[::-1] if f else "".join(s))
### BUGGY CODE ###

# D - FT Robot

from collections import deque
import copy

s = list(input())
x, y = map(int, input().split())

if len(s) == 1:
    if (s[0] == "F" and (x, y) == (1, 0)) or (s[0] == "T" and (x, y) == (0, 0)):
        print("Yes")
    else:
        print("No")
    exit()

zipped_s = []
count = 1
for idx in range(len(s) - 1):
    if s[idx] == s[idx+1]:
        count += 1
    else:
        zipped_s.append((s[idx], count))
        count = 1
zipped_s.append((s[-1], count))

robot = deque([[[0,0], 0, 0]])
while robot:
    r = robot.pop()
    if r[1] == len(zipped_s):
        if r[0] == [x, y]:
            print("Yes")
            exit()
        else:
            continue
    elif zipped_s[r[1]][0] == "F":
        if r[-1] == 0:
            r[0][0] += zipped_s[r[1]][1]
        elif r[-1] == 1:
            r[0][1] += zipped_s[r[1]][1]
        elif r[-1] == 2:
            r[0][0] -= zipped_s[r[1]][1]
        else:
            r[0][1] -= zipped_s[r[1]][1]
        r[1] += 1
        robot.append(r)
    else:
        if zipped_s[r[1]][1] % 2 == 0:
            r[1] += 1
            robot.append(r)
            r2 = copy.deepcopy(r)
            r2[2] = (r2[2] + 2) % 4
            robot.append(r2)
        else:
            r[1] += 1
            r2 = copy.deepcopy(r)
            r[2] = (r[2] + 1) % 4
            robot.append(r)
            r2[2] = (r2[2] + 3) % 4
            robot.append(r2)
print("No")

### FIXED CODE ###

# D - FT Robot

import copy

s = input()
x, y = map(int, input().split())

f = [len(x) for x in s.split("T")]
x -= f[0]
fx = f[2::2]
fy = f[1::2]

x_possible_set = set([0])
for dx in fx:
    tmp = set()
    for current_x in x_possible_set:
        tmp.add(current_x + dx)
        tmp.add(current_x - dx)
    x_possible_set = tmp.copy()

y_possible_set = set([0])
for dy in fy:
    tmp = set()
    for current_y in y_possible_set:
        tmp.add(current_y + dy)
        tmp.add(current_y - dy)
    y_possible_set = tmp.copy()

print("Yes" if x in x_possible_set and y in y_possible_set else "No")
### BUGGY CODE ###

X,Y,A,B,C = map(int,input().split())
p,q,r = [sorted(map(int,input().split()),reverse=True) for i in range(3)]
ans,temp = 0,0

for i in range(X+1):
    temp = sum([p[t] for t in range(i)])
    for j in range(Y+1):
        temp_2 = temp + sum([q[t] for t in range(j)])
        t = lambda C: X-i+Y-j if X+Y-i-j < C else C
        temp_2 += sum([r[t] for t in range(t(C))]) 
        ans = max(temp_2,ans)

print(ans)

### FIXED CODE ###

X,Y,A,B,C = map(int,input().split())
p,q,r = [sorted(map(int,input().split()),reverse=True) for i in range(3)]
ans = 0
pp,qq = [p[i] for i in range(X)] ,[q[i] for i in range(Y)]
r = r + pp + qq
r = sorted(r,reverse=True)
for i in range(X+Y):
    ans += r[i]
print(ans)
### BUGGY CODE ###

import math

k = int(input())
sum = 0

for a in range(1, k + 1):
    for b in range(1, k + 1):
        for c in range(1, k + 1):
            sum += math.gcd(a, math.gcd(b, c))
print(sum)


### FIXED CODE ###

from math import gcd

k = int(input())
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(c, gcd(a, b))
print(sum)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
lr = [tuple(map(int,input().split())) for _ in range(q)]
for i in range(q):
  temp = list(s[lr[i][0]-1:lr[i][1]])
  cnt = 0
  while len(temp) > 1:
    x = temp.pop()
    y = temp[-1]
    if x == 'C' and y == 'A':
      cnt += 1
  print(cnt)

### FIXED CODE ###

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

ac = [0] * (n - 1)
for i in range(n-1):
  if s[i] == 'A' and s[i+1] == 'C':
    ac[i] = 1

acc = [0] * n
for i in range(n-1):
  acc[i+1] = acc[i] + ac[i]

lr = [tuple(map(int,input().split())) for _ in range(q)]
for i in range(q):
  l = lr[i][0] - 1
  r = lr[i][1] - 1
  print(acc[r] - acc[l])
### BUGGY CODE ###

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

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

now = 1

d = []

while True:
    if A[now-1] in d:
        i = d.index(A[now-1])
        check = d[i:]
        break
    d.append(A[now-1])
    now = A[now-1]

    if len(d) >= K:
        break

if K <= len(d):
    print(d[K-1])
else:
    K -= (len(d)-len(check))
    K = K % len(check)
    print(check[K-1])



### FIXED CODE ###

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

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

now = 1

d = []
set_d = set()

while True:
    if A[now-1] in set_d:
        i = d.index(A[now-1])
        check = d[i:]
        break
    now = A[now-1]
    d.append(now)
    set_d.add(now)

    if len(set_d) >= K:
        break

if K <= len(set_d):
    print(d[K-1])
else:
    K -= (len(set_d)-len(check))
    K = K % len(check)
    print(check[K-1])