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

from collections import defaultdict
from numba import jit
from collections import Counter

n = int(input())
a = list(map(int, input().split()))
arr = defaultdict(int)
for k, v in Counter(a).items():
    arr[k] = v
q = int(input())
bc = []
for _ in range(q):
    b, c = map(int, input().split())
    bc.append((b, c))


@jit
def solve(n, arr, bc):
    for b, c in bc:
        arr[c] += arr[b]
        arr[b] = 0
        print(sum([x * y for x, y in arr.items()]))


solve(n, arr, bc)

### FIXED CODE ###

from collections import defaultdict
from collections import Counter

n = int(input())
a = list(map(int, input().split()))
arr = defaultdict(int)
for k, v in Counter(a).items():
    arr[k] = v
q = int(input())
bc = []
for _ in range(q):
    b, c = map(int, input().split())
    bc.append((b, c))

whole = sum([x * y for x, y in arr.items()])

for b, c in bc:
    arr[c] += arr[b]
    tmp = arr[b]
    arr[b] = 0
    whole += (c - b) * tmp
    print(whole)
### BUGGY CODE ###

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

ans = [ [ 12345678 for _ in range(w) ] for d in range(h)]

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            ans[i][j] = 0

for i in range(h):
    for j in range(1,w):
        ans[i][j] = min(ans[i][j], ans[i][j-1]+1)
    for j in range(w-1-1,-1,-1):
        ans[i][j] = min(ans[i][j],ans[i][j+1]+1)

for j in range(w):
    for i in range(1,h):
        ans[i][j] = min(ans[i][j], ans[i-1][j]+1)
    for i in range(h-1-1,-1,-1):
        ans[i][j] = min(ans[i][j], ans[i+1][j]+1)

ma =-4
for x in ans:
    for y in x:
        ma = max(ma,y)
print(ma)

### FIXED CODE ###

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

ans = [ [ 12345678 for _ in range(w) ] for d in range(h)]

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            ans[i][j] = 0

for i in range(h):
    for j in range(1,w):
        ans[i][j] = min(ans[i][j], ans[i][j-1]+1)
    for j in range(w-1-1,-1,-1):
        ans[i][j] = min(ans[i][j],ans[i][j+1]+1)

for j in range(w):
    for i in range(1,h):
        ans[i][j] = min(ans[i][j], ans[i-1][j]+1)
    for i in range(h-1-1,-1,-1):
        ans[i][j] = min(ans[i][j], ans[i+1][j]+1)

ma =-4
for x in ans:
    for y in x:
        ma = max(ma,y)
print(ma)
### BUGGY CODE ###

k,s=map(int,input().split())
ans=0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z == s:
                ans +=1

print(ans)


### FIXED CODE ###

k,s=map(int,input().split())
ans=0

for x in range(k,-1,-1):
    if s-x > k*2:
        break
    if s < x:
        continue
    for y in range(k,-1,-1):
        if s-x-y > k:
            break
        if 0<= s-x-y <=k:
            ans +=1

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

import math , sys

H,W = list(map( int, input().split() ))
maze = []
for i in range(H):
    maze.append(input())
if H==1:
    print(W-1)
    sys.exit()
if W ==1:
    print(H-1)
    sys.exit()
    
di = [(-1,0),(1,0),(0,1),(0,-1)]
def sol(s,g):
    h = s[0] ; w = s[1]
    gh,gw = g
    d = [[math.inf for _ in range(W)] for _ in range(H)]
    cand = []
    dis = 0
    while True:
        for each in di:
            dh , dw = each
            if h + dh>=0 and h + dh<H and w + dw>=0 and w + dw<W and maze[h+dh][w+dw]=="." and d[h+dh][w+dw]>dis+1:
                if h+dh ==gh and w+dw ==gw:
                    return dis+1
                cand.append((h+dh, w+dw))
                d[h+dh][w+dw] = dis +1
        if len(cand)==0:
            break
        h , w =cand.pop(0)
        dis = d[h][w]
    return d[g[0]][g[1]]

ans = 0

for sh in range(H):
    for sw in range(W):
        for gh in range(H):
            for gw in range(W):
                if maze[sh][sw]=="#" or maze[gh][gw]=="#":
                    continue
                ans = max(ans, sol((sh,sw),(gh,gw)))
