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

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
 
MOD = 998244353
MAX_N = 10**7 
 
fac = [1] + [0] * MAX_N
fac_inv = [1] + [0] * MAX_N
mod_pow2_n = [1] + [0] * MAX_N
for i in range(1, MAX_N+1):
    fac[i] = fac[i-1] * i % MOD
    mod_pow2_n[i] = mod_pow2_n[i-1] * 2 % MOD
 
fac_inv[MAX_N] = pow(fac[MAX_N], MOD-2, MOD)
for i in range(MAX_N, 1, -1):
    fac_inv[i-1] = fac_inv[i] * i % MOD
 
def mod_nCr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD 
    
n = int(input())
ans = 0
for i in range(n//2+1, n+1):
    ans += mod_nCr(n, i) * mod_pow2_n[n-i]
    ans %= MOD
print((pow(3, n, MOD) - ans * 2 + MOD)%MOD)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

MOD = 998244353
MAX_N = 10**7 

fac = [1] + [0] * MAX_N
fac_inv = [1] + [0] * MAX_N
mod_pow2_n = [1] + [0] * MAX_N
for i in range(1, MAX_N+1):
    fac[i] = fac[i-1] * i % MOD
    mod_pow2_n[i] = mod_pow2_n[i-1] * 2 % MOD

fac_inv[MAX_N] = pow(fac[MAX_N], MOD-2, MOD)
for i in range(MAX_N, 1, -1):
    fac_inv[i-1] = fac_inv[i] * i % MOD

def mod_nCr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD 
    
n = int(input())
ans = 0
for i in range(n//2+1, n+1):
    ans += mod_nCr(n, i) * mod_pow2_n[n-i]
    ans %= MOD
print((pow(3, n, MOD) - ans * 2 + MOD)%MOD)
### BUGGY CODE ###

#bit全探索する
INF =  5000

N, Ma, Mb = map(int, input().split())
a, b, c = [], [], []
for _ in range(N):
    Lst = [int(x) for x in input().split()]
    a.append(Lst[0])
    b.append(Lst[1])
    c.append(Lst[2])

cost = INF
for n in range(1,2**N):
    A, B, C = 0, 0, 0
    for i in range(N):
        if n & (1<<i):
            A += a[i]
            B += b[i]
            C += c[i]
    if A * Mb == B * Ma:
        cost = min(cost, C)
if cost != INF:
    print(cost)
else:
    print(-1)

### FIXED CODE ###

import collections
import copy
INF = 10000

#入力
N, Ma, Mb = map(int, input().split())
medichine = [tuple(map(int, input().split())) for _ in range(N)]

dp = {}
#dp初期化
dp = collections.defaultdict(lambda:INF)
dp[0,0] = 0

for a, b, c in medichine:
    dp_ = copy.copy(dp)
    for ca,cb in dp.keys():
        dp_[ca+a, cb+b] = min(dp_[ca+a, cb+b], dp[ca,cb]+c)
    dp = dp_    

ans = INF
for ca,cb in dp.keys():
    if ca == cb == 0: continue
    if ca*Mb == cb*Ma:
        ans = min(ans, dp[ca,cb])
        
print(-1 if ans == INF else ans)
### BUGGY CODE ###

s = list(input())

ans = [1] * len(s)

cnt = 0

while cnt < 100000:
    temp = ans.copy()
    for i in range(len(s)):
        if s[i] == "R" and temp[i] > 0:
            ans[i] -= temp[i]
            ans[i+1] += temp[i]
        elif s[i] == "L" and temp[i] > 0:
            ans[i] -= temp[i]
            ans[i-1] += temp[i]
    cnt += 1
    if temp == ans:
        print(*ans)
        exit()

print(*ans)



### FIXED CODE ###

s = list(input())

ans = [0] * len(s)

cnt = 0
r_temp = 0
l_temp = 0
temp = "R"

for i in range(len(s)):
    if temp != s[i] and temp == "R":
        r_temp = cnt
        cnt = 0
        temp = "L"
    if temp != s[i] and temp == "L":
        l_temp = cnt
        cnt = 0
        temp = "R"
        
        if (r_temp-l_temp)%2 == 0:
            ans[i-l_temp] = (r_temp+l_temp)//2
            ans[i-l_temp-1] = (r_temp+l_temp)//2
        elif r_temp > l_temp:
            if r_temp%2 == 0:
                ans[i-l_temp] = ((r_temp+l_temp-1)//2)+1
                ans[i-l_temp-1] = (r_temp+l_temp-1)//2
            else:
                ans[i-l_temp] = (r_temp+l_temp-1)//2
                ans[i-l_temp-1] = ((r_temp+l_temp-1)//2)+1
        elif r_temp < l_temp:
            if l_temp%2 == 0:
                ans[i-l_temp] = (r_temp+l_temp-1)//2
                ans[i-l_temp-1] = ((r_temp+l_temp-1)//2)+1
            else:
                ans[i-l_temp] = ((r_temp+l_temp-1)//2)+1
                ans[i-l_temp-1] = (r_temp+l_temp-1)//2
            
    if i == len(s)-1:
        l_temp = cnt + 1
        #print(r_temp)
        #print(cnt)
        if (r_temp-l_temp)%2 == 0:
            ans[i-l_temp+1] = (r_temp+l_temp)//2
            ans[i-l_temp] = (r_temp+l_temp)//2
        elif r_temp > l_temp:
            if r_temp%2 == 0:
                ans[i-l_temp+1] = ((r_temp+l_temp-1)//2)+1
                ans[i-l_temp] = (r_temp+l_temp-1)//2
            else:
                ans[i-l_temp+1] = (r_temp+l_temp-1)//2
                ans[i-l_temp] = ((r_temp+l_temp-1)//2)+1
        elif r_temp < l_temp:
            if l_temp%2 == 0:
                ans[i-l_temp+1] = (r_temp+l_temp-1)//2
                ans[i-l_temp] = ((r_temp+l_temp-1)//2)+1
            else:
                ans[i-l_temp+1] = ((r_temp+l_temp-1)//2)+1
                ans[i-l_temp] = (r_temp+l_temp-1)//2
        
    cnt += 1
        
        

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

sentence = input()
def recABC(s, c):
  temp = 0
  for i in range(0, len(s) - 2):
    if s[i] == "A":
      if s[i + 1] == "B":
        if s[i + 2] == "C":
            temp += 1
            if len(s) <= i + 3:
              s = s[: i] + "BCA"
            else:
              s = s[: i] + "BCA" + s[i + 3:]
            #print(s)
  
  if temp == 0:
    return c
  else:
    return recABC(s, c + temp)
print(recABC(sentence, 0))

### FIXED CODE ###

sentence = input()
slist = sentence.split("BC")
res = 0
a = 0
for l in slist:
  if ("B" in l) or ("C" in l) :
    l = l.replace("C", "B")
    al = l.split("B")
    a = len(al[-1])
    res += a
  else:
    a += len(l)
    res += a
else:
  res -= a
print(res)
### BUGGY CODE ###

N = int(input())
S = input()

total = 0
for i in range(N):
    for j in range(i,N):
        for k in range(j,N):
            if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
                if j - i != k - j:
                    total += 1

print(total)


### FIXED CODE ###

N = int(input())
S = input()

r = 0
g = 0
b = 0

for i in range(N):
    if S[i] == 'R':
        r += 1
    if S[i] == 'G':
        g += 1
    if S[i] == 'B':
        b += 1

rgb_tot = r*g*b
#print(rgb_tot)

for i in range(N):
    first = S[i]
    for j in range(i,N):
        if 2*j - i < N:
            if first != S[j] and first != S[2*j-i] and S[j] != S[2*j-i]:
                #print("%d %d %d" % (i,j,2*j-i))
                #print(rgb_tot)
                rgb_tot -= 1

print(rgb_tot)
### BUGGY CODE ###

H,W,M=map(int, input().split())
sumh=[0]*H
sumw=[0]*W
bomb=[]
for i in range(M):
  h,w=map(int, input().split())
  sumh[h-1]+=1
  sumw[w-1]+=1
  bomb.append((h,w))
 
qh=[]
qw=[]
maxh=max(sumh)
maxw=max(sumw)
qh=[i for i,x in enumerate(sumh) if x==maxh]
qw=[i for i,x in enumerate(sumw) if x==maxw]

cnt=0
for h,w in bomb:
  if (h-1) in qh and (w-1) in qw:
    cnt+=1
if cnt==len(qh)*len(qw):
  print(maxh+maxw-1)
else:
  print(maxh+maxw)

### FIXED CODE ###

H,W,M=map(int, input().split())
sumh=[0]*H
sumw=[0]*W
bomb=[]
for i in range(M):
  h,w=map(int, input().split())
  sumh[h-1]+=1
  sumw[w-1]+=1
  bomb.append((h,w))

maxh=max(sumh)
maxw=max(sumw)
ch=sumh.count(maxh)
cw=sumw.count(maxw)

cnt=0
for h,w in bomb:
  if sumh[h-1]==maxh and sumw[w-1]==maxw:
    cnt+=1

if cnt==ch*cw:
  print(maxh+maxw-1)
else:
  print(maxh+maxw)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
d = N // 2
ans = []
def linking_up():
    for i in range(N):
        if i % 2 == 0 and i != 0:
            if A.count(i) == 2 and A.count(0) == 1:
                ans.append('c')
        else:
            if A.count(i) == 2:
                ans.append('a')
linking_up()
if ans.count('a') == d or ans.count('c')== d:
    a = (2 ** d) % (10 ** 9 + 7)
    print(a)
else:
    print(0)
        




### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
mod=10**9+7
if n%2==0:
  for i in range(n):
    if a[i]!=(i//2)*2+1:
      print(0)
      exit()
  print(pow(2,n//2,mod))
else:
  for i in range(n):
    if a[i]!=((i+1)//2)*2:
      print(0)
      exit()
  print(pow(2,n//2,mod))
### BUGGY CODE ###

from fractions import gcd
import sys
input = sys.stdin.readline

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

g=A[0]
l=A[0]
for i in range(N):
    g=gcd(l,A[i])
    l=l*A[i]//g
    
ans=0
mod=10**9+7

for i in range(N):
    ans+=l//A[i]
    
print(ans%mod)

### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline

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


for i in range(N):
    a=A[i]
    for j in range(2,a):
        temp=0
        while a%j==0:
            a=a//j
            temp+=1
        lcm[j]=max(lcm[j],temp)
        if a==1 or j*j>A[i]:
            break
    if a!=1:
        lcm[a]=max(lcm[a],1)
                
        
l=1
for d in lcm.items():
    l*=pow(d[0],d[1])
    

ans=0
mod=10**9+7

for i in range(N):
    ans+=l//A[i]
    
print(ans%mod)
### BUGGY CODE ###

import math

s=list(input().split('T'))
sn=[]

for i in range(len(s)):
    sn.append(len(s[i]))

x, y = map(int,input().split(' '))
x = x-sn[0]

snx=[]
sny=[]

for i in range(2,len(sn),2):
    snx.append(sn[i])

for i in range(1,len(sn),2):
    sny.append(sn[i])

#X軸判定
xflg = 0
ansx=[[0]]
for i in range(len(snx)):
    tmpx=[]
    for j in range(len(ansx[i])):
        tmpx.append(ansx[i][j]+snx[i])
        tmpx.append(ansx[i][j]-snx[i])
    ansx.append(tmpx)

if x in ansx[len(snx)]:
    xflg = 1


#y軸判定
yflg = 0
ansy=[[0]]
for i in range(len(sny)):
    tmpy=[]
    for j in range(len(ansy[i])):
        tmpy.append(ansy[i][j]+sny[i])
        tmpy.append(ansy[i][j]-sny[i])
    ansy.append(tmpy)

if y in ansy[len(sny)]:
    yflg = 1

if xflg == 1 and yflg == 1:
    print("Yes")
else:
    print("No")
    


### FIXED CODE ###

import math

s=list(input().split('T'))
sn=[]

for i in range(len(s)):
    sn.append(len(s[i]))

x, y = map(int,input().split(' '))
x = x-sn[0]

snx=[]
sny=[]

for i in range(2,len(sn),2):
    snx.append(sn[i])

for i in range(1,len(sn),2):
    sny.append(sn[i])

#X軸判定
xflg = 0
ansx=[]
prex=[0]
tmpx=[0]
for i in range(len(snx)):
    tmpx=set()
    for j in prex:
        tmpx.add(j+snx[i])
        tmpx.add(j-snx[i])
    prex=tmpx

if x in tmpx:
    xflg = 1

#y軸判定
yflg = 0
prey=[0]
tmpy=[0]
for i in range(len(sny)):
    tmpy=set()
    for j in prey:
        tmpy.add(j+sny[i])
        tmpy.add(j-sny[i])
    prey=tmpy

if y in tmpy:
    yflg = 1

if xflg == 1 and yflg == 1:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

N = int(input())
A=list(map(int,input().split()))
L=[0]*65

for i in range(N):
    t=str(format(A[i],"b"))
    for j in range(len(t)):
        L[j]+=int(t[-j-1])

for i in range(len(L)):
    L[i]=L[i]*(N-L[i])
    L[i]%=(10**9+7)
    L[i]*=2**i
    L[i]%=(10**9+7)
print(sum(L)%(10**9+7))




### FIXED CODE ###

N = int(input())
A=list(map(int,input().split()))
L=[0]*65
MOD=(10**9+7)
for i in range(N):
    t=str(format(A[i],"b"))
    for j in range(len(t)):
        L[j]+=int(t[-j-1])

for i in range(len(L)):
    L[i]=L[i]*(N-L[i])
    L[i]*=2**i
    L[i]%=MOD
print(sum(L)%MOD)
### BUGGY CODE ###

S = [int(x) for x in list(input())]
times = 0

for i in range(len(S) - 1):
    if (S[0] == 0 and S[1] == 0):
        S[1] = 1
        S = S[1:]
        times += 1
    elif (S[0] == 1 and S[1] == 1):
        S[1] = 0
        S = S[1:]
        times += 1
    else:
        S = S[1:]
        
print(times)


### FIXED CODE ###

S = [int(x) for x in list(input())]

min_0 = 0
min_1 = 0

for i in range(len(S)):
    if i % 2 ==0:
        if not (S[i] == 0):
            min_0 += 1
        elif not (S[i] == 1):
            min_1 += 1
    if i % 2 ==1:
        if not (S[i] == 1):
            min_0 += 1
        elif not (S[i] == 0):
            min_1 += 1
                
times = min([min_0, min_1])
print(times)
### BUGGY CODE ###

from math import log, ceil
N = int(input())
A = list(map(int, input().split()))

#print(ceil(log(max(A)+1,2)))
keta = ceil(log(max(A)+1,2))

X = [0] * keta

for a in A:
  work = a
  i = 0
  while work > 0:
    X[i] += work % 2
    i += 1
    work = work // 2

ans = 0
mod = int(1e9+7)
for i in range(len(X)):
  ans += X[i] * (N-X[i]) * 2**i
  ans = ans % mod
  
print(ans)

### FIXED CODE ###

from math import log, ceil
N = int(input())
A = list(map(int, input().split()))

#print(ceil(log(max(A)+1,2)))
keta = ceil(log(max(A)+1,2))

X = [0] * keta

for a in A:
  work = a
  i = 0
  while work > 0:
    X[i] += work % 2
    i += 1
    work = work // 2

ans = 0
mod = int(1e9+7)
for i in range(len(X)):
  ans += X[i] * (N-X[i]) * 2**i
  ans = ans % mod
  
print(ans)
### BUGGY CODE ###

#AGC033-A Darker and Darker
"""
マンハッタン距離で最も白マスと黒マスの遠いところが答え
"""
import sys
from collections import deque
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

#迷路plane
H,W = map(int,readline().split())
maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]

def dfs(i,j):
    deq = deque([[i,j,1]])
    visited = [[False]*W for _ in range(H)]
    while deq:
        h,w,now = deq.popleft()
        visited[h][w] = True
        for a,b in [(0,1),(1,0),(0,-1),(-1,0)]:
            if not (0 <= h+a < H and 0 <= w+b < W):continue
            if visited[h+a][w+b]:continue
            if maze[h+a][w+b] == "#":return now
            else:deq.append([h+a,w+b,now+1])

ans = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == ".":
            ans = max(ans,dfs(i,j))

print(ans)

### FIXED CODE ###

#AGC033-A Darker and Darker
"""
愚直にbfs(queueが無くなるまで)
"""
import sys
from collections import deque
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

#迷路plane
H,W = map(int,readline().split())
maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]

def bfs(lst):
    deq = deque(lst)
    ans = 0
    while deq:
        h,w,now = deq.popleft()
        for a,b in [(0,1),(1,0),(0,-1),(-1,0)]:
            if not (0 <= h+a < H and 0 <= w+b < W):continue
            if maze[h+a][w+b]=="#":continue
            else:
                maze[h+a][w+b] = "#"
                ans = max(ans,now+1)
                deq.append([h+a,w+b,now+1])
    return ans

lst1 = []
for i in range(H):
    for j in range(W):
        if maze[i][j] == "#":
            lst1.append([i,j,0])

print(bfs(lst1))
### BUGGY CODE ###

k = int(input())
n = len(input())

MOD = 10**9 + 7

fact = [1] * 2200000
invfact = [1] * 2200000

for i in range(1, 2200000):
  fact[i] = fact[i-1] * i % MOD

invfact[-1] = pow(fact[-1], MOD-2, MOD)

for i in range(2200000-1, 0, -1):
  invfact[i-1] = invfact[i] * i % MOD

def nCk(n, k):
  return fact[n] * invfact[k] * invfact[n-k] % MOD

ans = 0

for l in range(n, n+k+1):
  ans += pow(25, l-n, MOD) * nCk(l-1,n-1) * pow(26, n+k-l, MOD) % MOD
  ans %= MOD

print(ans)


### FIXED CODE ###

k = int(input())
n = len(input())

MOD = 10**9 + 7

fact = [1] * 2200000
invfact = [1] * 2200000

for i in range(1, 2200000):
  fact[i] = fact[i-1] * i % MOD

invfact[-1] = pow(fact[-1], MOD-2, MOD)

for i in range(2200000-1, 0, -1):
  invfact[i-1] = invfact[i] * i % MOD

def nCk(n, k):
  return fact[n] * invfact[k] * invfact[n-k] % MOD

ans = 0

for l in range(n, n+k+1):
  ans += pow(25, l-n, MOD) * nCk(l-1,n-1) * pow(26, n+k-l, MOD) % MOD
  ans %= MOD

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

import numpy as np

R, G ,B, N = map(int, input().split())

tmp = [R, G, B]
tmp.sort()
R, G, B = tmp[2], tmp[1], tmp[0]


num_R = N // R + 1
num_G = N // G
RG = np.zeros((num_R, num_G+1))

RG[:, 0] = [N - R*i for i in range(num_R)]

for j in range(num_G):
    RG[:, j+1] = RG[:, j] - G

check = lambda x: 0 if x < 0 else 1 if x == 0 else 1 if x%B == 0 else 0

a = []
count = 0
for i in range(len(RG)):
    a = list(map(check, RG[i]))
    count += sum(a)

print(count)


### FIXED CODE ###

R, G, B, N = map(int, input().split())

count = 0
for i in range(N // R + 1):
    n = N - R * i
    for j in range(n // G + 1):
        if (n - G*j) >= 0 and (n - G*j) % B == 0:
            count += 1

print(count)
### BUGGY CODE ###

h=int(input())
a=[]
while h>=1:
    a.append(h)
    h//2
count=0
for i in a:
    while a[i]>=1:
        count+=1
        a[i]//2
print(count)

### FIXED CODE ###

n=int(input())
a=0
b=0
while n!=0:
    n=n//2
    a+=2**b
    b+=1
print(a)
### BUGGY CODE ###

n = int(input())
power = 1

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

power = power%(1000000000+7)

print(power)

### FIXED CODE ###

n = int(input())
power = 1

for i in range(1, n+1):
    power = power*i%(1000000000+7)



print(power)
### BUGGY CODE ###

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

AB.sort()
B = [[] for _ in range(100005)]
tmp = 0
for ab in AB:
  if ab[0] != tmp:
    B[ab[0]] = B[tmp].copy()
  B[ab[0]].append(ab[1])
  tmp = ab[0]

for i in range(1, M + 1):
  if len(B[i]) == 0:
    B[i] = B[i - 1].copy()

ans = 0
for i in range(1, M + 1):
  if len(B[i]) > 0:
    m = max(B[i])
    ans += m
    for j in range(i, M + 1):
      if len(B[j]) > 0:
        B[j].remove(m)

print(ans)

### FIXED CODE ###

from heapq import heappush, heappop

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

for i in range(N):
  ab = list(map(int, input().split()))
  #Ai > M の仕事はいらない
  if ab[0] <= M:
    jobs[ab[0] - 1].append(ab[1])

#最終日はAi=1の仕事のみ選べる。その前の日はAi<=2, ...
#終わりから考えればよさそう
hq = []
ans = 0
for i in range(M):
  for b in jobs[i]:
    heappush(hq, -1 * b)
  if len(hq) > 0:
    m = -1 * heappop(hq)
    ans += m

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

n = int(input())
A = list(map(int, input().split()))
SUM = sum(A)
MIN = min(A)
start = A.index(MIN)

for odd in range(0, 10**9+1, 2):
    dp = [0]*n
    dp[start] = cnt = odd
    for i in range(start+1, n):
        dp[i] = 2*A[i-1]-dp[i-1]
        cnt += dp[i]
    else:
        for i in range(start):
            dp[i] = 2*A[i-1]-dp[i-1]
            cnt += dp[i]
    if cnt == SUM:
        break
print(*dp)


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
SUM = sum(A)
MIN = min(A)
start = A.index(MIN)

dp = [0]*n
dp[start] = cnt = 0
for i in range(start+1, n):
    dp[i] = 2*A[i-1]-dp[i-1]
    cnt += dp[i]
else:
    for i in range(start):
        dp[i] = 2*A[i-1]-dp[i-1]
        cnt += dp[i]

odd = SUM-cnt
dp = [0]*n
dp[start] = cnt = odd
for i in range(start+1, n):
    dp[i] = 2*A[i-1]-dp[i-1]
    cnt += dp[i]
else:
    for i in range(start):
        dp[i] = 2*A[i-1]-dp[i-1]
        cnt += dp[i]

print(*dp)
### BUGGY CODE ###

from itertools import combinations

def canProd(a,x):
    for i in range(1,len(a)+1):
        comba = combinations(a,i)
        for j in comba:
            if sum(j) == x:
                return True
    return False


n = int(input())
a = [int(x) for x in input().split()]
q = int(input())
m = [int(x) for x in input().split()]

for i in m:
    if canProd(a,i):
        print("yes")
    else:
        print("no")

### FIXED CODE ###

from functools import lru_cache

@lru_cache(maxsize = None)
def canProd(i,m):
     
    if m == 0:
        return True
    if i >= n:
        return False
 
    res = canProd(i+1,m) or canProd(i+1,m-a[i])
    return res
 
 
n = int(input())
a = [int(x) for x in input().split()]
q = int(input())
m = [int(x) for x in input().split()]

rs = [None]*2001

maxm = max(m)
minm = min(m)

for i in range(minm,maxm+1):
    if canProd(0,i):
        rs[i] = "yes"
    else:
        rs[i] = "no"

for i in m:
    print(rs[i])
### BUGGY CODE ###

def combi(n, r) :
    ret = 1
    for i in range(n, n-r, -1) :
        ret *= i
        while r > 1 and ret % r == 0 :
            ret //= r
            r -= 1

    return ret

MOD = 10 ** 9 + 7
N, M, K = map(int, input().split(' '))

n, r = N * M - 2, K - 2
P = combi(n, r) % MOD

ans = 0
for n in range(N) :
    for m in range(M) :
        if n == 0 and m == 0 :
            continue

        d = n + m
        cnt = (N - n) * (M - m) * (1 if n == 0 or m == 0 else 2)

        ans += d * cnt * P
        ans %= MOD

print(ans)


### FIXED CODE ###

from math import factorial

MOD = 10 ** 9 + 7
N, M, K = map(int, input().split(' '))

n, r = N * M - 2, K - 2
#P = factorial(n) // factorial(n-r) // factorial(r) % MOD
P = factorial(n) * pow(factorial(n-r) % MOD, MOD - 2, MOD) * pow(factorial(r) % MOD, MOD - 2, MOD)

ans = 0
for n in range(N) :
    for m in range(M) :
        if n == 0 and m == 0 :
            continue

        d = n + m
        cnt = (N - n) * (M - m) * (1 if n == 0 or m == 0 else 2)

        ans += d * cnt

ans = (ans * P) % MOD
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


n = int(input().rstrip())
a = [a for a in input().rstrip().split()]

b = []
for i in range(n):
    if i % 2 == 0: b += [a[i]]
    else: b = [a[i]] + b
if (n - 1) % 2 == 0: b = list(reversed(b))

for elem in b: print(elem, end=' ')

### FIXED CODE ###

import sys
input = sys.stdin.readline


n = int(input().rstrip())
a = [a for a in input().split()]

b = [None] * n
for i in range(n):
    if i % 2 == 0: b[n // 2 + i // 2] = a[i]
    else: b[n // 2 - (-(-i // 2))] = a[i]
if (n - 1) % 2 == 0: b = list(reversed(b))

for elem in b: print(elem, end=' ')
### BUGGY CODE ###

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


c = 0
a = 0

t = [0]*(n+1)

temp = []


for i in range(m):
    s = input().split()
    x = s[0]
    y = s[1]
    if y == 'AC' and x not in set(temp):
        a += 1
        c += t[int(x)]
        temp += [x]
    elif y == 'WA':
        t[int(x)] += 1

print(a, c)


### FIXED CODE ###

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

a = [0] * (n+1)
b = [0] * (n+1)

c = 0

for i in [0]*(m):

    s = input().split()

    if a[int(s[0])] == 0:
        if s[1] == "AC":
            a[int(s[0])] = 1
            c += b[int(s[0])]
        else:
            b[int(s[0])] += 1

print(sum(a), c)
### BUGGY CODE ###

N=int(input())
S=list(input())

i=0
N1=N #配列長さ
while i<=N1-2:
    if S[i]==S[i+1]:
        for k in range(i+2,N):
            S[k-1]=S[k]
        N1=N1-1
    else:
        i=i+1
print(N1)

### FIXED CODE ###

N=int(input())
S=list(input())

a=0#色変化
for i in range(N-1):
    if not S[i]==S[i+1]:
        a=a+1
print(a+1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, K=map(int,input().strip().split(' '))
xl=[]
yl=[]
for i in range(N):
    xt,yt=map(int,input().strip().split(' '))
    xl.append(xt)
    yl.append(yt)
ans=10**20
x=sorted(xl)
y=sorted(yl)
for i in range(N):
    for j in range(i+1,N):
        xmin=x[i]
        xmax=x[j]
        for k in range(N):
            for l in range(k+1,N):
                ymin=y[k]
                ymax=y[l]
                A=(xmax-xmin)*(ymax-ymin)
                ct=0
                for m in range(N):
                    if xmin<=xl[m] and xl[m]<=xmax and ymin<=yl[m] and yl[m]<=ymax:
                        ct+=1
                if ct==K:
                    ans=min(ans,A)
                    break
print(ans)



### FIXED CODE ###

import sys
input = sys.stdin.readline

N, K=map(int,input().strip().split(' '))
x=[]
y=[]
point=[]
for i in range(N):
    xt,yt=map(int,input().strip().split(' '))
    x.append(xt)
    y.append(yt)
    point.append([xt,yt])
ans=10**20
x.sort()
y.sort()
point.sort(key=lambda x:x[1])


for i in range(N):
    for j in range(i+1,N):
        xmin=x[i]
        xmax=x[j]
        for k in range(N):
            ymin=y[k]
#            ymax=y[l]
#            
            ct=0
            for p in point:
                if xmin<=p[0] and p[0]<=xmax and ymin<=p[1]:
                    ct+=1
                if ct==K:
                    A=(xmax-xmin)*(p[1]-ymin)
                    ans=min(ans,A)
                    break
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n, k = map(int, input().split())
s = input()
rr = (list(map(int, input().split())) for _ in range(k))

from collections import Counter

for a, b in rr:
  c = Counter(s[a-1:b].replace('AC', '1'))['1']
  print(c)


### FIXED CODE ###

import sys
input = sys.stdin.readline
n, k = map(int, input().split())
s = input()
rr = (list(map(int, input().split())) for _ in range(k))

from collections import Counter

dc = [0, 0]
c = 0
for i in range(1, len(s)):
  if s[i-1]+s[i] == 'AC':
    c += 1
  dc.append(c)
for a, b in rr:
  print(dc[b] - dc[a])