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

S=input()
N=len(S)
Slis=[]
for i in range(N):
  Slis+=[int(S[i])]
T=[0 for i in range(N+1)]#T[i]はi桁より右側の数字


def kaizyou(n):
  c=1
  c=c*10**n
  return c%2019


for i in range(N):
  T[N-i-1]=(T[N-i]+kaizyou(i)*Slis[N-i-1])%2019

MOD=[0 for i in range(2019)]
for i in range(N+1):
  tmp=T[i]%2019
  MOD[tmp]+=1


  
ans=0

for i in range(2019):
  tmp=MOD[i]
  ans+=tmp*(tmp-1)//2
print(ans)


### FIXED CODE ###

S=input()
N=len(S)
Slis=[]
for i in range(N):
  Slis+=[int(S[i])]
T=[0 for i in range(N+1)]#T[i]はi桁より右側の数字


ten=1

for i in range(N):
  T[N-i-1]=(T[N-i]+ten*Slis[N-i-1])%2019
  ten=(ten*10)%2019

MOD=[0 for i in range(2019)]
for i in range(N+1):
  tmp=T[i]%2019
  MOD[tmp]+=1


  
ans=0

for i in range(2019):
  tmp=MOD[i]
  ans+=tmp*(tmp-1)//2
print(ans)
### BUGGY CODE ###

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

l_sorted = sorted(l)

s = ""
for x in l_sorted:
    s = s + str(l.index(x) + 1) + " "

print(s[:-1])

### FIXED CODE ###


N = int(input())
l = [int(x) for x in input().split()]
l_dict = {k: v for v, k in enumerate(l)}
l.sort()

for i, x in enumerate(l):
    if i == 0:
        print(l_dict[x] + 1, end="")
    else:
        print(" {}".format(str(l_dict[x] + 1)), end="")
### BUGGY CODE ###

M = 10 ** 6 + 5
N = int(input())
A = list(map(int, input().split()))
cnt = [0] * M
ans = 0
for i in A:
    for j in range(0, M, i):
        cnt[j] += 1
for i in A:
    if(cnt[i] == 1):
        ans += 1
print(ans)

### FIXED CODE ###

M = 10 ** 6 + 5
N = int(input())
A = list(map(int, input().split()))

cnt = [0] * M
for i in A:
    if(cnt[i] >= 2):
        continue
    for j in range(i, M, i):
        cnt[j] += 1
ans = 0
for i in A:
    if(cnt[i] == 1):
        ans += 1
print(ans)
### BUGGY CODE ###

#https://atcoder.jp/contests/abc110/tasks/abc110_c

s = list(str(input()))
t = list(str(input()))
u = []
v = []
cnt = 0
for i in range(len(s)):
    for j in range(len(s)):
        if s[i] == s[j]:
            cnt += 1
    u.append(cnt)
    cnt = 0

cnt = 0
for i in range(len(t)):
    for j in range(len(t)):
        if t[i] == t[j]:
            cnt += 1
    v.append(cnt)
    cnt = 0

flag = 'Yes'
for i in range(len(u)):
    if u[i] != v[i]:
        flag = 'No'
        break

print(flag)
'''
cnt = 1
for i in range(1, len(s)):
    if s[i] == s[i - 1]:
        cnt += 1
    else:
        u.append(cnt)
        cnt = 1
    if i == len(s) - 1:
        u.append(cnt)

cnt = 1
for i in range(1, len(t)):
    if t[i] == t[i - 1]:
        cnt += 1
    else:
        v.append(cnt)
        cnt = 1
    if i == len(t) - 1:
        v.append(cnt)

print(u)
print(v)

flag = 'Yes'
if len(u) == len(v):
    for i in range(len(u)):
        if u[i] != v[i]:
            flag = 'No'
else:
    flag = 'No'

print(flag)
'''
'''
if flag == 'Yes':
    for i in range(len(s)):
        f = False
        for j in range(len(t)):
            if s[i] == t[j]:
                f = True
                break
        if f == False:
            flag = 'No'
            print(i)
            break

print(flag)
'''


### FIXED CODE ###