print(ans)

### FIXED CODE ###

import math , sys

H,W = list(map( int, input().split() ))
maze = []
for i in range(H):
    maze.append(input())
if H==1:
    print(W-1)
    sys.exit()
if W ==1:
    print(H-1)
    sys.exit()

di = [(-1,0),(1,0),(0,1),(0,-1)]
"""
def sol(s,g):
    h = s[0] ; w = s[1]
    gh, gw = g
    d = [[math.inf for _ in range(W)] for _ in range(H)]
    cand = []
    dis = 0
    while True:
        for each in di:
            dh , dw = each
            if h + dh>=0 and h + dh<H and w + dw>=0 and w + dw<W and maze[h+dh][w+dw]=="." and d[h+dh][w+dw]>dis+1:
                cand.append((h+dh, w+dw))
                d[h+dh][w+dw] = dis +1
        if len(cand)==0:
            break
        h , w =cand.pop(0)
        dis = d[h][w]
    return d[g[0]][g[1]]
"""
ans = 0
for h in range(H):
    for w in range(W):
        if maze[h][w]=="#":
            continue
        d = [[math.inf for _ in range(W)] for _ in range(H)]
        cand = []
        dis = 0
        while True:
            for each in di:
                dh , dw = each
                if h + dh>=0 and h + dh<H and w + dw>=0 and w + dw<W and maze[h+dh][w+dw]=="." and d[h+dh][w+dw]>dis+1:
                    cand.append((h+dh, w+dw))
                    d[h+dh][w+dw] = dis +1
                    ans = max(ans, dis+1)
            #print(h,w,cand, d,dis,ans)
            if len(cand)==0:
                break
            h , w =cand.pop(0)
            dis = d[h][w]

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

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

sumsofAandB = sorted([a+b for a in A for b in B])
sumsofAll = sorted([ab+c for ab in sumsofAandB for c in C], reverse=True)
for i in range(K):
    print(sumsofAll[i])

### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

sumsofAandB = sorted([a+b for a in A for b in B], reverse=True)[:K]
sumsofAll = sorted([ab+c for ab in sumsofAandB for c in C], reverse=True)
for i in range(K):
    print(sumsofAll[i])
### BUGGY CODE ###

s=int(input());
for n in range(1,3501):
    for h in range(1,3501):
        x=4*h*n-s*n-s*h
        if x>0:
            if ((s*h*n)/x).is_integer():
                print(int((s*h*n)/x),h,n)
                exit()

### FIXED CODE ###

s=int(input());
for n in range(1,3501):
    for h in range(1,3501):
        x=4*h*n-s*n-s*h
        if x>0:
            if ((s*h*n)/x).is_integer():
                print(int((s*h*n)/x),h,n)
                exit()
### BUGGY CODE ###

s = input()

q = int(input())
r = 0
b = ""
c = ""
for i in range(q):
    A = list(input().split())
    if A[0] == '1':
        r += 1
    else:
        if (A[1] == '1' and r % 2 == 0) or (A[1] != '1' and r % 2 != 0):
            b = A[2] + b
        else:
            c = c + A[2]
s = b + s + c
if r % 2 == 0:
    print(s)
else:
    print(s[::-1])


### FIXED CODE ###

from collections import deque

s = deque(input())

q = int(input())
r = 0
for _ in range(q):
    A = list(input().split())
    if A[0] == '1':
        r = (r + 1)%2
    else:
        if (A[1] == '1' and r % 2 == 0) or (A[1] == '2' and r % 2 == 1):
            s.appendleft(A[2])
        else:
            s.append(A[2])

if r == 1:
    s.reverse()
print("".join(s))
### BUGGY CODE ###

import copy
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
  ans = 0
  b = copy.copy(a)
  b.pop(i)
  c = list(set(b))
  for j in range(len(c)):
    d = b.count(c[j])
    ans += (d*(d-1))//2
  print(ans)
  
         

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
k = [0]*n
for i in a:
  k[i-1]+=1
