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

N = int(input())
A = list(map(int, input().split()))
f = [[a] for a in A]
for i in range(N):
    for j in range(1<<N):
        if j & 1<<i:
            f[j] = sorted(f[j]+f[j^1<<i], reverse=True)[:2]
Ans = [sum(f[1])]
for a, b in f[2:]:
    Ans.append(max(Ans[-1], a+b))
print("\n".join(map(str, Ans)))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
f = [[a] for a in A]
for i in range(N):
    for j in range(1<<N):
        if j & 1<<i:
            f[j] = sorted(f[j]+f[j^1<<i], reverse=True)[:2]
Ans = [sum(f[1])]
for a, b in f[2:]:
    Ans.append(max(Ans[-1], a+b))
print("\n".join(map(str, Ans)))
### BUGGY CODE ###

import fractions
from functools import reduce
n = int(input())
an = list(map(int, input().split()))


def gcd(numbers):
    return reduce(fractions.gcd, numbers)


left = [gcd(an[:i]) for i in range(1, n)]
right = [gcd(an[i:]) for i in range(1, n)]

ans = 0
ans = max(ans, right[0], left[-1])
for i in range(1, n-1):
    ans = max(ans, fractions.gcd(left[i-1], right[i]))

print(ans)


### FIXED CODE ###

from fractions import gcd
n = int(input())
an = list(map(int, input().split()))

left = [an[0]]
right = [an[-1]]
for i in range(1, n-1):
    left.append(gcd(left[-1], an[i]))
    right.append(gcd(right[-1], an[-(i+1)]))

ans = max(right[-1], left[-1])
for i in range(n-2):
    ans = max(ans, gcd(left[i], right[-(i+2)]))

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



a, b = map(int, input().split())
MOD = (1e9 + 7)

def calc(x, y):
    right = above = 0
    while x>0 and y>0:
        if x>y:
            x -= 2
            y -= 1
            right += 1
        else:
            x -= 1
            y -= 2
            above += 1

    return (True, right, above) if x==0 and y==0 else (False, None, None)


def res(n, k):
    # print(n, k)
    total = 1
    if k < n-k:
        k = n-k
    for i in range(k+1, n+1):
        total = (total * i)# % MOD
    d = 1
    for i in range(1, n-k+1):
        d = (d*i) #% MOD
    return total // d

r, right, above = calc(a, b)
if not r:
    print(0)
else:
    print(int(res(above+right, right) % MOD))


### FIXED CODE ###



a, b = map(int, input().split())
MOD = int(1e9 + 7)

def calc(x, y):
    right = above = 0
    while x>0 and y>0:
        if x>y:
            x -= 2
            y -= 1
            right += 1
        else:
            x -= 1
            y -= 2
            above += 1

    return (True, right, above) if x==0 and y==0 else (False, None, None)


def res(n, k):
    # print(n, k)
    total = 1
    if k < n-k:
        k = n-k
    for i in range(k+1, n+1):
        total = (total * i)% MOD
        total *= pow(i-k, MOD-2, MOD)
    return total

r, right, above = calc(a, b)
if not r:
    print(0)
else:
    print(int(res(above+right, right) % MOD))
### BUGGY CODE ###