import sys
s = str(input())
t = str(input())
l = len(s)
tmp = [[], []]
for i in range(l):
    if (not s[i] in tmp[0]) and (not t[i] in tmp[1]):
        tmp[0].append(s[i])
        tmp[1].append(t[i])
    else:
        if s[i] in tmp[0]:
            tmp2 = 0
            for j in range(len(tmp[0])):
                if s[i] == tmp[0][j]:
                    tmp2 = j
            if t[i] != tmp[1][tmp2]:
                print('No')
                sys.exit()
        else:
            print('No')
            sys.exit()
print('Yes')
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import sys
from collections import Counter, defaultdict

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, Q = MAP()
STX = []
X = set()
A = defaultdict(list)
for i in range(N):
    s, t, x = MAP()
    # 全ての工事を同じ時系列に持ってくる
    STX.append((s-x, t-x, x))
    X.add(s-x)
    X.add(t-x)
    A[s-x].append((x, 0))
    A[t-x].append((x, 1))
D = LIST(Q)

S = sorted(X|set(D))
B = {}
C = Counter()
for key in S:
    li = A[key]
    for x, flag in li:
        if flag == 0:
            C[x] += 1
        else:
            C[x] -= 1
        if C[x] == 0:
            del C[x]
    mn = min(C) if len(C) else -1
    B[key] = mn
[print(B[x]) for x in D]


### FIXED CODE ###

# -*- coding: utf-8 -*-

import sys
from heapq import heappush, heappop

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, Q = MAP()
# 3種類の状態変化をイベントとして一括管理する
# 0: 工事終了, 1: 工事開始, 2: 人の出発
events = []
for i in range(N):
    s, t, x = MAP()
    # (開始座標に合わせた状態の工事開始時間, フラグ, 実際の座標)
    events.append((s-x, 1, x))
    # (開始座標に合わせた状態の工事終了時間, フラグ, 実際の座標)
    events.append((t-x, 0, x))
for i in range(Q):
    d = INT()
    # (人の出発時間, フラグ, index)
    events.append((d, 2, i))
# 時系列に沿ってソート、フラグも同時刻な時先に処理して欲しいものから番号を振ってある
events.sort()

# setとheapqを合わせて、時刻に合わせた処理と最小値取得を行う
S = set()
hp = []
ans = [0] * Q
for t, flag, x in events:
    # 工事終了
    if flag == 0:
        S.remove(x)
    # 工事開始
    elif flag == 1:
        S.add(x)
        heappush(hp, x)
    # 人の移動
    elif flag == 2:
        # heapqの先頭要素ついて、setと状態を合わせる
        while len(hp) and hp[0] not in S:
            heappop(hp)
        if len(hp):
            ans[x] = hp[0]
        else:
            ans[x] = -1
[print(a) for a in ans]
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(N):
    L = A[A[i] + i + 1:]
    for j in range(len(L)):
        if j+1 == L[j]:
            ans += 1
print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
ans = 0
l = []
r = []
for i,j in enumerate(A):
    l.append(i+j)
    r.append(i-j)

b = Counter(r)
for i in l:
    ans += b.get(i,0)
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
A=[int(input()) for i in range(m)]
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in A:dp[i]=0
print(dp[n])

### FIXED CODE ###

n,m=map(int,input().split())
A=set(int(input()) for i in range(m))
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in A:dp[i]=0
print(dp[n])
### BUGGY CODE ###

import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
mod = 10**9 + 7
K = int(input())
S = input()
n = len(S)
ans = 0
for i in range(K+1):
    ans += comb(i+n-1, n-1) * 25**i * 26**(K-i)
print(ans%mod)

### FIXED CODE ###

# F - Strivore
import sys
MOD = 10**9+7
K = int(input())
S = input()
l = len(S)
ans = 0
 
tmp = pow(26,K,MOD)
ans = tmp
waru = pow(26,-1,MOD)
 
for i in range(1,K+1):
    tmp = (tmp*25*waru)%MOD
    tmp = (tmp*(l-1+i)*pow(i,-1,MOD))%MOD
    ans = (ans+tmp)%MOD
 
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
Min = n
while True:
    if k == 1:
        print(0)
        exit()
    n = abs(n-k)
    if Min == n:
        break
    if Min > n:
        Min = n