g = 0
for i in range(n):
  g+=((k[i]*(k[i]-1))//2)
for i in a:
  print(g+1-k[i-1])
### BUGGY CODE ###

s = input()
t = input()

n = len(t) + 1
m = len(s) + 1

data = [[0 for _ in range(n)] for _ in range (m)]

ans = ''
for i in range(1,m) :
  for j in range(1,n) :
    if s[i-1] == t[j-1] :
      data[i][j] = data[i-1][j-1] + 1
    else :
      data[i][j] = max(data[i-1][j] , data[i][j-1])

i = len(s)
j = len(t)

while i>0 and j>0 :
  if data[i][j] == data[i][j-1] :
    j -= 1
  elif data[i][j] == data[i-1][j] :
    i -= 1
  else :
    ans = s[i-1] + ans
    i -= 1
    j -= 1
    
print(ans)

### FIXED CODE ###

s = input()
t = input()

n = len(t) + 1
m = len(s) + 1

data = [[0 for _ in range(n)] for _ in range (m)]

ans = ''
for i in range(1,m) :
  for j in range(1,n) :
    if s[i-1] == t[j-1] :
      data[i][j] = data[i-1][j-1] + 1
    else :
      data[i][j] = max(data[i-1][j] , data[i][j-1])

i = len(s)
j = len(t)

while i>0 and j>0 :
  if data[i][j] == data[i][j-1] :
    j -= 1
  elif data[i][j] == data[i-1][j] :
    i -= 1
  else :
    ans = s[i-1] + ans
    i -= 1
    j -= 1
    
print(ans)
### BUGGY CODE ###

def solve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    ans = 0
    for l in range(0, N):
        s = 0
        for r in range(l, N):
            s += A[r]
            if s % M == 0:
                ans += 1
    return ans

print(solve())


### FIXED CODE ###

def solve():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    ans = 0
    c = {}
    s = [0 for i in range(N+1)]
    s[0] = 0
    for i in range(0, N):
        s[i + 1] = (s[i] + A[i]) % M
    #print(s)
    for i in range(0, N+1):
        if s[i] not in c.keys():
            c[s[i]] = 0
        ans += c[s[i]]
        c[s[i]] += 1
    return ans

print(solve())
### BUGGY CODE ###

N = int(input())
per = [0] + [int(i) for i in input().split()]
res = 0
for i in range(1, N+1):
  flag = True
  if per[i] > min(per[1:i+1]): 
    pass
  else: 
    res += 1
print(res)

### FIXED CODE ###

N = int(input())
per = [0] + [int(i) for i in input().split()]
res = 0
min_per = per[1]
for i in range(1, N+1):
  min_per = min(min_per, per[i])
  flag = True
  if per[i] > min_per: 
    pass
  else: 
    res += 1
print(res)
### BUGGY CODE ###

import  re
s = input().replace("BC", "X")
cnt = 0
while "AX" in s:
  tmp = re.subn("AX", "XA", s)
  s = tmp[0]
  cnt += tmp[1]
print(cnt)

### FIXED CODE ###

cnt, tmp = 0, 0
for c in input().replace("BC", "X"):
  if c == "A":
    tmp += 1
  elif c == "X":
    cnt += tmp
  else:
    tmp = 0
print(cnt)
### BUGGY CODE ###

S = input()
text = S[::-1]
DP = [0] * 13
MOD = 10**9 + 7

if text[0] == '?':
    for i in range(10):
        DP[i] = 1
else:
    DP[int(text[0])] = 1

for i in range(1, len(S)):
    preDP = DP
    DP = [0] * 13
    if text[i] == '?':
        for x in range(10):
            nx = x * 10 ** i
            for k in range(13):
                t = (nx + k) % 13
                DP[t] += preDP[k]
                DP[t] %= MOD
    else:
        y = int(text[i]) * 10 ** i
        for k in range(13):
            t = (y+k) % 13
            DP[t] = preDP[k] % MOD

ans = DP[5]
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
MOD = 10**9 + 7


def main():
    S = input().rstrip()
    DP = [0] * 13
    n = len(S)
    DP[0] = 1

    for i in range(0, n):
        preDP = DP
        DP = [0] * 13
        if S[i] == '?':
            for k in range(13):
                for x in range(10):
                    t = (x + 10*k) % 13
                    DP[t] += preDP[k]
                    DP[t] %= MOD
        else:
            y = int(S[i])
            for k in range(13):
                t = (y+10*k) % 13
                DP[t] += preDP[k]
                DP[t] %= MOD

    ans = DP[5]
    print(ans)


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

# coding: utf-8
from collections import deque


def solve(*args: str) -> str:
    h, w = map(int, args[0].split())
    A = [[c == '.' for c in s] for s in args[1:]]

    Q = deque()
    for y in range(h):
        for x in range(w):
            if not A[y][x]:
                Q.append((x, y, 0))

    ret = 0
    while Q:
        x, y, n = Q.popleft()

        ret = max(ret, n)
        if 0 < x and A[y][x-1]:
            Q.append((x-1, y, n+1))
            A[y][x-1] = False

        if x+1 < w and A[y][x+1]:
            Q.append((x+1, y, n+1))
            A[y][x+1] = False

        if 0 < y and A[y-1][x]:
            Q.append((x, y-1, n+1))
            A[y-1][x] = False

        if y+1 < h and A[y+1][x]:
            Q.append((x, y+1, n+1))
            A[y+1][x] = False

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


### FIXED CODE ###

# coding: utf-8
from collections import deque


def solve(*args: str) -> str:
    h, w = map(int, args[0].split())
    A = [[c == '.' for c in s] for s in args[1:]]

    Q = deque()
    for y in range(h):
        for x in range(w):
            if not A[y][x]:
                Q.append((x, y, 0))

    ret = 0
    while Q:
        x, y, n = Q.popleft()

        ret = max(ret, n)
        if 0 < x and A[y][x-1]:
            Q.append((x-1, y, n+1))
            A[y][x-1] = False

        if x+1 < w and A[y][x+1]:
            Q.append((x+1, y, n+1))
            A[y][x+1] = False

        if 0 < y and A[y-1][x]:
            Q.append((x, y-1, n+1))
            A[y-1][x] = False

        if y+1 < h and A[y+1][x]:
            Q.append((x, y+1, n+1))
            A[y+1][x] = False

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
### BUGGY CODE ###

n = int(input())

nums = input().split()

q = int(input())

ans = []

for _ in range(q):
    b, c = input().split()
    
    nums = " ".join(nums)
    nums = nums.replace(b, c)
    nums = nums.split()
    t = [int(num) for num in nums]
    ans.append(sum(t))

for a in ans:
    print(a)

### FIXED CODE ###

from collections import Counter

n = int(input())

nums = tuple(map(int, input().split()))

count = Counter(nums)
s = sum(nums)

answers = []
q = int(input())
for _ in range(q):
    b, c = map(int, input().split())
    s = s + (c - b) * count[b]
    count[c] += count[b]
    count[b] = 0
    answers.append(s)
    
for answer in answers:
    print(answer)
### BUGGY CODE ###

from collections import defaultdict
n,x = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
mod = 10**9+7
rng = 300
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
def inv(a):
  return pow(a,mod-2,mod)
dp = [{} for i in range(n+1)]
dp[0][x] = 1
for i in range(n):
  for j in range(i+1,n+1):
    for k in dp[i].keys():
      num = dp[i][k]
      k %= a[j-1]
      if k in dp[j]:
        dp[j][k] = (dp[j][k]+num*fctr[n-i-1]*inv(fctr[n-j]))%mod
      else:
        dp[j][k] = (num*fctr[n-i-1]*inv(fctr[n-j]))%mod
ans = 0
for i,x in dp[n].items():
  ans = (ans+i*x)%mod
print(ans)

### FIXED CODE ###

from collections import defaultdict
n,x = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
mod = 10**9+7
dp = [defaultdict(int) for i in range(n+1)]
dp[0][x] = 1
for i in range(1,n+1):
  for j in dp[i-1].keys():
    k = j%a[i-1]
    dp[i][j] = (dp[i][j]+dp[i-1][j]*(n-i))%mod
    dp[i][k] = (dp[i][k]+dp[i-1][j])%mod
ans = 0
for i,x in dp[n].items():
  ans = (ans+i*x)%mod
print(ans)
### BUGGY CODE ###


n = int(input())
ab = str(input())

ans = 0
def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j] and i > j:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A

