Harryxun/stf_run huggingface dataset:
import numpy as np

S = input()
mod = 10**9 + 7
dp = np.zeros(13)
dp[0] = 1

M = np.zeros((13, 13))
for i in range(13):
    for d in range(10):
        M[i][(i * 10 + d) % 13] += 1

for i in range(len(S)):
    ndp = np.zeros(13)
    if S[i] == '?':
        ndp = np.matmul(dp, M)
    else:
        d = int(S[i])
        for j in range(13):
            ndp[(j * 10 + d) % 13] += dp[j]
    dp = ndp % mod
print(int(dp[5])


### FIXED CODE ###

import numpy as np
 
s = input()
p = np.array([0]*13)
p[0] = 1
 
amari = [[0]*13 for _ in range(13)]
for j in range(10):
  for i in range(13):
    amari[i][(i*10+j)%13] += 1
M = np.array(amari)
 
for si in range(len(s)):
  a = np.array([0]*13)
  if s[si] == '?':
    a = np.dot(p,M)
  else:
    c = int(s[si])
    for i in range(13):
      a[(i*10+c)%13] += p[i]
  p = np.mod(a,1000000007)
print(p[5])
s = [list(map(int,input().split())) for i in range(2)]
t = s[0]
N = t[0]
K = t[1]
H = s[1]
for i in range(K):
    a = max(H)
    H.remove(a)
print(sum(H))

### FIXED CODE ###

s = [list(map(int,input().split())) for i in range(2)]
t = s[0]
N = t[0]
K = t[1]
H = s[1]
if K > N:
    print(0)
else:
    H.sort()
    H[N - K:N]=[]
    print(sum(H))
n=int(input())
sp=[]
for i in range(n):
  s,p=input().split()
  p=int(p)
  sp.append([s,p,i+1])

sp.sort(key=lambda sp:(sp[0],-sp[1])
for n in sp:
  print(i[2])

### FIXED CODE ###

n=int(input())
sp=[]
for i in range(n):
  s,p=input().split()
  p=int(p)
  sp.append([s,p,i+1])

sp.sort(key=lambda sp:(sp[0],-sp[1]))
for i in sp:
  print(i[2])
#4
N = int(input())
x,y,k = 0,0,0

x = int(0.8*N)

for i in range(x,N):
    k = str(i*108)
    if int(k[0:-2]) == N:
        print(i)
        y +=1
        break

if y !=1:
    print(":(")

    

### FIXED CODE ###

#4
import sys
N = int(input())
x,y,k = 0,0,0

if N == 1:
    print(1)
    sys.exit()
elif N <= 12:
    print(N)
    sys.exit()
x = int(0.8*N)

for i in range(x,N):
    k = str(i*108)
    if int(k[0:-2]) == N:
        print(i)
        y +=1
        break

if y !=1:
    print(":(")
from itertools import combinations
 
N = int(input())
d = list(map(int(input().split())))
 
score = 0
for i,j in combinations(range(N), 2):
  score += d[i] * d[j]
print(score)

### FIXED CODE ###

from itertools import combinations
 
N = int(input())
d = list(map(int, input().split()))
 
score = 0
for i,j in combinations(range(N), 2):
  score += d[i] * d[j]
print(score)
# -*- coding: utf-8 -*-

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

ans = 0
for i in range(int(X)):
    for h in range(int(X)):
        if X == 1 * i + 2 * h:
            a = i
            b = h
if Y == 1 * b + 2 * a:
    ans = (a + b) 

print(ans % (10 ** 9 + 7))


### FIXED CODE ###

# -*- coding: utf-8 -*-
#コンビネーション
def cmb(n, r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod

N = 10 ** 6  # N は必要分だけ用意する
mod = pow(10, 9) + 7
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

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

import math
x, y = map(int,input().split())

if (2 * y - x) % 3 != 0 and (2 * x - y) % 3 != 0:
    print(0)
else:
    a = (2 * y - x) // 3
    b = (2 * x - y) // 3
    ans = cmb(a+b, a)
    print(ans % (pow(10, 9) + 7))
import sys
sys.setrecursionlimit(100000)

N = int(input())
T = []
for i in range(N):
    T.append(int(input()))

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

lcm = 1
for i in T:
    lcm = int(lcm * i / gcd(lcm, i))

print(lcm)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

N = int(input())
T = []
for i in range(N):
    T.append(int(input()))

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

lcm = 1
for i in T:
    lcm = int(lcm * i // gcd(lcm, i))

print(lcm)
A = input()

S = 0
lis = [0] * 2019
lis[0] += 1
l = len(A)+1
d = 1

for n in reversed(A):
    S += int(n)*d
    sm = S % 2019
    lis[sm] += 1
    d *= 10

result = 0

for n in lis:
    result += (n*(n-1)/2)


print(int(result))


### FIXED CODE ###

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

if W >= S:
    print('unsafe')
else:
    print('safe')
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, Q = map(int, input().split())
    *C, = map(int, input().split())

    last = [-1]*(N+1)
    P = [[] for _ in [0]*(N+1)]
    for i, c in enumerate(C):
        if last[c] != -1:
            P[last[c]].append(i+1)
        last[c] = i+1

    queries = [[] for _ in [0]*(N+1)]
    indices = [[] for _ in [0]*(N+1)]
    for i in range(Q):
        l, r = map(int, input().split())
        queries[l].append(r)
        indices[l].append(i)

    def add(A, i, x):
        while i <= N:
            A[i] += x
            i += i & -i

    def sum(A, i):
        ret = 0
        while i:
            ret += A[i]
            i ^= i & -i
        return ret

    A = [0]*(N+1)
    ans = [0]*Q
    for l in range(N, 0, -1):
        for cr in P[l]:
            add(A, cr, 1)
        for i, r in zip(queries[i], queries[l]):
            ans[i] = r-l+1-sum(A, r)

    print(*ans, sep='\n')


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N, Q = map(int, input().split())
    *C, = map(int, input().split())

    last = [-1]*(N+1)
    P = [[] for _ in [0]*(N+1)]
    for i, c in enumerate(C):
        if last[c] != -1:
            P[last[c]].append(i+1)
        last[c] = i+1

    queries = [[] for _ in [0]*(N+1)]
    for i in range(Q):
        l, r = map(int, input().split())
        queries[l].append((r, i))

    def add(A, i, x):
        while i <= N:
            A[i] += x
            i += i & -i

    def sum(A, i):
        ret = 0
        while i:
            ret += A[i]
            i ^= i & -i
        return ret

    A = [0]*(N+1)
    ans = [0]*Q
    for l in range(N, 0, -1):
        for cr in P[l]:
            add(A, cr, 1)
        for r, i in queries[l]:
            ans[i] = r-l+1-sum(A, r)

    print(*ans, sep='\n')


if __name__ == '__main__':
    main()
from heapq import*
import sys
r=sys.stdin.readline
def g(n,E,S,G):
 F=[1e7]*-~n;F[S],H=0,[(0,S)]
 while H:
  c,u=heappop(H)
  if u==G:return c
  for f,v in E[u]:
   t=c+f
   if t<F[v]:F[v]=t;heappush(H,(t,v))
 return-1
def s(n,k):
 E=[[]for _ in[0]*-~n]
 for _ in[0]*k:
  f=r();p=map(int,f[2:].split())
  if'0'==f[0]:print(g(n,E,*p))
  else:c,d,e=p;E[c],E[d]=E[c]+[(e,d)],E[d],[(e,c)]
for e in iter(r,'0 0\n'):s(*map(int,e.split()))


### FIXED CODE ###

def s():
 import sys
 r=sys.stdin.readline
 I=float('inf')
 for e in iter(r,'0 0\n'):
  n,k=map(int,e.split())
  F=[[I]*-~n for _ in[0]*-~n]
  for i in range(1,n+1):F[i][i]=0
  for _ in[0]*k:
   f=r();g=map(int,f[2:].split())
   if'0'==f[0]:a,b=g;A=F[a][b];print([A,-1][A==I])
   else:
    c,d,e=g
    if e<F[c][d]:
     for i in range(2,n+1):
      for j in range(1,i):
       F[i][j]=F[j][i]=min(F[i][j],F[i][c]+e+F[d][j],F[i][d]+e+F[c][j])
s()
n,m=[int(i) for i in input().split()]
a=[]
for i in range(m):
    l,r=[int(i) for i in input().split()]
    a.append(set(range(l,r+1)))
for i in range(m):
  a[0]=a[0] & a[1]
print(len(a))

### FIXED CODE ###

n, m=[int(i) for i in input().split()]

maxL = float("-inf")
minR = float("inf")

for i in range(m):
    l, r = [int(i) for i in input().split()]
    maxL, minR = max(maxL, l), min(minR, r)

print(max(0, minR - maxL + 1))
import math
from fractions import gcd

l, r, p1, p2 = list(map(int, input().split()))
lcm = int(l*r / gcd(p1, p2))
ans = (r-l+1) - (math.floor(r/p1)-math.ceil(l/p1)+1) - (math.floor(r/p2)-math.ceil(l/p2)+1) + math.floor(r/lcd)-math.ceil(l/lcd)+1
print(ans)


### FIXED CODE ###

import math
import fractions
l, r, p1, p2 = list(map(int, input().split()))
lcm = p1*p2 // fractions.gcd(p1, p2)
ans = (r-l+1) - (r//p1-(l-1)//p1) - (r//p2-(l-1)//p2) + (r//lcm)-(l-1)//lcm
print(ans)
AE = []
for i in range(5):
    AE.append(int(input()))

ans = 0
mini = []
for i in AE:
    if(i%10 == 0):
        ans += i
    else:
        ans += (i//10 + 1)*10
        mini.append(i%10)
print(ans + min(mini) - 10)

### FIXED CODE ###

AE = []
for i in range(5):
    AE.append(int(input()))

ans = 0
mini = []
for i in AE:
    if(i%10 == 0):
        ans += i
    else:
        ans += (i//10 + 1)*10
        mini.append(i%10)
if(mini != []):
    print(ans + min(mini) - 10)
else:
    print(ans)
a,b,c,d=input().split()
a=int(a)
b=int(b)
c=int(c)
d=int(d)
if a>=b:
  if c>=d:
    print(b+d)
  else:
    print(b+c)
else:
  if c>=d:
    print(a+d)
  else:
    print(a+c)

### FIXED CODE ###

a=int(input())
b=int(input())
c=int(input())
d=int(input())
if a>=b:
  if c>=d:
    print(b+d)
  else:
    print(b+c)
else:
  if c>=d:
    print(a+d)
  else:
    print(a+c)
st = input()
hash_set = set()
for item in st:
    hash_set.add(item)

a = "abcdefghijklmnopqrstuvwxyz"

flag = False
for item in a:
    if item in b:
        print(item)
        break

if flag == False:
    print("None")


### FIXED CODE ###

st = input()
hash_set = set()
for item in st:
    hash_set.add(item)

a = "abcdefghijklmnopqrstuvwxyz"

flag = False
for item in a:
    if not item in hash_set:
        print(item)
        flag = True
        break

if flag == False:
    print("None")
mport math
K=int(input())
k=0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            d=math.gcd(a,b)
            d=math.gcd(d,c)
            k+=d
print(k)


### FIXED CODE ###

import math
K=int(input())
k=0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            d=math.gcd(a,b)
            d=math.gcd(d,c)
            k+=d
print(k)
n = int(input())
a=0
w=0
t=0
r=0

for i in range(n):
    ans = input()

    if ans == 'AC':
        a+=1
    elif ans == 'WA':
        w+=1
    elif ams == 'TLE':
        t+=1
    else:
        r+=1

print("AC x" +str(a))
print("WA x" +str(w))
print("TLE x" +str(t))
print("RE x" +str(r))



### FIXED CODE ###

n = int(input())
a=0
w=0
t=0
r=0

for i in range(n):
    ans = input()

    if ans == 'AC':
        a+=1
    elif ans == 'WA':
        w+=1
    elif ans == 'TLE':
        t+=1
    else:
        r+=1

print("AC x"+" "+str(a))
print("WA x"+" "+str(w))
print("TLE x"+" "+str(t))
print("RE x"+" "+str(r))
s = input()
s1 = s[:s//2]
s2 = s[-1 * (s//2):]
ans = 0
for i in range(s//2):
  if s1[i] != s2[i]:
    ans += 1
print(ans)    


### FIXED CODE ###

n = input()
s = len(n)
s1 = n[:s//2]
s2 = n[-1 * (s//2):]
s2 = s2[::-1]
ans = 0
for i in range(s//2):
  if s1[i] != s2[i]:
    ans += 1
print(ans)
N = int(input())
l = list(map(int.input().split()))

if 2 * max(l) < sum(l):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

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

if 2 * max(l) < sum(l):
    print("Yes")
else:
    print("No")
from collections import Counter

a = map(int, input().split())
b = Counter([input() for _ in range(a)])
for k,v in b.items():
  print(f"{k} x {v}")

### FIXED CODE ###

from collections import Counter
 
a = int(input())
b = [input() for _ in range(a)]
for v in ["AC", "WA", "TLE", "RE"]:
  print(f"{v} x {b.count(v)}")
K = int(input())

result = ""

for i in range(K):
  if i == K - 1:
    result += K
  else:
    result += K
    
print(K)
print(result)


### FIXED CODE ###

K = int(input())

N = 50

ans = [i for i in range(N)]
x,y = divmod(K,N)

ans = list(map(lambda a:a+x,ans))

for i in range(y):
    ans[i] += N + 1
    ans = list(map(lambda a:a-1,ans))

print(N)
print(*ans)
from math import gcd
from functools import reduce
import sys

def get_gcd(number_list):
    return reduce(gcd, number_list)

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

gcd_list = []
for i in range(N):
    tmp_list = Numbers[:i] + Numbers[i + 1:]
    gcd_list.append(get_gcd(tmp_list))
print(int(max(gcd_list)))


### FIXED CODE ###

from functools import reduce
from itertools import combinations
from fractions import gcd

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


Left = [0] * (N + 1)
Right = [0] * (N + 1)

for i in range(N):
    Left[i + 1] = gcd(Left[i], A[i])
    Right[N - i - 1] = gcd(Right[N - i], A[N - i - 1])
ans = 0
for i in range(N):
    ans = max(ans, gcd(Left[i], Right[i + 1]))
    
print(ans)
a = 0
b= 0

input_numbers = raw_input()

fori in input_numbers:
   if input_numbers[0] == i:
      a = int(i)
   elif input_numbers[2] == i:
      b = int(i)

print a * b, 2 * (a + b)

### FIXED CODE ###

num = raw_input()
num = num.split()
a = int(num[0])
b = int(num[1])

print a * b, 2 * (a + b)
if (a+b)%3 or a%3 or b%3==0:
    print ('Possible')
else: print('Impossible')

### FIXED CODE ###

c= [int (i) for i in input().split()]
if sum(c)%3==0 or c[0]%3==0 or c[1]%3 ==0:
	print('Possible')
else: print('Impossible')
N = int(input())
a = [sorted(list(int(input()))) for i in range(N)]
b = 0
for i in a:
 b = b + a.count(i)
print(b / 2)

### FIXED CODE ###

from collections import Counter

N = int(input())
a = [''.join(sorted(input())) for i in range(N)]
count = Counter(a).values()
b = 0
for i in count:
    b = b + i * (i-1)
b=int(b/2)
print(b)
import sys
sys.setrecursionlimit(4100000)
import math
INF = 10**9

def main():
    a,b = map(int, input().split())

    print(a*b//math.gcd(a, b))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(4100000)
import math
INF = 10**9
import fractions

def main():
    a,b = map(int, input().split())

    print(a*b//fractions.gcd(a, b))


if __name__ == '__main__':
    main()
n = input()
cnt = 0
for i in range(1,n+1):
  a = len(i)
  if a % 2 == 1:
    cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
cnt = 0
for i in range(1,n+1):
  a = len(str(i))
  if a % 2 == 1:
    cnt += 1
print(cnt)
N = int(input())
a = [int(input()) for i in range(N) ]
count = 0
for i in range(N):
	for n in a:
 		if n % 2 == 0:
    		count += 1
            n /= 2
print(count)

### FIXED CODE ###

N = int(input())
a_list = list(map(int, input().split()))
count = 0
while True:
	odd = 0
	for i in range(N):
		if a_list[i] % 2 == 0:
			a_list[i] = int(a_list[i] / 2)
			count += 1
		else:
			odd += 1
	if odd == len(a_list):
		break
print(count)
N, T = map(int, input().split())

ct = [int(j) for j in input().split() for i in range(H)]

ct.sort(key=lambda x: x[0])

ans = 1001

for i in range(N):
    if ct[i][1] <= T:
        ans = ct[i][0]
        break

print("TLE" if ans == 1001 else ans)


### FIXED CODE ###

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

ct = []

for i in range(N):
    ct.append([int(i) for i in input().split()])

ct.sort(key=lambda x: x[0])

ans = 1001

for i in range(N):
    if ct[i][1] <= T:
        ans = ct[i][0]
        break

print("TLE" if ans == 1001 else ans)
n = int(input())
# n = 100
m = 0
for i in range(1, n+1):
    a = i
    c = 0
    while a % 2 == 0:
        a = a//2
        c += 1
    if c > m:
        x = i
    m = max(m, c)
print(x)


### FIXED CODE ###

n = int(input())
# n = 100
m = 0
x = 1
for i in range(1, n+1):
    a = i
    c = 0
    while a % 2 == 0:
        a = a//2
        c += 1
    if c > m:
        x = i
    m = max(m, c)
print(x)
S=list(input())
while len(S)>0:
    if S[0] == 'h' and S[1] == 'i':
        S.remove('h')
        S.remove('i')
    else:   
        break

if len(S) == 0:
    print('Yes')
else:
    print('No')






### FIXED CODE ###

S=list(input())
while len(S)>1:
    if S[0] == 'h' and S[1] == 'i':
        S.remove('h')
        S.remove('i')
    else:   
        break

if len(S) == 0:
    print('Yes')
else:
    print('No')
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
G = [[] for _ in [0]*N]
for _ in [0]*(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

add = [0]*N
for _ in [0]*M:
    p, x = map(int, input().split())
    p -= 1
    add[p] += x
counter = [0]*N

def dfs(v, p, x):
    counter[v] = x
    for u in G[v]:
        if u == p:
            continue
        dfs(u, v, x+add[u])


dfs(0, -1, add[0])

print(*counter)


### FIXED CODE ###

# AtCoder Beginner Contest 138
# D - Ki
# https://atcoder.jp/contests/abc138/tasks/abc138_d
import sys
sys.setrecursionlimit(10**6)

input = sys.stdin.readline
N, Q = map(int, input().split())

G = [[] for _ in [0]*N]
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

counter = [0]*N

for _ in range(Q):
    p, x = map(int, input().split())
    counter[p-1] += x

visited = [False]*N


def dfs(v=0, x=0):
    visited[v] = True
    counter[v] += x
    for u in G[v]:
        if visited[u]:
            continue
        dfs(u, counter[v])


dfs()
print(*counter)
# coding:utf-8

import math

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

dist_list = [abs(x-y) for x in map(int, input().split())]

dist_list.sort()

if n == 1:
    d = dist_list[0]
else:
    for i in reversed(range(n)):
        if i == n-1:
            d = math.gcd(dist_list[i], dist_list[i-1])
        else:
            d = math.gcd(dist_list[i-1], d)    

print(d)


### FIXED CODE ###

# coding:utf-8

from fractions import gcd 

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

dist_list = [abs(x-y) for x in map(int, input().split())]

if n == 1:
    d = dist_list[0]
else:
    d = gcd(dist_list[1], dist_list[0])
    for i in range(n-2):
        d = gcd(d, dist_list[i+1])

print(d)
N = int(input()) #1行目を取得する
a = list(map(int,input().split()))
 
num = 0
exist_odd = True
while exist_odd:
  num += 1
  for i in range(N):
    if a[i] % 2 == 0:
      a[i] = a[i] / 2
    else:
      exist_odd = False

print(num - 1)

### FIXED CODE ###

s = input()
a = [int(c) for c in s]
b = 0
for i in a:
  if i == 1:
    b += 1
 
print(b)
while 1:
    n = input()
    if n == 0:
        break
    
    sum_a = 0
    sum_b = 0
    
    for i in range(n):
        a,b = map(int, raw_input().split())
        
        if a > b:
            sum_a = sum_a + a + b
        elif a < b:
            sum_b = sum_b + a + b
        elif a == b:
            sum_a = sum_a + a
            sum_b = sum_b + b

    print("%s %s" %(sum_a,sum_b))

        



### FIXED CODE ###

while 1:
    n = int(input())
    if n == 0:
        break
    
    sum_a = 0
    sum_b = 0
    
    for i in range(n):
        a,b = map(int, input().split())
        
        if a > b:
            sum_a = sum_a + a + b
        elif a < b:
            sum_b = sum_b + a + b
        elif a == b:
            sum_a = sum_a + a
            sum_b = sum_b + b

    print(sum_a,sum_b)
import sys
input = sys.stdin.readline

def main():
    n = input()
    l = len(n)
    mody = 2019
    cnt = 0
    for i in range(l - 3):
        x = int(n[i:i + 4])
        x %= mody
        if x == 0:
            cnt += 1
        for j in range(i + 4, l):
            x = 10 * x + int(n[j])
            x %= mody
            if x == 0:
                cnt += 1
    print(cnt)
if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import Counter
S = list(map(int, input()))
P = 2019

def solve(S,P):
    S = S[::-1]
    T = [0] * len(S)
    T[0] = S[0] % P
    power = 1
    for i in range(1, len(S)):
        power *= 10
        power %= P
        T[i] = T[i-1] + power * S[i]
        T[i] %= P
    counter = Counter(T)
    return sum(x * (x - 1) // 2 for x in counter.values()) + counter[0]
print(solve(S,P))
n,k,q = list(map(int, input().split()))
a = [0]*q
for i in range(q):
    tmp = int(input())
    a[tmp-1] += 1

b = ["No"]*n
    

for i in range(n):
    if k - q + a[i] > 0 :
        b[i] = "Yes"

for i in range(n):
    print(b[i])

### FIXED CODE ###

n,k,q = list(map(int, input().split()))
a = [0]*n
for i in range(q):
    tmp = int(input())
    a[tmp-1] += 1

b = ["No"]*n
    

for i in range(n):
    if k - q + a[i] > 0 :
        b[i] = "Yes"

for i in range(n):
    print(b[i])
import numpy as np
import sys
input = sys.stdin.buffer.readline

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

dp = np.zeros((N, 10**5+1), np.int64)
dp[0, vws[0][1]:] = vws[0][0]
for i in range(1, 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:])

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    print(dp[V-1][L])



### 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]))
n, q = map(int, input().split())
tl = [list() for _ in range(n)]
ans = [0] * n

for i in range(n-1):
    a, b = map(int, input().split())
    tl[a-1].append(b)

def rec(p, x):
    ans[p-1] += x
    for num in tl[p-1]:
        rec(num, x)

for i in range(q):
    p, x = map(int, input().split())
    rec(p, x)

print(" ".join(map(str, ans)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
 
n, q = map(int, input().split())
tl = [list() for _ in range(n)]
xl = [0] * n
ans = [0] * n
 
for i in range(n-1):
    a, b = map(int, input().split())
    tl[a-1].append(b-1)
    tl[b-1].append(a-1)
 
for i in range(q):
    p, x = map(int, input().split())
    xl[p-1] += x

def rec(p, parent, x):
    x += xl[p]
    ans[p] = x
    for num in tl[p]:
        if num == parent: continue
        rec(num, p, x)

rec(0, -1, 0)
 
print(*ans)
a,b,c = map(int.input().split())

if a <= b <= c:
  print(a,b,c)

### FIXED CODE ###

x = input().split()
i = list(map(int,x))
 
i.sort()
print('{} {} {}'.format(i[0],i[1],i[2]))
N,A,B,C,D = map(int,input().split())
if N > 18 and D > 1:
	flag = 10 **9
else:
	flag = pow(D,N)
B -= A
if N % 2 == 1:
	if (B % (C + D) <= (N - 1) * (D - C) / 2 or abs(B % (C + D) - (C + D)) <= (N - 1) * (D - C) / 2) and B <= flag and B >= -flag:
		print("YES")
	else:
		print("NO")
else:
	if (abs(B % (C + D) - (D - C) / 2) <= (N - 1) * (D - C) / 2 or (B % (C + D) + (D - C) / 2) mod (C + D) <= (N - 1) * (D - C) / 2) and B <= flag and B >= -flag:
		print("YES")
	else:
		print("NO")

### FIXED CODE ###

N,A,B,C,D = map(int,input().split())
flag = D * (N - 1)
B -= A
if D - C == 0:
	if A == B:
		print("YES")
	else:
		print("NO")
elif N % 2 == 1:
	if (B % (C + D) <= (N - 1) * (D - C) / 2 or abs(B % (C + D) - (C + D)) <= (N - 1) * (D - C) / 2) and B <= flag and B >= -flag:
		print("YES")
	else:
		print("NO")
else:
	if abs(B % (C + D) - (D + C) / 2) <= (N - 1) * (D - C) / 2 and B <= flag and B >= -flag:
		print("YES")
	else:
		print("NO")
A, B= [int(input() )for _ in range(2)]
S = list(input())

if ("".join(S[0:A]+S[B:]).isdigit()) & (S[A]=="-"):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

g = list(map(int,input().split()))
S = str(input())
 
if ((S[:g[0]]+S[g[0]+1:]).isdigit()) &  (S[g[0]]=="-"):
    print("Yes")
else:
    print("No")
A=int(input("Aの文字数を入力:"))
B=int(input("Bの文字数を入力:"))
C=int(input("Cの文字数を入力:"))

if A==5 and B==5 and C==7:
    print("YES")
elif A==5 and B==7 and C==5:
    print("YES")
elif A==7 and B==5 and C==5:
    print("YES")
else:
    print("NO")


### FIXED CODE ###

a, b, c = map(int, input().split())
if a * b * c == 5 * 7 * 5:
  print("YES")
else:
  print("NO")