print(Min)


### FIXED CODE ###

n, k = map(int, input().split())
r = n%k
print(min(r, k-r))
### BUGGY CODE ###

H,W,M = map(int,input().split())
HW = []

Hmax_temp = [0]*(H+1)
Wmax_temp = [0]*(W+1)
Hmax = 0
Wmax = 0
for i in range(M):
	H_M,W_M = map(int,input().split())
	Hmax_temp[H_M] += 1
	Wmax_temp[W_M] += 1
	HW.append([H_M,W_M])

Hmax = max(Hmax_temp)
Wmax = max(Wmax_temp)

#H方向の走査
y_max = []
for i in range(H+1):
	if Hmax == Hmax_temp[i]:
		y_max.append(i)
		
#W方向の走査
x_max = []
for j in range(W+1):
	if Wmax == Wmax_temp[j]:
		x_max.append(j)

#爆弾設置位置に対象が存在するか？
flag = False
for i in y_max:
	for  j in x_max:
		if [i,j] not in HW:
			flag = True
			break
	if flag:
		break

#答えのセット
if flag:
	ans = Wmax + Hmax
else:
	ans = Wmax + Hmax - 1
print(ans)

### FIXED CODE ###



H,W,M = map(int,input().split())

Hmax_temp = [0]*(H+1)
Wmax_temp = [0]*(W+1)
Hmax = 0
Wmax = 0
Bomb = dict()
for i in range(M):
	H_M,W_M = map(int,input().split())
	Hmax_temp[H_M] += 1
	Wmax_temp[W_M] += 1
	Bomb[(H_M,W_M)] = 1

Hmax = max(Hmax_temp)
Wmax = max(Wmax_temp)

#H方向の走査
y_max = []
for i in range(H+1):
	if Hmax == Hmax_temp[i]:
		y_max.append(i)
		
#W方向の走査
x_max = []
for j in range(W+1):
	if Wmax == Wmax_temp[j]:
		x_max.append(j)

#爆弾設置位置に対象が存在するか？
flag = False
for i in y_max:
	for  j in x_max:
		if (i,j) not in Bomb:
			flag = True
			break
	if flag:
		break

#答えのセット
if flag:
	ans = Wmax + Hmax
else:
	ans = Wmax + Hmax - 1
print(ans)
### BUGGY CODE ###

import numpy as np

n = int(input())

buf = []
cnt = []

for i in range(n):
    buf2 = input()
    if buf2 not in buf:
        buf.append(buf2)
        cnt.append(0)
    cnt[buf.index(buf2)] += 1

aaa = max(cnt)
ans2 = np.array(buf)[np.array(cnt) == aaa]
ans3 = sorted(ans2)

for i in ans3:
    print(i)

### FIXED CODE ###

n = int(input())
s = []

for i in range(n):
    s.append(input())

word_buf = {}

for i in s:
    if i in word_buf.keys():
        word_buf[i] += 1
    else:
        word_buf[i] = 1

max_cnt = max(word_buf.values())
max_word = [i[0] for i in word_buf.items() if i[1] == max_cnt]
max_word.sort()

for i in max_word:
    print(i)
### BUGGY CODE ###

n,k = map(int,input().split())
A = [int(i) for i in input().split()]
A.sort()
F = [int(i) for i in input().split()]
F.sort(reverse=True)