def check_prime(k):
    num = int(k ** 0.5 // 1)
    for i in range(2, num + 1):
        if k % i == 0:
            if check.get(i) or check.get(k//i):return 0
    return 1

n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
double = dict()
check = dict()
if a[0] == 1:
    if n == 1 or a[1] != 1:
        print(1)
        exit()
    else:
        print(0)
        exit()

for i in range(n):
    if i < n - 1 and a[i] == a[i + 1]:
        double[a[i]] = 1
        check[a[i]] = 1
        continue
    if double.get(a[i]):continue


    temp = check_prime(a[i])
    if temp:
        check[a[i]] = 1
        ans += 1
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
check = [True] * (a[-1] + 1)
cnt = Counter(a)

for i in range(n):
    if check[a[i]] == False:continue
    for j in range(a[i], a[-1] + 1, a[i]):
        if j == a[i]:continue
        check[j] = False

ans = 0
for i in range(n):
    if check[a[i]] and cnt[a[i]] == 1:ans += 1

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

def main():
    MOD = 7 + 10**9
    S = list(input())
    N = len(S)
    dp = [[0]*13 for _ in range(N)]
    if S[N-1] == '?':
        for m in range(10):
            dp[0][m] = 1
    else:
        tm = int(S[N-1])%13
        dp[0][tm] = 1
    for i in range(1,N):
        if S[N-1-i] == '?':
            for j in range(13):
                for k in range(10):
                    dp[i][j] += dp[i-1][(j-(k*10**i)%13)%13]%MOD
        else:
            m = (int(S[N-1-i])*10**i) % 13
            for l in range(13):
                dp[i][l] += dp[i-1][(l-m)%13]
    print(dp[N-1][5]%MOD)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    MOD = 7 + 10**9
    S = tuple(input())
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] += 1
    s=[1]
    for n in range(1,N):
        s.append((s[n-1]*10)%13)
    for i in range(N):
        for k in range(13):
            if S[-(i+1)] != '?':
                dp[i+1][(k+int(S[-(i+1)])*s[i])%13] += dp[i][k] 
                dp[i+1][(k+int(S[-(i+1)])*s[i])%13] %= MOD
            else:
                for l in range(10):
                    dp[i+1][(k+l*s[i])%13] += dp[i][k]
                    dp[i+1][(k+l*s[i])%13] %= MOD
    print(dp[-1][5])

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

s = input()
q = int(input())

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

### FIXED CODE ###

s = input()
q = int(input())

f1 = 1
f2 = 2
cnt = 0
st = ""
se = ""

for _ in range(q):
    q = input().split()
    if int(q[0]) == 1:
        cnt += 1
    elif int(q[0]) == 2:
        if cnt % 2 == 0:
            if int(q[1]) == 1:
                st = q[2] + st
            elif int(q[1]) == 2:
                se += q[2]
        else:
            if int(q[1]) == 1:
                se += q[2]
            elif int(q[1]) == 2:
                st = q[2] + st


ans = st + s + se
if cnt % 2 == 0:
    print(ans)
else:
    ans = list(ans)
    ans.reverse()
    ans = "".join(ans)
    print(ans)
### BUGGY CODE ###

T = input()

w0 = "dream"
w1 = "dreamer"
w2 = "erase"
w3 = "eraser"

dict_sen = {0:w0,1:w1,2:w2,3:w3}

dp = ""
S = ""

while(len(dp) < len(T)):
  for i in range(4):
    S = dict_sen[i]
    if T[len(dp):len(dp)+len(S)] == S:
      dp = dp + S
      break
if dp == T :
  print("YES")
else :
  print("NO")

### FIXED CODE ###

S=str(input()) #Sの入力
Smojisuu=len(S)
c=S.count("eraser")
S=S.replace("eraser","xxxxxx",c)
d=S.count("erase")
S=S.replace("erase","xxxxx",d)
e=S.count("dreamer")
S=S.replace("dreamer","xxxxxxx",e)
f=S.count("dream")
S=S.replace("dream","xxxxx",f)
g=S.count("x")
if len(S)>g:
  print("NO")
elif len(S)==g:
  print("YES")
else:
  print("error")
### BUGGY CODE ###

def line(N, X, Y):
    X = X - 1
    Y = Y - 1

    queue = [(a, a + 1) for a in range(N - 1)]
    queue.append((X, Y))
    visited = set(queue)
    print(len(queue))

    for i in range(N - 2):
        new_queue = []

        def add_to_queue(x, y):
            if y == N or y < 0:
                return
            if x == N or x < 0:
                return
            if x == y:
                return

            if x > y:
                x, y = y, x

            t = (x, y)
            if t not in visited:
                new_queue.append(t)
                visited.add(t)

        for q in queue:
            add_to_queue(q[0], q[1] + 1)
            add_to_queue(q[0], q[1] - 1)
            add_to_queue(q[0] + 1, q[1])
            add_to_queue(q[0] - 1, q[1])

        print(len(new_queue))
        # print(f"{len(new_queue)} {new_queue}")
        queue = new_queue


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

# line(5, 2, 4)
# print()
# line(3, 1, 3)
# print()
# line(7, 3, 7)
# print()
# line(10, 4, 8)


### FIXED CODE ###

# https://atcoder.jp/contests/abc160/tasks/abc160_d
N, X, Y = map(int, input().split())

visited = set()

# special case: first advance
for i in range(N - 1):
    visited.add((i, i + 1))
visited.add((X - 1, Y - 1))

print(len(visited))

next_items = visited.copy()
for _ in range(N - 2):
    candidates = []

    for point in next_items:
        x, y = point

        if (x - 1, y) not in visited and x - 1 >= 0:
            visited.add((x - 1, y))
            candidates.append((x - 1, y))

        if (x + 1, y) not in visited and x + 1 != y:
            visited.add((x + 1, y))
            candidates.append((x + 1, y))

        if (x, y - 1) not in visited and x != y - 1:
            visited.add((x, y - 1))
            candidates.append((x, y - 1))

        if (x, y + 1) not in visited and y + 1 < N:
            visited.add((x, y + 1))
            candidates.append((x, y + 1))

    print(len(candidates))
    next_items = candidates
### BUGGY CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

N,M = II()
A,B = Line(N)
a = []
for i in range(N):
  a.append([A[i],B[i]])
a.sort(key = lambda x:(-x[1],x[0]))

from bisect import bisect_left
s = [i for i in range(1,M+1)]
ans = 0
for i in range(N):
  if a[i][0]<=M:
    place = bisect_left(s,a[i][0])
    if place <= len(s)-1:
      s.pop(place)
      ans += a[i][1]
print(ans)


### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

N,M = II()
A,B = Line(N)
a = []
for i in range(N):
  a.append([A[i],B[i]])
a.sort(key = lambda x:(x[0],x[1]))

b = []
for i in range(N):
  b.append([-a[i][1], a[i][0]])

from bisect import bisect_left, bisect_right
import heapq

ans = 0
h = []

for i in range(1,M+1):
  left = bisect_left(a,[i,0])
  right = bisect_right(a,[i,float('inf')])-1
  if right-left>=0:
    for i in range(left,right+1):
      heapq.heappush(h,b[i])
    x = heapq.heappop(h)
    ans += -x[0]
  else:
    if h:
      x = heapq.heappop(h)
      ans += -x[0]

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

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

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

### FIXED CODE ###

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

ans = 0
if 0 not in A:
  ans = 1
  for i in range(N):
    ans *= A[i]
    if ans > 10**18:
      ans = '-1'
      break

print(ans)
### 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=int(input())
cnt=0
for i in range(1,N):
    cnt += len(make_divisors(N-i))
    
print(cnt)

### FIXED CODE ###

N=int(input())

ans=0
for a in range(1,N):
    ans += (N-1)//a
print(ans)
### BUGGY CODE ###

#b faster
#m_i(k) = min(m_i(k-1), a_(i-k))
n,x =  [int(i) for i in input().split()]
a   =  [int(i) for i in input().split()]
m   =  a[::]
a.extend(a)

min_cost = 10**10

for k in range(n):
    cost = x * k
    for i in range(n,2*n):
        mini = min(m[i-n], a[i-k])
        m[i-n] = mini
        cost += mini
    min_cost = min(min_cost, cost)
print(min_cost)

### FIXED CODE ###

#b faster
#m_i(k) = min(m_i(k-1), a_(i-k))
# http://agc004.contest.atcoder.jp/data/agc/004/editorial.pdf
n,x =  [int(i) for i in input().split()]
a   =  [int(i) for i in input().split()]
m   =  a[::]
a.extend(a)

min_cost = sum(a)

for k in range(n):
    #cost = x * k
    for i in range(n,2*n):
        m[i-n] = min(m[i-n], a[i-k])
        #cost += mini
    min_cost = min(min_cost, x*k + sum(m))
print(min_cost)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys, heapq
sys.setrecursionlimit(300000)

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

def solve(N: int, S: "List[str]"):
    tmp = []
    for i in range(N):
        cur = 0
        mn = 0
        for c in S[i]:
            if c == '(':
                cur += 1
            else:
                cur -= 1
                mn = min(mn, cur)
        tmp.append((mn, cur, cur - mn))

    tmp.sort(key=lambda x: (x[0], x[1]), reverse=True)
    #print(tmp)

    cur = 0
    idx = 0
    q = []
    count = 0
    while count < N:
        while idx < N and cur + tmp[idx][0] >= 0:
            heapq.heappush(q, (-tmp[idx][2], -tmp[idx][1], -tmp[idx][0]))
            idx += 1
        if len(q) == 0:
            print(NO)
            return
        #print(count, q)
        diff, cnt, mn = heapq.heappop(q)
        diff, cnt, mn = -diff, -cnt, -mn
        #print(cnt, mn)
        if cur + mn < 0:
            print(NO)
            return
        cur += cnt
        count += 1

    #for mn, cnt, diff in tmp:
    #    if abs(mn) > cur:
    #        print(NO)
    #        return
    #    cur += cnt

    #print(cur)
    if cur == 0:
        ret = YES
    else:
        ret = NO
    print(ret)
    return

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
    S = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3

import sys, heapq
sys.setrecursionlimit(300000)

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

def solve(N: int, S: "List[str]"):
    tmp = []
    for i in range(N):
        cur = 0
        mn = 0
        for c in S[i]:
            if c == '(':
                cur += 1
            else:
                cur -= 1
                mn = min(mn, cur)
        tmp.append((mn, cur))

    tmp.sort(key=lambda x: (x[1] < 0, (-x[0] if x[1] >= 0 else -(x[1] - x[0]))))
    #tmp.sort(key=lambda x: (x[1] < 0, -x[0], x[1]))
    #print(tmp)

    cur = 0
    for mn, cnt in tmp:
        #print(cur, mn, cnt)
        if abs(mn) > cur:
            print(NO)
            return
        cur += cnt

    if cur == 0:
        ret = YES
    else:
        ret = NO
    print(ret)
    return

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
    S = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, S)

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