lenab = len(ab)
for i in range(0, lenab):
    if ans > lenab - i - 1:
        break
    S = ab[i:]
    o = z_algo(S)
    p = o[1:]
    p.append(ans)
    ans = max(p)

print(ans)

### FIXED CODE ###


n = int(input())
ab = str(input())

ans = set([0])
lenab = len(ab)

for h in range(lenab):
    abc = ab[h:]
    lenabc = len(abc)
    i = 1; j = 0
    A = [0]*lenabc
    A[0] = lenabc
    while i < lenabc:
        while i+j < lenabc and abc[j] == abc[i+j] and j < i:
            j += 1
        if j == 0:
            i += 1
        else:
            A[i] = j
            ans.add(j)
            k = 1
            while lenabc - i > k < j - A[k] and j < i - k :
                A[i + k] = A[k]
                k += 1
            i += k;
            j -= k

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

import sys
input = sys.stdin.readline
from collections import deque
n,m,s,t = map(int,input().split())
es = deque([])
der = deque([])
for i in range(m):
  u,v,a,b = map(int,input().split())
  es.append((u-1,v-1,a))
  es.append((v-1,u-1,a))
  der.append((u-1,v-1,b))
  der.append((v-1,u-1,b))

es = tuple(es)
der = tuple(der)
def shortest_path(S,n,w,es): 
  d = [10**15] * n #d[i] : s→iの最短距離
  d[S] = 0
  while True:
    update = False
    for p,q,r in es: # e: 辺iについて [from,to,cost]
      if d[p] != 10**15 and d[q] > d[p] + r:
        d[q] = d[p] + r
        update = True       
    if not update:
      break
  return d