left = -1
right = 10**12
def f(x):
    cnt = 0
    for i in range(n): cnt += max(A[i]-x//F[i],0)
    return cnt <= k
    
while right - left > 1:
    mid = (left+right)//2
    if f(mid): right = mid
    else: left = mid
print(right)

### FIXED CODE ###

n,k = map(int,input().split())
A = [int(i) for i in input().split()]
A.sort()
F = [int(i) for i in input().split()]
F.sort(reverse=True)

left = -1
right = 10**12
def f(x):
    cnt = 0
    for i in range(n): cnt += max(A[i]-x//F[i],0)
    return cnt <= k
    
while right - left > 1:
    mid = (left+right)//2
    if f(mid): right = mid
    else: left = mid
print(right)
### BUGGY CODE ###

import math

x = int(input())
a = math.ceil(x ** 0.2)
while True:
    aa = a ** 5
    bb = aa - x
    bbb = bb ** 0.2
    if bb < 0:
        b = -1
    else:
        b = 1
    b *= int(bbb.real + bbb.imag)
    if aa - b ** 5 == x:
        print(a,b)
        break
    a -= 1

### FIXED CODE ###

import math
import sys

x = int(input())
r = math.ceil(x ** 0.2)
# print(r)
def reverse_num(x):
    return r - x
def calc_b(aa):
    bb = aa - x
    bbb = abs(bb) ** 0.2
    if bb < 0:
        b = -1
    else:
        b = 1
    # print(bb,b * int(bbb.real + bbb.imag))
    return b * int(bbb.real + bbb.imag)
def check(a):
    aa = a ** 5
    b = calc_b(aa)
    # print(a,b)
    if aa - b ** 5 == x:
        print(a,b)
        return True
    else:
        return False
for a in range(r // 2 + 1):
    if check(a) or check(reverse_num(a)):
        sys.exit()
a = r + 1
while True:
    if check(a):
        sys.exit()
    a += 1
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
s = []
for i in range(1, N):
    s.append(abs(sum(A[0:i]) - sum(A[i:])))
print(min(s))

### FIXED CODE ###

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

ans = float('inf')
snu = 0
ara = sum(A)
for a in A[0:-1]:
    snu += a
    ara -= a
    ans = min(ans, abs(snu - ara))
print(ans)
### BUGGY CODE ###

A,B,N=map(int, input().split())
answer=0
import math
Blist=[]
apple=min(B,N)
for i in range(1,apple+1):
    newans=math.modf(i/B)[0]*A
    newans//=1
    answer=newans if newans>answer else answer
print(int(answer))

### FIXED CODE ###

A,B,N=map(int, input().split())
answer=0
import math
if N < B:
    print(int(math.modf(N/B)[0]*A))
else:
    apple=min(B,N)
    startnum = B-1 if B>1 else 1
    for i in range(startnum,apple+1):
        newans=math.modf(i/B)[0]*A
        newans//=1
        answer=newans if newans>answer else answer
    print(int(answer))
### BUGGY CODE ###

from collections import Counter
s=list(input())
lst=[]  #sのリバース
lst2=[] #累積和を2019で割ったあまり
for i in range(len(s)):
    lst.append(s.pop())

num=0
for j in range(len(lst)):
    lst2.append(num%2019)
    num+=int(lst[j])*10**(j)
lst2.append(num%2019)
ans=0
cou=dict(Counter(lst2))
for x in cou.values():
    ans+=x*(x-1)/2
print(int(ans))


### FIXED CODE ###

from collections import Counter

s=input()[::-1]
ans=0
lst=[0]
num=0
p=1
for i in s:
    lst.append((int(i)*p+lst[-1])%2019)
    p=p*10%2019

ans=sum(x*(x-1)//2 for x in Counter(lst).values())
print(ans)
### BUGGY CODE ###

import numpy as np
import math
n, m = map(int, input().split())
a = np.array(list(map(int, input().split())))
for i in range(m):
    a[np.argmax(a)] /= 2
sum = 0
for i in range(n):
    sum += math.floor(a[i])
print(sum)

### FIXED CODE ###

import heapq
n, m = map(int, input().split())
a = list(map(lambda x: int(x) * (-1), input().split()))
heapq.heapify(a)
for _ in range(m):
    tmp_min = heapq.heappop(a)
    heapq.heappush(a, (-1)*(-tmp_min//2))
print(-sum(a))
### BUGGY CODE ###

N = int(input())
d = {}
for _ in range(N):
    s = input()
    if s not in d:
        d[s] = 0
    d[s] += 1

n = d[max(d)]

res = [kv[0] for kv in d.items() if kv[1] == max(d.values())]

res.sort()

for s in res:
    print(s)

### FIXED CODE ###

N = int(input())
d = {}
for _ in range(N):
    s = input()
    if s not in d:
        d[s] = 0
    d[s] += 1

n = max(d.values())

res = [kv[0] for kv in d.items() if kv[1] == n]

res.sort()

for s in res:
    print(s)
### BUGGY CODE ###

import Queue
t = int(input())

queue = Queue.Queue()
queue.put([0,0])
while True :
	x = queue.get()
	if x[0] == t:
		print x[1]
		break

	else :
		queue.put([ x[0]+x[1]+1 , x[1]+1 ])
		queue.put([ x[0] , x[1]+1])
		if x[0] - (x[1]+1) > 0 :
			queue.put([x[0]-(x[1]+1),x[1]+1])



### FIXED CODE ###

n = int(input())

ans = 0
i = 1
while n > ans :
	ans += i
	i += 1

print i-1
### BUGGY CODE ###

N, M = map(int, input().split())
list1 = [0]*N

for i in range(M):
    a, b = map(int, input().split())
    for j in range(a-1,b):
        list1[j] = list1[j]+1

count1 = 0
for i in range(len(list1)):
     if list1[i]==M:
        count1 +=1

print(count1)


### FIXED CODE ###

N, M = map(int, input().split())
a1 = 0
b1 = N
for i in range(M):
    a, b = map(int, input().split())
    if a1 <= a:
        a1 =a
    if b1 >= b:
        b1 = b

ans = b1-a1+1
if ans <0:
    ans = 0
print(ans)
### BUGGY CODE ###

import itertools
import math

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

number = []
for i in range(m):
    number.append(i+1)
a = list(itertools.combinations_with_replacement(number,n))
length = len(a)
memo = [0] * length

for i in range(q):
    num = list(map(int,input().split()))
    for j in range(length):
        if int(a[j][num[1]-1])-int(a[j][num[0]-1]) == int(num[2]):
            memo[j] += num[3]
print(max(memo))



### FIXED CODE ###

import itertools

n,m,q = map(int,input().split())
num = [list(map(int,input().split())) for i in range(q)]

number = []
for i in range(m):
    number.append(i+1)
a = list(itertools.combinations_with_replacement(number,n))
length = len(a)
memo = [0] * length
ans = 0

for i in range(length):#組み合わせの数回す
    sum = 0
    for j in range(q):
       if a[i][num[j][1]-1] - a[i][num[j][0]-1]  == num[j][2]:
            sum += num[j][3]
    ans = max(sum,ans)
print(ans)
### BUGGY CODE ###

k = int(input())
if k % 2 == 0:
    print(-1)
else:
    s = i = 0
    while True:
        i += 1
        s = (s*10 + 7) % k
        if s % k == 0:
            print(i)
            break

### FIXED CODE ###

k = int(input())
if k % 2 == 0 or k % 5 == 0:
    print(-1)
else:
    s = i = 0
    while True:
        i += 1
        s = (s*10 + 7) % k
        if s % k == 0:
            print(i)
            break
### BUGGY CODE ###

t=input()
ans=""
for i in range(len(t)):
    if t[i]=="?": ans+="D"
    else: ans+=t[i]
print(ans)

### FIXED CODE ###

t=input()
ans=""
for i in range(len(t)):
    if t[i]=="?": print("D",end="")
    else: print(t[i],end="")
### BUGGY CODE ###

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


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

shop = []
shop_a0 = []

for i in range(n):
    a, b = map(int, input().split())
    if a != 0:
        shop.append([a, b, a/(b+1)])
    else:
        shop_a0.append(b)

shop = sorted(shop, key=lambda x: -x[2])
shop_a0 = sorted(shop_a0)

n = len(shop)

INF = 10**10
# dp[i][j]:i番目まで見てj個の店を回るのに掛かる所要時間の最小値
dp = [[INF for _ in range(30)] for __ in range(n+1)]
dp[0][0] = 0

m = min(n+1, 30)

for j in range(m):
    for i in range(n):
        dp[i+1][j] = min(dp[i][j], dp[i][j-1] + 1 +
                         shop[i][0]*(dp[i][j-1]+1) + shop[i][1])

ss = []
if shop_a0:
    ss.append(1+shop_a0[0])
    for i in range(1, len(shop_a0)):
        ss.append(ss[-1]+1+shop_a0[i])

ans = 0

for i in range(m):
    if t - dp[n][i] >= 0:
        ans = max(ans, bisect_right(ss, t-dp[n][i]) + i)

print(ans)


### FIXED CODE ###

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


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

shop = []
shop_a0 = []

for i in range(n):
    a, b = map(int, input().split())
    if a != 0:
        shop.append([a, b, a/(b+1)])
    else:
        shop_a0.append(b)

shop = sorted(shop, key=lambda x: -x[2])
shop_a0 = sorted(shop_a0)

n = len(shop)

INF = 10**10
# dp[i][j]:i番目まで見てj個の店を回るのに掛かる所要時間の最小値
dp = [[INF for _ in range(31)] for __ in range(n+1)]
dp[0][0] = 0

m = min(n+1, 30)

for i in range(n):
    for j in range(m):
        if (shop[i][0]+1)*(dp[i][j]+1) + shop[i][1] > t:
            dp[i+1][j+1] = dp[i][j+1]
        else:
            dp[i+1][j+1] = min(dp[i][j+1], (shop[i][0]+1)
                               * (dp[i][j]+1) + shop[i][1])
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

ss = []
if shop_a0:
    ss.append(1+shop_a0[0])
    for i in range(1, len(shop_a0)):
        ss.append(ss[-1]+1+shop_a0[i])

ans = 0

for i in range(m):
    if t - dp[n][i] >= 0:
        ans = max(ans, bisect_right(ss, t-dp[n][i]) + i)

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

k = int(input())

num = 0
ans = -1
for i in range(10 ** 7):
    num *= 10
    num += 7
    num %= k
    if num == 0:
        ans = i + 1
        break

print(ans)


### FIXED CODE ###

k = int(input())

num = 0
ans = -1
for i in range(10 ** 7):
    num *= 10
    num += 7
    num %= k
    if num == 0:
        ans = i + 1
        break

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

# D - Knapsack Queries on a tree

from sys import stdin
import bisect

readline = stdin.readline
bisect_right = bisect.bisect_right

n = int(readline())

v = [0] * n
w = [0] * n
for i in range(n):
    v[i], w[i] = map(int, readline().split())

max_l = 10 ** 5
INF = float('inf')

# dp table (for some amount)
dp = [None] * min(n, 2 ** 10)

# dp[vertex] = list of (weight, value)
dp[0] = [(0, 0), (w[0], v[0])]

for u in range(1, len(dp)):
    parent = (u - 1) // 2

    ls = dp[parent][:]
    ls.extend((ww + w[u], vv + v[u]) for ww, vv in dp[parent]
              if ww + w[u] <= max_l)
    ls.sort()

    # remove unnecessary entries
    tail = 0
    for i in range(1, len(ls)):
        if ls[tail][0] == ls[i][0]:
            ls[tail] = ls[i]
        elif ls[tail][1] < ls[i][1]:
            tail += 1
            ls[tail] = ls[i]
    del ls[tail + 1:]
    dp[u] = ls

def solve(u, l):
    if u < len(dp):
        x = bisect_right(dp[u], (l, INF)) - 1
        return dp[u][x][1]

    parent = (u - 1) // 2
    s = solve(parent, l)
    if l >= w[u]:
        s = max(s, v[u] + solve(parent, l - w[u]))
    return s

q = int(readline())
for i in range(q):
    u, l = map(int, readline().split())
    print(solve(u - 1, l))


### FIXED CODE ###

# D - Knapsack Queries on a tree

from sys import stdin
import bisect

readline = stdin.readline
bisect_right = bisect.bisect_right

n = int(readline())

v = [0] * n
w = [0] * n
for i in range(n):
    v[i], w[i] = map(int, readline().split())

max_l = 10 ** 5
vshift = 21
mask = (1 << vshift) - 1

# dp table (for some amount)
dp = [None] * min(n, 2 ** 12)

# dp[vertex] = list of (weight, value)
dp[0] = [(0 << vshift) + 0, (w[0] << vshift) + v[0]]

for u in range(1, len(dp)):
    parent = (u - 1) // 2

    ls = dp[parent][:]
    ls.extend(x + (w[u] << vshift) + v[u] for x in dp[parent]
              if (x >> vshift) + w[u] <= max_l)
    ls.sort()

    # remove unnecessary entries
    tail = 0
    for i in range(1, len(ls)):
        if (ls[tail] >> vshift) == (ls[i] >> vshift):
            ls[tail] = ls[i]
        elif (ls[tail] & mask) < (ls[i] & mask):
            tail += 1
            ls[tail] = ls[i]
    del ls[tail + 1:]
    dp[u] = ls

def solve(u, l):
    if u < len(dp):
        x = bisect_right(dp[u], (l << vshift) + mask) - 1
        return dp[u][x] & mask

    parent = (u - 1) // 2
    s = solve(parent, l)
    if l >= w[u]:
        s = max(s, v[u] + solve(parent, l - w[u]))
    return s

q = int(readline())
for i in range(q):
    u, l = map(int, readline().split())
    print(solve(u - 1, l))
### BUGGY CODE ###

import sys,math,collections,itertools
input = sys.stdin.readline

H,W,M=map(int,input().split())
bom = [] #ボムの場所
bomH =[0]*(H+1) 
bomW=[0]*(W+1)

for _ in range(M):
    h,w=map(int,input().split())
    bom.append((h,w))
    bomH[h]+=1
    bomW[w]+=1

#縦の爆弾と横の爆弾は独立。爆弾を置く場所に爆弾があると-1
max_bomH = max(bomH)
max_bomW = max(bomW)

index_max_H = []
index_max_W = []

for ih in range(H+1):
    if bomH[ih] == max_bomH:
        index_max_H.append(ih)

for iw in range(W+1):
    if bomW[iw] == max_bomW:
        index_max_W.append(iw)

point = itertools.product(index_max_H,index_max_W)#置き場所候補
sPoint = set(point)
sBom = set(bom)
#爆弾が置き場所候補から爆弾場所を消す,すべてなくなれば、-1,どこか残れば0
for sb in sBom:
    sPoint.discard(sb)

print(max_bomH+max_bomW - (len(sPoint)==0) )
    


### FIXED CODE ###

import sys,math,collections,itertools
input = sys.stdin.readline

H,W,M=map(int,input().split())
bom = [] #ボムの場所
bomH =[0]*(H+1) 
bomW=[0]*(W+1)

for _ in range(M):
    h,w=map(int,input().split())
    bom.append((h,w))
    bomH[h]+=1
    bomW[w]+=1

#縦の爆弾と横の爆弾は独立。爆弾を置く場所に爆弾があると-1
max_bomH = max(bomH)
max_bomW = max(bomW)

cnt = 0#爆弾が置かれた場所のbomH,bomWがともにMaxの場所の数
for h,w in bom:
    if bomH[h]==max_bomH and bomW[w] == max_bomW:
        cnt += 1

print(max_bomH +max_bomW -(cnt == bomH.count(max_bomH) * bomW.count(max_bomW)))
### BUGGY CODE ###

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

array=map(int,input().split())

A=list(array)
A.insert(0,0)

visit=[]
visited=1
once=0
while True:
    visit.append(visited)
    once+=1
    if A[visited] in visit:
        break
    visited=A[visited]

roop=visit[visit.index(A[visited]):]
if K<once:
    print(visit[K])
else:
    order=K-once
    print(roop[order%len(roop)])

### FIXED CODE ###

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

array=map(int,input().split())

A=list(array)
A.insert(0,0)

visit=0
root=[]
visited=1
once=0
while True:
    if visit & (0b1<<visited):
        break
    root.append(visited)
    visit|=0b1<<visited
    once+=1
    visited=A[visited]

roop=root[root.index(visited):]
if K<once:
    print(root[K])
else:
    order=K-once
    print(roop[order%len(roop)])