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

import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))
M = 1000000007
ans = 0
for i in range(n-1):
    for j in range(i+1,n):
        ans += A[i] * A[j]
print(ans%M)

### FIXED CODE ###

import sys
input = sys.stdin.readline
M = 1000000007
n = int(input())
A = list(map(int, input().split()))
ans = 0
s = 0
for i in range(n):
    s += A[i]
    s %= M

for i in range(n):
    s = s - A[i]
    if s < 0:
        s += M
    ans += A[i] * s
    ans %= M
print(ans)
### BUGGY CODE ###

import sys

x = int(input())

total = 0

for a in range(0,1000):
    for b in range(0,1000):
        for c in range(0,1000):
            for d in range(0,1000):
                for e in range(0,1000):
                    for f in range(0,1000):
                        total = 100*a + 101*b + 102*c + 103*d + 104*e +105*f
                        if x == total:
                            print(1)
                            sys.exit()

print(0)

### FIXED CODE ###

x = int(input())

# 商品の合計がi個の場合の可能なxの範囲
# i=1   100-105
# i=2   200-210
# i=3   300-315
# i=4   400-420
# i=5   500-525
# i=6   600-630
# i=7   700-735
# i=8   800-840
# i=9   900-945
# ...
# i=19 1900-1995
# i=20以降は常に1

i = x // 100

if 100*i <= x <= 105*i:
  print(1)
else:
  print(0)
### BUGGY CODE ###

N,M=map(int,input().split())
A=sorted(list(map(float,input().split())),reverse=True)
for i in range(M):
    A[0]=A[0]/2
    A=sorted(A,reverse=True)
A=[int(a) for a in A]
print(sum(A))

### FIXED CODE ###

import heapq
N,M=map(int,input().split())
hq=list(map(float,input().split()))
hq=[-n for n in hq]
heapq.heapify(hq)
for i in range(M):
    heapq.heappush(hq,heapq.heappop(hq)/2)
hq=[int(a) for a in hq]
print(-sum(hq))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = map(int, input())
A = list(map(int, input().split()))

while len(A) >= 2:
    x = A.pop(A.index(max(A)))
    n = x
    for i in range(len(A)):
        if x % A[i] > 0:
            n = min(x, x % A[i])

    if n == x:
        pass
    else:
        A.append(n)

print(A[0])


### FIXED CODE ###

# -*- coding: utf-8 -*-
N = map(int, input())
A = list(map(int, input().split()))

while len(A) >= 2:
    idx = A.index(min(A))
    x = A.pop(idx)
    B = list()
    for i in range(len(A)):
        if A[i] % x != 0:
            B.append(A[i] % x)
    B.append(x)
    A = B[:]

print(A[0])
### BUGGY CODE ###

s = input()
sl = len(s)
s = list(s)
while True:
  flag = False
  for i in range(len(s)-1):
    if i+1 > len(s)-1 : break
    if s[i] != s[i+1]:
      s.pop(i+1)
      s.pop(i)
      flag = True
  else:
    if not flag:
      break
print(sl - len(s))

### FIXED CODE ###

s = input()

t = s[0]
for i in s[1:]:
  if not t:
    t=i
    continue
  if i != t[-1]:
    t=t[:-1]
  else:
    t+=i

print(len(s) - len(t))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
q = int(input())
ql = []
R = 0
for _ in range(q):
    l,r = map(int, input().split())
    ql.append((l,r))
    R = max(R,r)
R += 1

primes = []
for n in range(2,R+1):
    flag = True

    for p in primes:
        if n%p==0:
            flag = False
            break
        if n<p*p:
            break

    if flag:
        primes.append(n)