import fractions

K = int(input())

ans = 0
a=[]
for i in range(1,K+1):
	for j in range(1, K+1):
		tmp = fractions.gcd(i,j)
		for k in range(1, K+1):
			ans+=fractions.gcd(tmp,k)

print(ans)

### FIXED CODE ###

import math
K = int(input())

ans = 0
a=[]
for i in range(1,K+1):
	for j in range(1, K+1):
		tmp = math.gcd(i,j)
		for k in range(1, K+1):
			ans+=math.gcd(tmp,k)

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

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

ma=0
for i in range(1,min(b,n)+1):
    ma=max(ma,(i*a)//b-a*(i//b))
print(ma)


### FIXED CODE ###

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

i=min(b-1,n)
print((i*a)//b-a*(i//b))
### BUGGY CODE ###

ans = 0
n = int(input())
for i in range(1,n+1):
  for j in range(1,n//i+1):
    if i * j < n:ans += 1
print(ans)


### FIXED CODE ###

ans = 0
n = int(input())
for i in range(1,n+1):
  for j in range(1,n//i+1):
    if i * j < n:ans += 1
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
x = list(set(a))
b = []
for i in range(len(x)):
    b.append(a.count(x[i]))

b.sort(reverse = True)
c = len(b)
if c > k:
    d = c - k
    print(sum(b[c-d:c]))
else:
    print(0)


### FIXED CODE ###

import collections
n,k = map(int,input().split())
a = list(map(int,input().split()))
l = collections.Counter(a)
l = list(l.values())
l.sort(reverse = True)
print(sum(l[k:]))
### BUGGY CODE ###

#!/usr/bin/env python3

import itertools

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

ans = 0
cnt = 0
X = [i for i in range(1, M+1)]
Y = X * N

for i in itertools.permutations(Y, r=N):
    cnt = 0
    j = list(i)
    j.sort()
    for k in lis:
        if j[k[1]-1] - j[k[0]-1] == k[2]:
            cnt += k[3]
    ans = max(ans, cnt)

print(ans)

### FIXED CODE ###

#!/usr/bin/env python3

import itertools

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

ans = 0
cnt = 0
X = [i for i in range(1, M+1)]

for i in itertools.combinations_with_replacement(X, r=N):
    cnt = 0
    j = list(i)
    for k in lis:
        if j[k[1]-1] - j[k[0]-1] == k[2]:
            cnt += k[3]
    ans = max(ans, cnt)

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

n,k,q=map(int,input().split())
point=[k]*n
for _ in range(q):
    a=int(input())-1
    for i in range(n):
        if a!=i:
            point[i]-=1
for i in range(n):
    if point[i]>0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n,k,q=map(int,input().split())
ans=[0]*n
for _ in range(q):
    a=int(input())
    ans[a-1]+=1
for i in range(n):
    if ans[i]>q-k:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

from fractions import gcd  # in math module python >= 3.5
from functools import reduce


def gcdall(numlist):
    return reduce(gcd, numlist)


def main():
    _ = int(input())
    a = list(map(int, input().split()))
    if len(a) < 3:
        print(max(a))
        return

    gcds = []
    calced = []
    for i in range(len(a)):
        target = set([a[j] for j in range(len(a)) if j != i])
        if (any([c == target for c in calced])):
            continue
        excepted = list(target)
        b = 0
        while all([k % 2 == 0 for k in excepted]):
            b += 1
            excepted = [k // 2 for k in excepted]

        if b > 0:
            gcds.append(gcdall(excepted) * 2 * b)
        else:
            gcds.append(gcdall(excepted))

        calced.append(excepted)
    print(max(gcds))


main()

### FIXED CODE ###

from fractions import gcd  # in math module python >= 3.5


def main():
    n = int(input())
    a = list(map(int, input().split()))
    if len(a) < 3:
        print(max(a))
        return

    ls = []
    for i in range(n+1):
        if i == 0:
            ls.append(0)
        else:
            ls.append(gcd(ls[i-1], a[i-1]))

    rs = []
    for i in range(n+1):
        if i == 0:
            rs.append(0)
        else:
            rs.append(gcd(rs[i-1], a[-i]))
    rs = list(reversed(rs)) + [0]

    m = [gcd(ls[i], rs[i+1]) for i in range(n+1)]

    print(max(m))


main()
### BUGGY CODE ###

inp = input()
a,b,c,d = [int(x) for x in list(inp)]

def add(a,b):
    return a+b
def sub(a,b):
    return a-b
lis = [0,0,0]
count = 0
while True:
    sum = 0
    if lis[0] == 0:
        sum = add(a,b)
    else:
        sum = sub(a,b)
    if lis[1] == 0:
        sum = add(sum,c)
    else:
        sum = sub(sum,c)
    if lis[2] == 0:
        sum = add(sum, d)
    else:
        sum = sub(sum, d)
    if sum == 7:
        break
    count += 1
    lis[0] = count % 2
    lis[1] = count // 2
    lis[2] = count// 4

if lis[0] == 0:
    x = '+'
else:
    x = '-'
if lis[1] == 0:
    y = '+'
else:
    y = '-'
if lis[2] == 0:
    z = '+'
else:
    z = '-'
print('{}{}{}{}{}{}{}=7'.format(a,x,b,y,c,z,d))

### FIXED CODE ###

inp = input()
a,b,c,d = [int(x) for x in list(inp)]

def add(a,b):
    return a+b
def sub(a,b):
    return a-b
lis = [0,0,0]
count = 0
while True:
    sum = 0
    if lis[0] == 0:
        sum = add(a,b)
    else:
        sum = sub(a,b)
    if lis[1] == 0:
        sum = add(sum,c)
    else:
        sum = sub(sum,c)
    if lis[2] == 0:
        sum = add(sum, d)
    else:
        sum = sub(sum, d)
    if sum == 7:
        break
    count += 1
    lis[0] = count % 2
    lis[1] = (count // 2) % 2
    lis[2] = (count// 4) % 2

if lis[0] == 0:
    x = '+'
else:
    x = '-'
if lis[1] == 0:
    y = '+'
else:
    y = '-'
if lis[2] == 0:
    z = '+'
else:
    z = '-'
print('{}{}{}{}{}{}{}=7'.format(a,x,b,y,c,z,d))
### BUGGY CODE ###

#segtree ライブラリ
#BITライブラリの作成
#リストの要素を1,0で長さをｎとした時に使える
class BIT:
    def __init__(self,n):
        self.n=n
        self.data=[0]*(n+1)
    def to_sum(self,i):
        s=0     
        while i>0:
            s+=self.data[i]
            i-=(i& -i)
        return s
    def add(self,i,x):
        while i<=self.n:
            self.data[i]+=x
            i+=(i & -i)
    def get(self,i,j):
        return self.to_sum(j)-self.to_sum(i-1)
n=int(input())
s=list(input())
q=int(input())
que=[]

for i in range(q):
    p=list(input().split())
    que.append(p)
alpha="abcdefghijklmnopqrstuvwxyz"
segtree={alpha[i]:BIT(n) for i in range(26)}  
for i in range(n):
    segtree[s[i]].add(i+1,1)
for q in que:
    x,y,z=q[0],q[1],q[2]
    if int(x)==1:
        #y文字目をzに変更する
        y=int(y)  
        for i in range(26):
            if segtree[alpha[i]].get(y,y)==1:
                segtree[alpha[i]].add(y,-1)
                break
        segtree[z].add(y,1)
    else:
        ans=0
        for i in range(26):
            if segtree[alpha[i]].get(int(y),int(z))>0:
                ans+=1
        print(ans)       

### FIXED CODE ###

#segtree ライブラリ
#BITライブラリの作成
#リストの要素を1,0で長さをｎとした時に使える
class BIT:
    def __init__(self,n):
        self.n=n
        self.data=[0]*(n+1)
    def to_sum(self,i):
        s=0     
        while i>0:
            s+=self.data[i]
            i-=(i& -i)
        return s
    def add(self,i,x):
        while i<=self.n:
            self.data[i]+=x
            i+=(i & -i)
    def get(self,i,j):
        return self.to_sum(j)-self.to_sum(i-1)
n=int(input())
s=list(input())
q=int(input())
que=[]

for i in range(q):
    p=list(input().split())
    que.append(p)
alpha="abcdefghijklmnopqrstuvwxyz"
segtree={alpha[i]:BIT(n) for i in range(26)}  
for i in range(n):
    segtree[s[i]].add(i+1,1)
for q in que:
    x,y,z=q[0],q[1],q[2]
    if int(x)==1:
        #y文字目をzに変更する
        y=int(y)  
        for i in range(26):
            if segtree[alpha[i]].get(y,y)==1:
                segtree[alpha[i]].add(y,-1)
                break
        segtree[z].add(y,1)
    else:
        ans=0
        for i in range(26):
            if segtree[alpha[i]].get(int(y),int(z))>0:
                ans+=1
        print(ans)
### BUGGY CODE ###

from collections import deque
import sys

def main():
    input = sys.stdin.readline
    n,k = map(int,input().split())

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

    #ループを探す？

    checked_list = [1]
    que = deque([a[0]])

    counter = 0
    q_append = que.append
    c_append = checked_list.append

    while True:
        counter += 1
        x = que.popleft()
        if counter == k:
            print(x)
            exit()
        if x in set(checked_list):
            startflg = checked_list.index(x)
            loop_length = counter - startflg
            loop_list = checked_list[startflg:counter]
            amari = (k-startflg) % loop_length
            print(loop_list[amari])
            exit()
        else:
            q_append(a[x-1])
            c_append(x)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import deque
import sys

def main():
    input = sys.stdin.readline
    n,k = map(int,input().split())

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

    #ループを探す？

    checked_dict = {1:0}
    que = deque([a[0]])

    counter = 0


    while True:
        counter += 1
        x = que.popleft()
        if counter == k:
            print(x)
            exit()
        if x in checked_dict:
            startflg = checked_dict[x]
            loop_length = counter - startflg

            inverse_dict = {v:k for k,v in checked_dict.items()}

            loop_list = [inverse_dict[i] for i in range(startflg,startflg+loop_length)]
            amari = (k-startflg) % loop_length
            print(loop_list[amari])
            exit()
        else:
            que.append(a[x-1])
            checked_dict[x] = counter

if __name__ == '__main__':
    main()