chk = [0]*(n+1)
ES = tuple(shortest_path(s-1,n,m*2,es))
DER = tuple(shortest_path(t-1,n,m*2,der))
for i in range(n-1,-1,-1):
  chk[i] = max(chk[i+1],10**15-ES[i]-DER[i])

chk = tuple(chk)
for i in range(n):
  print(chk[i])

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque
n,m,s,t = map(int,input().split())
egg = [[] for i in range(n)]
es = [[] for i in range(n)]
for i in range(m):
  u,v,a,b = map(int,input().split())
  es[u-1].append([a,v-1])
  es[v-1].append([a,u-1]) 
  egg[u-1].append([b,v-1])
  egg[v-1].append([b,u-1]) 

es = tuple(es)
egg = tuple(egg)

import heapq
def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [10**18] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

ES = dijkstra_heap(s-1,es)
EDGE = dijkstra_heap(t-1,egg)
cost = 0
chk = [0]*n
for i in range(n-1,-1,-1):
  cost = max(cost,10**15-ES[i]-EDGE[i])
  chk[i] = cost
chk = tuple(chk)
print(*chk, sep="\n")
### BUGGY CODE ###

n,m = map(int, input().split())
l = [0] * n

ac = 0
wa = 0
ac_done = []
for _ in range(m):
    p, s = input().split()
    p = int(p)
    if s == 'AC' and p not in ac_done:
        ac += 1
        wa += l[p-1]
        ac_done.append(p)
    elif s =='WA' and p not in ac_done:
        l[p-1] = 1 + l[p-1]

print(ac,wa)



### FIXED CODE ###

n,m = map(int, input().split())
l = [0] * n

ac = 0
wa = 0
ac_done = [False] * n

for _ in range(m):
    p, s = input().split()
    p = int(p)
    if ac_done[p-1]:
        continue
    else:
        if s == 'AC':
            ac += 1
            wa += l[p-1]
            ac_done[p-1] = True
        else:
            l[p-1] += 1 

print(ac,wa)
### BUGGY CODE ###

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

ans = 0
for i in range(N):
  for j in range(i):
    f = True
    if P[i] >= P[j]:
      f = False
      break
  else:
    ans += 1
print (ans)


### FIXED CODE ###

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

ans = 0
m_n = N
for i in range(N):
  if m_n >= P[i]:ans += 1
  m_n = min(m_n,P[i])
print (ans)
### BUGGY CODE ###

import sys
import numpy as np
from numba import njit

input = sys.stdin.buffer.readline

N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]

n = min(2**10, N)
vws_arr = np.array(vws, np.int32)

dp = np.zeros((n, 10**5+1), np.int32)
for i in range(n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])