like2017 = [0]*(R+1)
for i in range(R):
    if i%2==1 and (i in primes) and ((i+1)//2 in primes):
        like2017[i+1] = like2017[i] + 1
    else:
        like2017[i+1] = like2017[i]

for (l,r) in ql:
    print(like2017[r+1] - like2017[l])


### FIXED CODE ###

def sieve(n):
    res = list(range(n+10)) # nが小さい時よう
    res[0] = -1
    res[1] = -1
    i = 2
    while i*i<n:
        if res[i]<i:
            i += 1
            continue
        j = i*i
        while j<n:
            if res[j]==j:
                res[j] = i
            j += i
        i += 1
    return res

s = sieve(10**5+10)
acc = [0]*(10**5+10)
for i in range(2,10**5+9):
    if i%2==1 and s[i]==i and s[(i+1)//2]==(i+1)//2:
        acc[i+1] = acc[i]+1
    else:
        acc[i+1] = acc[i]

q = int(input())
res = [0]*q
for i in range(q):
    l,r = map(int, input().split())
    res[i] = acc[r+1]-acc[l]

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

N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]
p = [K] * N
for i in range(N):
    p[i] += A.count(i+1) - Q
    if p[i] > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

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

import sys
import pdb
from bisect import *
from collections import *
from copy import deepcopy
from datetime import *
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    N,Q = map(int, input().split())
    S = input().rstrip()
    ans = [0]*Q
    for q in range(Q):
        l,r = map(int, input().split())
        l -= 1
        r -= 1
        mid = (r+l)//2+1
        cnt = 0
        for i in range(l,mid):
            if S[i:i+2] == 'AC': cnt += 1
        for i in range(mid,r):
            if S[i:i+2] == 'AC': cnt += 1
        print(cnt)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import pdb
from bisect import *
from collections import *
from copy import deepcopy
from datetime import *
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    N,Q = map(int, input().split())
    S = input().rstrip()
    dp = [0]*(N+1)
    for i in range(1,N):
        if S[i-1:i+1] == 'AC':
            dp[i+1] = dp[i]+1
        else:
            dp[i+1] = dp[i]
    for _ in range(Q):
        l,r = map(int, input().split())
        print(dp[r]-dp[l])

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

import numpy as np
N = int(input())

furui = np.zeros(N+1, dtype=float)
for i in range(1, N+1):
    furui[i::i] = furui[i::i]+1

for i in range(1, N+1):
    furui[i] = furui[i]*i

print(int(furui.sum()))




### FIXED CODE ###

N = int(input())

furui = [1]*(N+1)
ans = 1
for i in range(2, N+1):
    k = i
    while k <= N:
        furui[k] += 1
        k += i
    ans += furui[i]*i

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

a=int(input())
li = input().split()
ans = "YES"
for i in li:
    if li.count(i) > 1:
        ans = "NO"
        break
print(ans)

### FIXED CODE ###

a=int(input())
li = input().split()
if len(li) == len(set(li)):
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

S = int(input())
if S <= 10**9:
    print(0,0,S,0,0,1)
else:
    for i in reversed(range(1,int(S**0.5)+1)):
        if S%i == 0:
            print(0, 0, i, 0, 0, S//i)
            exit()

### FIXED CODE ###

S = int(input())
if S <= 10**9:
    print(0,0,S,0,0,1)
elif S == 10**18:
    print(0,0,10**9,0,0,10**9)
else:
    xb = int(S**0.5 + 1)
    yc = int(S**0.5 + 1)
    xc = xb*yc - S
    print(0, 0, xb, 1, xc, yc)
### BUGGY CODE ###

import math

n=int(input())

def keta(n):
    return int(math.log10(n)+1)
def max(a,b):
    if a>b :return a
    else: return b

result=100
for i in range(1,n//2+10):
    if n%i==0 and result>max(keta(i),keta(n//i)):
        result=max(keta(i),keta(n//i))
print(result)


### FIXED CODE ###

import math

n=int(input())

def keta(n):
    return int(math.log10(n)+1)
def max(a,b):
    if a>b :return a
    else: return b

result=100
for i in range(1,math.ceil(math.sqrt(n)+3)):
    if n%i==0 and result>max(keta(i),keta(n//i)):
        result=max(keta(i),keta(n//i))
print(result)
### BUGGY CODE ###

k = int(input())
s = input()
mod = 10**9+7
maxn = 2000005
fact = [0 for i in range(maxn)]
fact[0] = 1
for i in range(1,maxn):
	fact[i] = (i*fact[i-1])%mod
n = len(s)
ans = pow(26,n+k,mod)
for m in range(n):
	calc = (fact[n+k]%mod * pow(fact[m],mod-2,mod))%mod
	calc = (calc * pow(fact[n+k-m],mod-2,mod))%mod
	p = pow(25,n+k-m,mod)
	val = (calc*p)%mod
	ans = (ans-val)%mod
print(ans%mod)

### FIXED CODE ###

k = int(input())
s = input()
mod = 10**9+7
maxn = 2000005
fact = [0 for i in range(maxn)]
fact[0] = 1
for i in range(1,maxn):
	fact[i] = (i*fact[i-1])%mod
n = len(s)
ans = pow(26,n+k,mod)
for m in range(n):
	calc = (fact[n+k]%mod * pow(fact[m],mod-2,mod))%mod
	calc = (calc * pow(fact[n+k-m],mod-2,mod))%mod
	p = pow(25,n+k-m,mod)
	val = (calc*p)%mod
	ans = (ans-val)%mod
print(ans%mod)
### BUGGY CODE ###

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

dp = [[10**12]*((10**3)*N+1) for i in range(N+1)]
dp[0][0] = 0
v_sum = 0
for i in range(N):
    w, v = map(int,input().split())
    v_sum += v
    for j in range((10**3)*N+1):
        if j > v_sum:
            break
        if j - v >= 0:
            dp[i+1][j] = min(dp[i][j],dp[i][j-v]+w)#諸悪の根源
        else:
            dp[i+1][j] =dp[i][j]

for i in range(len(dp[-1])):
    if 0 < dp[-1][i]<= M:
        ans = i
    else:
        pass

print(ans)





### FIXED CODE ###

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

dp = [[10**12]*((10**3)*N+1) for i in range(N+1)]
dp[0][0] = 0
v_sum = 0
for i in range(N):
    w, v = map(int,input().split())
    v_sum += v
    for j in range((10**3)*N+1):
        if j > v_sum:
            break
        if j - v >= 0:
            dp[i+1][j] = min(dp[i][j],dp[i][j-v]+w)#諸悪の根源
        else:
            dp[i+1][j] =dp[i][j]

for i in range(len(dp[-1])):
    if 0 < dp[-1][i]<= M:
        ans = i
    else:
        pass

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

import heapq

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
TF = [False for _ in range(N)]
kouho = []
ans = 0

# 後ろから見て優先度付きキューで取り出す
mae = 0
for i in reversed(range(M)):
    mae += 1
    kouho = []
    for n in range(N):
        if AB[n][0] <= mae and TF[n] != True:
            kouho.append([AB[n][1] * (-1), n])
    heapq.heapify(kouho)
    
    if kouho:
        b, n = heapq.heappop(kouho)
        ans += b*(-1)
        TF[n] = True
    
print(ans)

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
kouho = []
ans = 0

AB = sorted(AB)

# 後ろから見て優先度付きキューで取り出す
n = 0
heapq.heapify(kouho)
for i in range(1, M+1):
    if n < N:
        while AB[n][0] <= i:
            heapq.heappush(kouho, AB[n][1] * (-1))
            n += 1
            if n >= N:
                break
    
    if kouho:
        b = heapq.heappop(kouho)
        ans += b*(-1)
    
print(ans)
### BUGGY CODE ###

from math import factorial

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

    A.sort()
    n = A[-1]
    maxc = 0
    for r in A[:-1]:
        comb = factorial(n) // (factorial(r) * factorial(n - r))
        if maxc < comb:
            ans = r
            maxc = comb
    print(n, ans)

main()


### FIXED CODE ###

import bisect

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

    A.sort()
    n = A[-1]
    i = bisect.bisect_left(A, n / 2)
    if n / 2 - A[i-1] <= A[i] - n / 2:
        r = A[i-1]
    else:
        r = A[i]
    print(n, r)

main()
### BUGGY CODE ###

n = int(input())
a  = list(map(int,input().split()))

a.sort(reverse=True)
dic = {a[0]:1}
ans = 0

for i in range(1,n):
    h = a[i]
    max_h = list(dic)[0]
    
    
    
    if h == max_h:
        dic[h] += 1
        ans += h
    
    else:
        if h in dic:
            dic[h] += 2
            dic[max_h] -= 1
            ans += max_h
        
        else:
            dic[h] = 2
            dic[max_h] -= 1
            ans += max_h
        
        if dic[max_h] == 0:
            del dic[max_h]
    
    

print(ans)
            

### FIXED CODE ###

n = int(input())
a  = list(map(int,input().split()))

a.sort(reverse=True)
dic = {a[0]:1}
ans = 0

for i in range(1,n):
    h = a[i]
    max_h = next(iter(dic))
    
    
    
    if h == max_h:
        dic[h] += 1
        ans += h
    
    else:
        if h in dic:
            dic[h] += 2
            dic[max_h] -= 1
            ans += max_h
        
        else:
            dic[h] = 2
            dic[max_h] -= 1
            ans += max_h
        
        if dic[max_h] == 0:
            del dic[max_h]
    
    

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

n = int(input())
c = input()
cnt = 0
if c.count('WR')==0:
  print(0)
else:
  while c.count('WR')>1:
    pre = -1
    post = -1
    for i,j in enumerate(c):
      if i==len(c)-1:
        continue
      if j=='W' and c[i+1]=='R':
        if pre==-1:
          pre = i
        elif post==-1:
          post = i+1
        else:
          c = c[:pre]+'R'+c[pre+2:post]+'W'+c[post+1:]
          cnt += 1
          break
  for i in c[::-1]:
    if i=='R':
      cnt += 1
    else:
      break
  print(cnt)

### FIXED CODE ###

n = int(input())
c = input()
print(c[:c.count('R')].count('W'))
### BUGGY CODE ###

n = int(input())
height = [int(x) for x in input().split()]
cnt =0
i_index = 0
j_index = 0
for i in height[:n-1]:
    i_index += 1
    j_index = i_index
    for j in height[i_index:]:
        j_index+=1
        if j+i == abs(i_index - j_index):
            cnt += 1

print(cnt)

### FIXED CODE ###

# n = int(input())
# height = [int(x) for x in input().split()]
# cnt =0

# for i_index, i in enumerate(height[:-1]):
#     if i+i_index >= n:
#         continue

#     for j_index, j in enumerate(height[i_index+i+1:]):
#         if j+i == j_index+i+1:
#             cnt += 1
#             # print(i,j,j_index)
            
# print(cnt)
def count(dic,x):
    if x in dic:
        dic[x]+=1
    else:
        dic[x]=1
 
N=int(input())
A=list(map(int,input().split()))
dic1={}
dic2={}
s=0
for i in range(N):
    count(dic1,i-A[i])
    count(dic2,i+A[i])
for x in dic1:
    if x in dic2:
        s+=dic1[x]*dic2[x]
print(s)
### BUGGY CODE ###

def hoge():
  from itertools import permutations
  N, M, R = map(int, input().split())
  r = map(int, input().split())
  inf = float('inf')
  d = [[inf] * N for i in range(N)]

  for i in range(N):
      d[i][i] = 0

  for i in range(M):
      a, b, c = map(int, input().split())
      a -= 1
      b -= 1
      t = min(c, d[a][b])
      if d[a][b] > c:
          d[a][b], d[b][a] = t, t


  for k in range(N):
      for i in range(N):
          for j in range(N):
              d[i][j] = min(d[i][j], d[i][k] + d[k][j])


  ans = inf
  for i in permutations(r):
      temp = 0
      for j in range(len(i)-1):
          temp += d[i[j]-1][i[j+1]-1]
          if temp > ans:
              break
      ans = min(ans, temp)

  print(ans)
hoge()


### FIXED CODE ###

from itertools import permutations

def input_list():
    return list(map(int, input().split()))

def main():
    n, m, r = input_list()
    rlist = input_list()
    rlist = [r-1 for r in rlist]
    d = [[float('inf')]*n for i in range(n)]
    for i in range(n):
        d[i][i] = 0
    
    for i in range(m):
        a, b, c = input_list()
        d[a-1][b-1] = c
        d[b-1][a-1] = c

    for k in range(n):
        for i in range(n):
            for j in range(n):
                distance = d[i][k]+d[k][j]
                if d[i][j] > distance:
                    d[i][j] = distance

    ans = float('inf')
    for p in permutations(rlist):
        distance = 0
        for i in range(r-1):
            distance += d[p[i]][p[i+1]]

        if ans > distance:
            ans = distance

    print(ans)

main()
### BUGGY CODE ###

import sys

sys.setrecursionlimit(500000)
h, n = 0, 0
ab = None
dp = dict()

def input() -> str:
    return sys.stdin.readline().rstrip()

def f(i, j):
    if j <= 0:
        return 0
    if i < 0 and j > 0:
        return float("inf")
    ij = n * j + i
    if ij not in dp:
        dp[ij] = min([f(i - 1, j - k * ab[i][0]) + k * ab[i][1] for k in range((h - 1) // ab[i][0] + 2)])
    return dp[ij]

def main():
    global h, n, ab
    h, n = map(int, input().split())
    ab = sorted([tuple(map(int, input().split())) for _ in range(n)], key=lambda x: -x[0])
    print(f(n - 1, h))

if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys

def input() -> str:
    return sys.stdin.readline().rstrip()

h, n = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]
m = max(a for a, _ in ab)
dp = [0] * (h + m * 2 + 1)
for i in range(-m, h + m + 1):
    if i <= 0:
        dp[i] = 0
    else:
        dp[i] = min(dp[i - a] + b for a, b in ab)
print(min(dp[h:h + m + 1]))
### BUGGY CODE ###

from math import factorial

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod = 10**9+7

if K==1:print(0)
else:
  def comb(n,k):
    return factorial(n)//(factorial(n-k)*factorial(k))

  A1=sorted(A)
  A2=A1[::-1]
  
  ans=0
  for i in range(N-K+1):
    ans += (A2[i]-A1[i])*comb(N-i-1,K-1)
    ans %= mod

  print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod = 10**9+7

if K==1:print(0)
else:
  factorial=[1 for i in range(N+1)]
  for i in range(1,N+1):
    if i==1:factorial[i]=1
    else:factorial[i] = factorial[i-1]*i % mod
  
  def comb(n,k):
    return factorial[n]*pow(factorial[n-k]*factorial[k], -1, mod)

  A1=sorted(A)
  A2=A1[::-1]
  
  ans=0
  for i in range(N-K+1):
    ans += (A2[i]-A1[i])*comb(N-i-1,K-1)
  ans %= mod

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

n = input()
li = list(map(int, input().split())) 

total = 1
li.sort()
for a in li:
    if a == 0:
        total = 0
        break
    total *= a

if 10 ** 18 < total:
    total = -1

print(total)

### FIXED CODE ###

n = input()
li = list(map(int, input().split())) 

total = 1
li.sort()
for a in li:
    if a == 0:
        total = 0
        break
    total *= a
    if 10 ** 18 < total:
        total = -1
        break
print(total)
### BUGGY CODE ###

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

from fractions import gcd
from functools import reduce
max_gcd = 0

for i in range(n+1):
  max_gcd = max(max_gcd, reduce(gcd, A[:i] + A[i+1:]))
print(max_gcd)  

### FIXED CODE ###

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

L = {}
R = {}

L[0] = A[0]
#print("L", 0, L[0])
for i in range(n-1):
  L[i+1] = gcd(L[i], A[i+1])
  #print("L", i+1, L[i+1])

R[n-1] = A[n-1]
#print("R", n-1, R[n-1])
for i in range(n-1):
  R[n-2-i] = gcd(R[n-1-i], A[n-2-i])
  #print("R", n-2-i, R[n-2-i])
  
max_gcd = 0
for i in range(1, n-1):
  max_gcd = max(gcd(L[i-1], R[i+1]), max_gcd)
  #print(i, L[i-1], R[i+1], gcd(L[i-1], R[i+1]))
max_gcd = max((max_gcd, L[n-2], R[1]))
print(max_gcd)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    ans = 0

    for a in A:
        flag = False
        left = bisect_left(A, a)
        right = bisect_right(A, a)

        if right-left > 1:
            continue

        divs = make_divisors(a)
        for d in divs:
            left = bisect_left(A, d)
            right = bisect_right(A, d)
            if left != right and d != a:
                flag = True
                break

        if flag == False:
            ans += 1
    
    print(ans)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

def solve(A):
    n = A[-1]
    is_nodiv = [True for _ in range(n+1)]

    pre = 0
    for a in A:
        if pre == a or not is_nodiv[a]:
            is_nodiv[a] = False
            continue

        for j in range(2*a, n+1, a):
            is_nodiv[j] = False
        
        pre = a
        
    return sum([is_nodiv[a] for a in A])



def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    ans = solve(A)
    print(ans)

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

import sys


def main():
    input = sys.stdin.readline

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

    L_MAX = 10**5
    D_TH = 9
    V_MAX = 1 << D_TH
    dp = [[0] * (L_MAX + 1) for _ in range(V_MAX + 1)]

    for i, (val, w) in enumerate(items[:V_MAX]):
        for j in range(L_MAX + 1):
            i1 = i + 1
            i0 = (i + 1) // 2
            if j < w:
                dp[i1][j] = dp[i0][j]
            else:
                dp[i1][j] = max(dp[i0][j], dp[i0][j - w] + val)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v + 1 <= V_MAX:
            ans = dp[v + 1][l]
        else:
            items_sub = [items[v]]
            while v > V_MAX:
                v = (v - 1) // 2
                items_sub.append(items[v])

            ans = 0
            for bit in range(1 << len(items_sub)):
                s_val = s_w = 0
                for i, (val, w) in enumerate(items_sub):
                    if (bit >> i) & 1:
                        s_val += val
                        s_w += w
                if s_w <= l:
                    ans = max(ans, dp[V_MAX][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    # items = []
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            # for j in range(w):
            #     dp[i1][j] = dp[i0][j]
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            # items.append((val, w))
            items_v.append(val)
            items_w.append(w)

    # items = tuple(items)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                # vv.append(items[v - V_MAX][0])
                # ww.append(items[v - V_MAX][1])
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            # m = len(vv)
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


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

import math

def process(number_list):
    left, point = number_list[0], number_list[-2]
    if left == 1:
        print(1)
        return 0
    yojo = number_list[-1] % left
    point -= yojo
    right = left * (math.ceil(point / left) - 1) + yojo
    if right == 0:
        number_list.pop(-1)
        if len(number_list) == 1:
            print(number_list[0])
            return 0
    else:
        number_list[-1] = right
        number_list.sort()
    return number_list

def main():
    num = int(input())
    number_list = list(map(int, input().split()))
    number_list.sort()
    while 1:
        number_list = process(number_list)
        if number_list == 0:
            break


if __name__ == '__main__':
    main()

### FIXED CODE ###

import math

def process(number_list):
    left, point = number_list[0], number_list[-2]
    if left == 1:
        print(1)
        return 0
    right = number_list[-1] % left
    number_list.pop(-1)
    if right == 0:
        if len(number_list) == 1:
            print(number_list[0])
            return 0
    else:
        number_list.insert(0, right)
    return number_list

def main():
    num = int(input())
    number_list = list(map(int, input().split()))
    number_list.sort()
    while 1:
        number_list = process(number_list)
        if number_list == 0:
            break


if __name__ == '__main__':
    main()