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

#!/mnt/c/Users/moiki/bash/env/bin/python
N,P = list(map(int, input().split()))
import math


def get_prime(n):
    """ Returns  a list of primes < n """
    sieve = [True] * n
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,n,2) if sieve[i] and  i >= int(math.sqrt(P)+1)]

primax = int(1e8) - 10000000#int(1e7) + 9 * int(1e6) + 9 * int(1e5) + 9 * int(1e4)
primes = get_prime(primax)
# print(primes)


def df(P, p):
    if P >= p:
        cnt = 0
        while P >= p and P % p == 0:
            P = int(P//p)
            cnt += 1
        return cnt
    else:
        raise "P , p error."

gc = []
for p in primes:
    if P % p == 0:
        cnt = df(P, p)
        P = int( P // int(p**cnt))
        gc.append([p, cnt])

ans = 1
for g,cnt in gc:
    if cnt >= N:
        ans *= g**(cnt//N)

print(ans)


### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
N,P = list(map(int, input().split()))
import math

if N == 1:
    print(P)
    exit(0)

def get_prime(n):
    """ Returns  a list of primes < n """
    sieve = [True] * n
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,n,2) if sieve[i]]

primax = int(1e7) + 9 * int(1e6)
primes = get_prime(primax)
# print(primes)



def df(P, p):
    if P >= p:
        cnt = 0
        while P >= p and P % p == 0:
            P = int(P//p)
            cnt += 1
        return cnt
    else:
        raise "P , p error."

gc = []
for p in primes:
    if P % p == 0:
        cnt = df(P, p)
        P = int( P // int(p**cnt))
        gc.append([p, cnt])
ans = 1
for g,cnt in gc:
    if cnt >= N:
        ans *= g**(cnt//N)

debug = 1
for g,cnt in gc:
    debug *= g**cnt

# N > 100:  why WA
# debug < P: under 3 RE
# debug*2 > P:  None
if P > 1e9 and debug != P and  debug < P and N == 1:
    raise "errror"
print(ans)
### BUGGY CODE ###

from itertools import *
n,m=map(int,input().split())
M=m
a=[1]
for i in range(2,int(m**.5)+1):
    while m%i==0:
        m//=i
        a+=[i]
if m!=1:a+=[m]
ans=1
for i in range(len(a)):
    for b in combinations(a,i):
        c=1
        for j in b:
            c*=j
        if c>=n:
            ans=max(ans,M//c)
print(ans)

### FIXED CODE ###

from itertools import *
n,m=map(int,input().split())
M=m
a=[1]
for i in range(2,int(m**.5)+1):
    while m%i==0:
        m//=i
        a+=[i]
if m!=1:a+=[m]
ans=1
for i in range(len(a)):
    for b in combinations_with_replacement(set(a),i):
        c=1
        for j in b:c*=j
        if c>=n and M%c==0:ans=max(ans,M//c)
print(ans)
### BUGGY CODE ###

import copy
class warshallFloyd:
    def __init__(self, adj):
        # math.infはpython3.5以降のみ使用可能
        self.inf = 10 ** 9
        self.dis = copy.deepcopy(adj)
        for i in range(len(adj)):
            for j in range(len(adj)):
                if i != j and adj[i][j] == 0:
                    self.dis[i][j] = self.inf

    # 全ての頂点間の最短距離を算出、
    def search(self):
        for k in range(len(self.dis)):
            for i in range(len(self.dis)):
                for j in range(len(self.dis)):
                    if self.dis[i][j] > self.dis[i][k] + self.dis[k][j]:
                        self.dis[i][j] = self.dis[i][k] + self.dis[k][j]
        return self.dis


def func(n, m, r, adj):
    war = warshallFloyd(adj)
    dis = war.search()

    def depth(visited, prev, last):
        if last == 0:
            # print("visited:{} prev:{}, last:{}".format(
                # visited, r[prev], last))
            return 0
        add = 10 ** 10
        for i in range(len(visited)):
            if not visited[i]:
                _visited = copy.deepcopy(visited)
                _visited[i] = True
                add = min(add, dis[r[prev]][r[i]] + depth(_visited, i, last - 1))
                # print("add:{}".format(add))
        return add

    _min = 10 ** 10
    for i in range(len(r)):
        # iをスタートとする
        visited = [False for _ in range(len(r))]
        visited[i] = True
        _min = min(_min, depth(visited, i, len(r) - 1))
    return str(_min)

n, m, R = [int(i) for i in input().split()]
r = [int(i) - 1 for i in input().split()]
adj = [[0 for _ in range(n)] for _ in range(n)]
for i in range(m):
    a, b, c = [int(i) for i in input().split()]
    adj[a - 1][b - 1] = c
    adj[b - 1][a - 1] = c
print(func(n, m, r, adj))
"""
print("2 vs "+func(3, 3, [0, 1, 2], [[0, 1, 4], [1, 0, 1], [4, 1, 0]]))
print("4 vs "+func(3, 3, [0, 2], [[0, 2, 6], [2, 0, 2], [6, 2, 0]]))
print("3 vs "+func(4, 6, [1, 2, 3], [[0, 4, 6, 1], [4, 0, 3, 2], [6, 3, 0, 1], [1, 2, 1, 0]]))
# print("print(func({}, {}, {}, {}))".format(n, m, r, adj))
"""


### FIXED CODE ###

import itertools
n, m, R = map(int, input().split())
r = list(map(int, input().split()))
dis = [[float("inf") for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    dis[a - 1][b - 1] = c
    dis[b - 1][a - 1] = c

def war(dis):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dis[i][j] > dis[i][k] + dis[k][j]:
                    dis[i][j] = dis[i][k] + dis[k][j]
    return dis
dis = war(dis)
_min = float("inf")
it = itertools.permutations(r)
for iterR in it:
    _dis = 0
    start = iterR[0] - 1
    for end in iterR[1:]:
        _dis += dis[start][end - 1]
        start = end - 1
    _min = min(_min, _dis)
print(_min)
### BUGGY CODE ###

n=int(input())
A=[int(input()) for _ in range(n)]
B=set(A)
ans=0
for i in B:
    c=A.count(i)
    ans+=c%2
print(ans)

### FIXED CODE ###

n=int(input())
A=[int(input()) for _ in range(n)]
B={}
for i in A:
    if i in B:
        B[i]=(1+B[i])%2
    else:
        B[i]=1
print(sum(B.values()))
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
from collections import defaultdict
ns = defaultdict(set)
ds = [0]*n
sts = [None]*m
for i in range(m):
    s,t = map(int, input().split())
    s -= 1
    t -= 1
    ns[t].add(s)
    ds[s] += 1
    sts[i] = (s,t)
def sub(x):
    if x is not None:
        s,t = sts[x]
        if ds[s]<=1:
            return None
        ns[t].remove(s)
        ds[s] -= 1
    ps = [None]*n
    ts = [None]*n
    ps[0] = 1
    ts[0] = 0
    for i in range(1, n):
        pp = 0
        tt = 0
        for v in ns[i]:
            if ps[v]==0:
                continue
            if ds[v]>0:
                pp += ps[v]/ds[v]
            tt += (ts[v]+1)*ps[v]/ds[v]
#             if x==3:
#                 print(v, pp, tt)
        
        ps[i] = pp
        if pp>0:
            ts[i] = tt/pp
#         if x==3:
#             print(ps,ts,ds)
        
#     print(ps, ts, ds, ns)
    if x is not None:
        ns[t].add(s)
        ds[s] += 1
    return ts[n-1]
ans = float("inf")
for i in range(m):
    res = sub(i)
    if res is not None:
        ans = min(ans, res)
if ans==float("inf"):
    ans = sub(None)
print(ans)

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
from collections import defaultdict
ns = defaultdict(set)
ins = defaultdict(set)
ds = [0]*n
sts = [None]*m
for i in range(m):
    s,t = map(int, input().split())
    s -= 1
    t -= 1
    ns[t].add(s)
    ins[s].add(t)
    ds[s] += 1
    sts[i] = (s,t)
ts = [None]*n

def sub(x):
    global ts
    if x is not None:
        s,t = x
#         s,t = sts[x]
        if ds[s]<=1:
            return None
        ns[t].remove(s)
        ins[s].remove(t)
        ds[s] -= 1
    ts[n-1] = 0
    for i in range(n-2, -1, -1):
        tt = 0
        for v in ins[i]:
            tt += (ts[v])
        ts[i] = tt/len(ins[i]) + 1
    if x is not None:
        ns[t].add(s)
        ins[s].add(t)
        ds[s] += 1
    return ts[0]
ans = sub(None)
its = ts[:]
for i in range(n):
    if len(ins[i])>=2:
        mm = max(its[j] for j in ins[i])
        for j in ins[i]:
            if its[j]==mm:
                break
        res = sub((i,j))
        if res is not None:
            ans = min(ans, res)
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
"""
一番大きい偶数を2で割る
それ以外は3倍
を繰り返す
奇数だけになったら終了
"""
# O(n)
def f(L):
    even = []
    for l in L:
        if l%2 == 0:
            even.append(l)

    if even == []:
        return -1
    else:
        return max(even)

maxEven = f(a)
while True:
    if maxEven == -1:
        print(ans)
        exit()
    else:
        for i in range(n):
            if a[i] == maxEven:
                a[i] = a[i] // 2
            else:
                a[i] *= 3
            if a[i]%2 == 0:
                maxEven = max(maxEven, a[i])
        ans += 1

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
"""
一番大きい偶数を2で割る
それ以外は3倍
を繰り返す
奇数だけになったら終了
↓
各項が2で何回われるか の合計
"""
for i in range(n):
    cnt = 0
    tmp = a[i]
    while True:
        if tmp % 2 == 0:
            tmp = tmp // 2
            cnt += 1
        else:
            break
    ans += cnt
print(ans)
### BUGGY CODE ###

from collections import Counter

n, m = map(int, input().split())
ab = sorted([list(map(int, input().split())) for i in range(n)])
c = [[]] * m
a, b = ab[0]
last = a
ad = [b]
for i in range(1, n):
    a, b = ab[i]
    if a == last:
        ad.append(b)
    else:
        if last <= m:
            c[last - 1] = ad
        ad = [b]
    last = a
if a <= m:
    c[a - 1] = ad
choice = {}
ans = 0
for i in range(m):
    choice = dict(Counter(choice) + Counter(c[i]))
    if choice:
        use = max(choice)
        ans += use
        choice[use] -= 1
print(ans)


### FIXED CODE ###

import heapq

n, m = map(int, input().split())
ab = sorted([list(map(int, input().split())) for i in range(n)])
c = [[]] * m
a, b = ab[0]
last = a
ad = [b]
for i in range(1, n):
    a, b = ab[i]
    if a == last:
        ad.append(b)
    else:
        if last <= m:
            c[last - 1] = ad
        ad = [b]
    last = a
if a <= m:
    c[a - 1] = ad
a = [3, 0, 2, 6]
choice = []
heapq.heapify(choice)
ans = 0
for i in range(m):
    for j in c[i]:
        heapq.heappush(choice, -j)
    if choice:
        ans -= heapq.heappop(choice)
print(ans)
### BUGGY CODE ###

def solve():
    from sys import stdin
    f_i = stdin
    
    N = int(f_i.readline())
    
    adj = [[] for i in range(N)]
    for i in range(N - 1):
        A, B = map(int, f_i.readline().split())
        A -= 1
        B -= 1
        adj[A].append(B)
        adj[B].append(A)
    
    mod = 10 ** 9 + 7
    pow2 = [(2 ** i) % mod for i in range(N + 1)]
    
    from sys import setrecursionlimit
    setrecursionlimit(10 ** 6)
    
    ans = 0
    def dfs(node, parent):
        nonlocal ans
        cnt = 1
        for child in adj[node]:
            if child != parent:
                cnt += dfs(child, node)
        
        ans += (pow2[cnt] - 1) * (pow2[N-cnt] - 1) % mod
        return cnt
    
    dfs(0, None)
    
    ans = (ans - N * pow2[N-1] + pow2[N] - 1) % mod
    ans = ans * pow(pow2[N], mod - 2, mod) % mod
    
    print(ans)

solve()

### FIXED CODE ###

from sys import stdin
f_i = stdin

N = int(f_i.readline())

adj = [[] for i in range(N)]
for i in range(N - 1):
    A, B = map(int, f_i.readline().split())
    A -= 1
    B -= 1
    adj[A].append(B)
    adj[B].append(A)

mod = 10 ** 9 + 7

pow2 = [1] * (N + 1)
for i, j in zip(range(N), range(1, N + 1)):
    pow2[j] = pow2[i] * 2 % mod

from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

ans = 0

def dfs(node, parent):
    global ans
    cnt = 1
    
    for child in adj[node]:
        if child != parent:
            cnt += dfs(child, node)
    
    ans += (pow2[cnt] - 1) * (pow2[N-cnt] - 1)
    ans %= mod
    
    return cnt

dfs(0, None)

ans = (ans - N * pow2[N-1] + pow2[N] - 1) % mod
ans = ans * pow(pow2[N], mod - 2, mod) % mod

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

#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
import threading
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [list(map(list, sys.stdin.readline().split())) for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

threading.stack_size(128*1024*1024)

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

dp = [-1]*(K+1)
for a in A:
    dp[a] = 1
for i in range(A[0]):
    dp[i] = 0

def rec(x):
    if (x<0):
        return 1
    if (dp[x]!=-1):
        return dp[x]
    res = 1
    for a in A:
        res &= rec(x-a)
    dp[x] = 1^res
    return dp[x]

print("First" if rec(K) else "Second")


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random
import threading
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [list(map(list, sys.stdin.readline().split())) for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

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

dp = [False]*(K+1)
for a in A:
    dp[a] = True

for i in range(K+1):
    for a in A:
        if (i<a):
            break
        if (not dp[i-a]):
            dp[i] = True
            break

print("First" if dp[K] else "Second")
### BUGGY CODE ###

from itertools import combinations

n = int(input())
A = input()
A = [int(s) for s in A.split()]
q = int(input())
m = input()
m = [int(s) for s in m.split()]

for mm in m:
	ans = 'no'
	for i in range(1,n+1):
		for c in combinations(A,i):
			if sum(c) == mm:
				ans = 'yes'
				break
		if ans == 'yes':
			break
	print(ans)

### FIXED CODE ###

def solve(i,m):
	if m == 0:
		return True
	if i >= n:
		return False
	res = solve(i+1,m) or solve(i+1,m-A[i])
	return res

n = int(input())
A = input()
A = [int(s) for s in A.split()]
q = int(input())
m = input()
m = [int(s) for s in m.split()]

ans = []
s = sum(A)
for mm in m:
	if s < mm:
		ans.append('no')
	else:
		ans.append({True:'yes',False:'no'}[solve(0,mm)])
#ans = [{True:'yes',False:'no'}[solve(0,mm)] for mm in m]
print('\n'.join(ans))
### BUGGY CODE ###

n, m, Q = [int(i) for i in input().split()]
l_list = []
r_list = []
p_list = []
q_list = []
for _ in range(m):
    l, r = [int(i) for i in input().split()]
    l_list.append(l)
    r_list.append(r)

for _ in range(Q):
    p, q = [int(i) for i in input().split()]
    p_list.append(p)
    q_list.append(q)


start_map = [[] for i in range(n)]
end_map = [[] for i in range(n)]

for i in range(m):
    l = l_list[i]
    r = r_list[i]

    start_map[l - 1].append(i)
    end_map[r - 1].append(i)

for i in range(Q):
    count = 0
    p = p_list[i]
    q = q_list[i]
    start_list = []
    end_list = []
    for j in range(p, q+1):
        start_list.extend(start_map[j-1])
        end_list.extend(end_map[j-1])
    rail_set = set(start_list) & set(end_list)

    print(len(rail_set))





### FIXED CODE ###

N,M,Q = map(int,input().split())
l = [[0 for i in range(N)] for j in range(N)]
 
for _ in range(M):
    L,R = map(int,input().split())
    l[L-1][R-1] += 1
 
csum = [[0 for i in range(N+1)] for j in range(N+1)]
 
for i in range(1,N+1):
    for j in range(1,N+1):
        csum[i][j] = csum[i][j-1] + csum[i-1][j] - csum[i-1][j-1] + l[i-1][j-1]
 
for _ in range(Q):
    p,q = map(int,input().split())
    print(csum[q][q]-csum[q][p-1]-csum[p-1][q]+csum[p-1][p-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    N = int(input())
    X = list(map(int, input().split()))
    D = [0 for i in range(N)]

    for i in range(N-1):
        D[i] = X[i+1] - X[i]

    n = 1
    for i in range(1, N):
        n *= i

    ans = 0
    r = 0
    mod = 10**9+7
    for i in range(1, N):
        r += n // i
        r %= mod
        ans += D[i-1] * r
        ans %= mod
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import math
input = sys.stdin.readline

mod = 10**9+7


def main():
    N = int(input())
    r1 = [1]
    for i in range(N-1):
        r1.append(r1[i] * (i+1) % mod)
    r2 = [1]
    for i in range(N-1):
        r2.append(r2[i] * (N-1-i) % mod)

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

    ans = 0
    r = 0
    for i in range(N):
        r += r1[i] * r2[N-i-2]
        ans += D[i] * r
        ans %= mod
    print(ans)


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

N,M = map(int, input().split())
A,B = [],[]
AtN,Bf1 = [],[]
for i in range(M):
    a,b = map(int, input().split())
    if a == 1:
        Bf1 += [b]
    elif b == N:
        AtN += [a]

if (any((b in AtN) for b in Bf1)):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

N,M = map(int, input().split())
AtN,Bf1 = set(),set()
for i in range(M):
    a,b = map(int, input().split())
    if a == 1:
        Bf1.add(b)
    elif b == N:
        AtN.add(a)

if (any((b in AtN) for b in Bf1)):
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

import copy
ans=0
n=int(input())
l=[list(map(int,input().split())) for _ in [0]*n]
o=copy.deepcopy(l)

for k in range(n):
  for i in range(n):
    for j in range(n):
      if l[i][j]>l[i][k]+l[k][j]:
        print(-1)
        exit()
for k in range(n):
  for i in range(n):
    for j in range(n):
        if i==j or j==k or k==i :
            continue
        if o[i][j]==o[i][k]+o[k][j]:
            o[i][j]=float("inf")
for i in range(n):
    for j in range(n):
        if o[i][j] != float("inf") :
            ans+=o[i][j]
print(ans//2)


### FIXED CODE ###

INF = 10 ** 12

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

for i in range(N):
    for j in range(N):
        for k in range(N):
            if a[i][j] > a[i][k] + a[k][j]:
                print(-1)
                exit()

res = 0
for i in range(N):
    for j in range(i + 1, N):
        for k in range(N):
            if i != k and j != k and a[i][j] == a[i][k] + a[k][j]:
                break
        else:
            res += a[i][j]

print(res)
### BUGGY CODE ###

alp = {"a":2, "b":3,"c":5,"d":7,"e":11,"f":13,"g":17,"h":19,"i":23,"j":29,
       "k":31,"l":37,"m":41,"n":43,"o":47,"p":53,"q":59,"r":61,"s":67,"t":71,
       "u":73,"v":79,"w":83,"x":89,"y":97,"z":101}

n = int(input())

s = []

for i in range(n):
    tss= str(input()) # tss; temporary str s
    ts = 1
    for j in range(10):
      ts *= alp[tss[j]] # ts; temporary s
    s.append(ts)

a = 0 # a; pre ans

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

print(a)  

### FIXED CODE ###

n = int(input())
d = dict()

for _ in range(n):
    s = "".join(sorted([x for x in input()]))
    d[s] = d.get(s, 0) + 1

ans = 0

for v in d.values():
    if v >= 2:
        ans += (v * (v-1)) // 2

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

import sys
import numpy as np
from numba import njit

input = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit(cache = True)
def pre(vws):
    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:])
    return dp

@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])

@njit(cache = True)
def query(dp, VLs, vws):
    for V, L in VLs:
        V -= 1
        if V < n:
            print(dp[V, L])
        else:
            vs = []
            ws = []
            while V >= n:
                vs.append(vws[V][0])
                ws.append(vws[V][1])
                V = (V-1) // 2
            print(func(np.array(vs, np.int32), np.array(ws, np.int32), L, dp[V]))

N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]
Q = int(input())
VLs = list(map(lambda s: tuple(map(int, s.split())), readlines()))

n = min(2**10, N)

dp = pre(vws)
query(dp, VLs, vws)

### 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]))