@njit("i4(i4[::1], i4[::1], i4, i4[::1])", cache = True)
def func(vs, ws, L, dp_):
    values = np.zeros(1 << len(vs), np.int32)
    weights = np.zeros(1 << len(vs), np.int32)
    for i in range(len(vs)):
        for bits in range(1 << len(vs)):
            if bits & (1 << i):
                values[bits] += vs[i]
                weights[bits] += ws[i]
    mask = (weights <= L)     
    return np.amax(dp_[L - weights[mask]] + values[mask])

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        Vs = []
        while V >= n:
            Vs.append(V)
            V = (V-1) // 2
        vs = vws_arr[Vs, 0]
        ws = vws_arr[Vs, 1]
        print(func(vs, ws, L, dp[V]))


### FIXED CODE ###

import sys
import numpy as np
from numba import njit

input = sys.stdin.buffer.readline

N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]

n = min(2**11, N)
vws_arr = np.array(vws, np.int32)

dp = np.zeros((n, 10**5+1), np.int32)
for i in range(n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])


@njit("i4(i4[::1], i4[::1], i4, i4[::1])", cache = True)
def func(vs, ws, L, dp_):
    values = np.zeros(1 << len(vs), np.int32)
    weights = np.zeros(1 << len(vs), np.int32)
    for i in range(len(vs)):
        for bits in range(1 << len(vs)):
            if bits & (1 << i):
                values[bits] += vs[i]
                weights[bits] += ws[i]
    ret = 0
    for v, w in zip(values, weights):
        if w <= L:
            ret = max(dp_[L - w] + v, ret)
    return ret

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        Vs = []
        while V >= n:
            Vs.append(V)
            V = (V-1) // 2
        vs = vws_arr[Vs, 0]
        ws = vws_arr[Vs, 1]
        print(func(vs, ws, L, dp[V]))
### BUGGY CODE ###

#! python3
# dictionary.py

# ハッシュ法, チェイン法, 開番地法, etc
# オープンアドレス法で実装する

M = 8193173

def getkey(text):
    dic = {'A': 1, 'T': 2, 'G': 3, 'C': 4}
    sum = 0
    p = 1
    for c in text:
        sum += p*dic[c]
        p *= 5
    return sum

def h1(key):
    return key % M

def h2(key):
    return 1 + (key %(M-1))

def h3(key, i):
    return (h1(key) + i*h2(key)) % M

dict = {}
def find(text):
    global dict
    key = getkey(text)
    i = 0
    while i < M:
        h = h3(key, i)
        if dict.get(h) == None:
            break
        elif dict[h] == text:
            return True
        i += 1
    return False

def insert(text):
    global dict
    key = getkey(text)
    i = 0
    while i < M:
        j = h3(key, i)
        if dict.get(j) == None:
            dict[j] = text
            break
        else:
            i += 1

n = int(input())
for i in range(n):
    op, text = input().split(' ')
    if op == 'insert':
        insert(text)
    elif op == 'find':
        rst = find(text)
        if rst:
            print('yes')
        else:
            print('no')


### FIXED CODE ###

import sys

M = 1046527
def h1(key):
    return key % M

def h2(key):
    return 1 + (key %(M-1))

def h3(key, i):
    return (h1(key) + i*h2(key)) % M

word_dic = {'A': 1, 'T': 2, 'G': 3, 'C': 4}
def getkey(text):
    sum = 0
    p = 1
    for c in text:
        sum += p*word_dic[c]
        p *= 5
    return sum

dict = [None for i in range(M)]
def find(text):
    key = getkey(text)
    i = 0
    while i < M:
        h = h3(key, i)
        if dict[h] == None:
            break
        elif dict[h] == text:
            return True
        i += 1
    return False

def insert(text):

    key = getkey(text)
    i = 0
    while i < M:
        j = h3(key, i)
        if dict[j] == None:
            dict[j] = text
            break
        else:
            i += 1

n = int(input())
operations = sys.stdin.readlines()
for ope in operations:
    op, text = ope.rstrip().split(' ')
    if op == 'insert':
        insert(text)
    elif op == 'find':
        rst = find(text)
        if rst:
            print('yes')
        else:
            print('no')