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

import sys
input = sys.stdin.readline


class BIT:
    def __init__(self, a):
        self.n = len(a)
        self.a = [0] * (self.n + 1)

        for i, j in enumerate(a):
            self.update(i, j)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            self.a[i] = self.a[i] + x
            i += i & (-i)

    def get(self, i):
        s = 0
        i += 1
        while i != 0:
            s = s + self.a[i]
            i -= i & (-i)
        return s


def inmin(x):
    return int(x)-1


if __name__ == "__main__":
    n, q = map(int, input().split())
    c = list(map(inmin, input().split()))
    que = [[i, list(map(inmin, input().split())), 0] for i in range(q)]
    que.sort(key=lambda x: x[1][1])

    last = [-1] * n
    bit = BIT([0]*(n+10))
    j = 0
    for i in range(n):
        if last[c[i]] >= 0:
            bit.update(last[c[i]]+5, -1)
        bit.update(i+5, 1)
        last[c[i]] = i
        while j < q and que[j][1][1] == i:
            que[j][2] = bit.get(i+5) - bit.get(que[j][1][0]+4)
            j += 1
    que.sort()
    for i in que:
        print(i[-1])


### FIXED CODE ###

import sys
input = sys.stdin.readline


class BIT:
    def __init__(self, a):
        self.n = len(a)
        self.a = [0] * (self.n + 1)

        for i, j in enumerate(a):
            self.update(i, j)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            self.a[i] = self.a[i] + x
            i += i & (-i)

    def get(self, i):
        s = 0
        i += 1
        while i != 0:
            s = s + self.a[i]
            i -= i & (-i)
        return s


def inmin(x):
    return int(x)-1


if __name__ == "__main__":
    n, q = map(int, input().split())
    c = list(map(inmin, input().split()))
    que = [[i, list(map(inmin, input().split()))] for i in range(q)]
    que.sort(key=lambda x: x[1][1])
    ans = [0] * q

    last = [-1] * n
    bit = BIT([0]*(n+10))
    j = 0
    for i in range(n):
        if last[c[i]] >= 0:
            bit.update(last[c[i]]+5, -1)
        bit.update(i+5, 1)
        last[c[i]] = i
        while j < q and que[j][1][1] == i:
            ans[que[j][0]] = bit.get(i+5) - bit.get(que[j][1][0]+4)
            j += 1
    print(*ans)
### BUGGY CODE ###

n = int(input())
if n == 1:print(0);exit()
sum = 0
for i in range(0,n-1):
  sum += i+1
print(sum)

### FIXED CODE ###

n = int(input())
print((1+n-1)*(n-1)//2)
### BUGGY CODE ###

import fractions

  
def isprime(x):
    count = 1
    for i in range(2,int(x**0.5)+1):
        if x % i == 0:
            count += 1
      
    return count

a,b = map(int,input().split())
g = fractions.gcd(a,b)



ans=0
for i in range(1,int(g**0.5)+1):
    if g % i == 0:
        if isprime(i) == 1:
            ans += 1
        if i != g//i:
            if isprime(g//i) == 1:
                ans += 1
       

print(ans)
  

  

  

  

  


### FIXED CODE ###

def gcd(x, y):
    a, b = x, y
    r = a % b
    while r != 0:
        a, b = b, r
        r = a % b
    return b

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

def isprime(x):
    t = 1
    for i in range(2, int(x**0.5) + 1):
        if x % i == 0:
            t = 0
            break
    if t == 1 and x != 1:
        return True
    else:
        return False


a, b = map(int, input().split())

CD = divisors(gcd(a, b))

ans = 1
for cd in CD:
    if isprime(cd):
        ans += 1

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

#!/usr/bin/env python3.4

# abc127_d

import collections
import itertools
import functools

def find_index(iterable, func, from_i):
    i = from_i
    l = len(iterable)
    while i<l and not func(iterable[i]):
        i += 1
    return i

def insert(deq, i, x):
    deq.rotate(-i)
    deq.appendleft(x)
    deq.rotate(i)

def main():
    # Input
    _, m = [int(s) for s in input().split()]
    cards = [int(s) for s in input().split()]
    acts = [[int(s) for s in input().split()] for _ in range(m)]
    # Get ans
    cards = collections.deque(sorted(cards))
    acts.sort(key=lambda a: a[1])
    i = 0
    for b, c in acts:
        i = find_index(cards, lambda card: card>=c, i)
        #print(i, cards[:i], cards[i:])
        change_num = min(b, i)
        #cards = cards[:i][change_num:] + [c]*change_num + cards[i:]
        for _ in range(change_num):
            insert(cards, i, c)
            cards.popleft()
        #print(cards)
    ans = sum(cards)
    # Output
    print(ans)

if __name__ == '__main__':
    main()



### FIXED CODE ###

#!/usr/bin/env python3.4

# abc127_d

import collections
import itertools
import functools

def main():
    # Input
    _, m = [int(s) for s in input().split()]
    cards = [int(s) for s in input().split()]
    acts = [[int(s) for s in input().split()] for _ in range(m)]
    # Get ans
    cards = collections.deque(sorted(cards))
    acts.sort(key=lambda a: a[1], reverse=True)
    for b, c in acts:
        for _ in range(b):
            if cards[0] >= c:
                break
            cards.popleft()
            cards.append(c)
    ans = sum(cards)
    # Output
    print(ans)

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

n, a, b = map(int,input().split())
mod7 = 10 ** 9 + 7
def power(a,b,mod):
    p = 1
    q = a
    while b != 0:
        if b % 2 == 1:
            p = (p * q) % mod
        q = (q * q) % mod
        b = b // 2
    return p

def fact(n, mod):
    p = 1
    for i in range(1,n+1):
        p = (p * i) % mod
    return p

def divi(a,b,mod):
    p = (power(b, mod-2, mod) * a) % mod
    return p

def combi(n,a,mod):
    nf = fact(n,mod)
    af = fact(a,mod)
    bf = fact(n-a,mod)
    return divi(divi(nf,af,mod),bf,mod)

Answer = power(2, n, mod7) - combi(n, a, mod7) - combi(n, b , mod7) - 1
print(Answer)

### FIXED CODE ###

n, a, b = map(int,input().split())
mod7 = 10 ** 9 + 7
def power(a,b,mod):
    p = 1
    q = a
    while b != 0:
        if b % 2 == 1:
            p = (p * q) % mod
        q = (q * q) % mod
        b = b // 2
    return p

def fact(n, mod):
    p = 1
    for i in range(1,n+1):
        p = (p * i) % mod
    return p


def combi(n,a,mod):
    inv_af = power(fact(a,mod),mod-2,mod)
    p = 1
    for i in range(a):
        p = (p * (n-i)) % mod
    return inv_af * p % mod

Answer = (power(2, n, mod7) - combi(n, a, mod7) - combi(n, b, mod7) - 1) % mod7
print(Answer)
### BUGGY CODE ###

from  collections import deque

S = str(input())
Q = int(input())

#Que = [list(map(str, input().split())) for _ in range(Q)]

deque_S = deque(S)
re_flag = 1
for i in range(Q):
    que = str(input())

    if len(que) == 1:
        #S = S[::-1]
        re_flag *= -1

    else:
        if que[2] == '1':
            if re_flag == 1:
                #S = que[4:] + S
                deque_S.appendleft(que[4:])
            else:
                #S =  S + que[-1:3:-1]
                deque_S.append(que[-1:3:-1])
        if que[2] == '2':
            if re_flag == 1:
                #S = S + que[4:]
                deque_S.append(que[4:])
            else:
                #S = que[-1:3:-1] + S
                deque_S.appendleft(que[-1:3:-1])

ans = ''
for i in range(len(deque_S)):
    ans += deque_S[i]

#print(deque_S)

if re_flag == -1:
    S = S[::-1]
    ans = ans[::-1]
print(ans)

### FIXED CODE ###

from  collections import deque

S = str(input())
Q = int(input())

#Que = [list(map(str, input().split())) for _ in range(Q)]

deque_S = deque(S)
re_flag = 1
for i in range(Q):
    que = str(input())

    if len(que) == 1:
        #S = S[::-1]
        re_flag *= -1

    else:
        if que[2] == '1':
            if re_flag == 1:
                #S = que[4:] + S
                deque_S.appendleft(que[4:])
            else:
                #S =  S + que[-1:3:-1]
                deque_S.append(que[-1:3:-1])
        if que[2] == '2':
            if re_flag == 1:
                #S = S + que[4:]
                deque_S.append(que[4:])
            else:
                #S = que[-1:3:-1] + S
                deque_S.appendleft(que[-1:3:-1])

ans = ''
if re_flag == 1:
    ans = ''.join(deque_S)
else:
    ans = ''.join(deque_S)[::-1]
#print(deque_S)

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

import numpy
N = int(input())
A,B = [],[]
for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)

AA = list(numpy.argsort(A)[::-1])
BB = list(numpy.argsort(B)[::-1])
Al = []
Bl = []
aans,bans = 0,0
for i in range(N):
    a = AA.pop(0)
    aans += A[a]
    Al.append(a)
    BB.remove(a)
    if not BB:
        break
    b = BB.pop(0)
    bans += B[b]
    Bl.append(b)
    AA.remove(b)
    if not AA:
        break

print(aans - bans)


### FIXED CODE ###

import numpy
import collections
N = int(input())
arr = []
for i in range(N):
    a,b = map(int,input().split())
    arr.append([a+b,a,b])

arr = sorted(arr,reverse=True)
ansa,ansb = 0 , 0
for i in range(N):
    if i % 2 == 0:
        ansa += arr[i][1]
    else:
        ansb += arr[i][2]
print(ansa - ansb)
### BUGGY CODE ###

n = int(input())
A = [int(input()) for _ in range(n)]
l = []

for i in range(n):
    for j in range(n):
        if i != j:
            l.append(A[j])
    print(max(l))
    l.clear()
        

### FIXED CODE ###

n = int(input())
A = [int(input()) for _ in range(n)]
B = sorted(A)
B_M = max(B)
B_M_1 = max(B[:n-1])
for i in range(n):
    if A[i] == B_M:
       print(B_M_1)
    else:
        print(B_M)
### BUGGY CODE ###

n,q=[int(i) for i in input().split()]
s=list(input())
for i in range(q):
    c=0
    query = (lambda x: [x[0]-1, x[1]])([int(i) for i in input().split()])
    seq = s[query[0]:query[1]]
    for i in range(query[1]-query[0]-1):
        if seq[i]+seq[i+1] == "AC":
            c += 1
    print(c)


### FIXED CODE ###

N, Q = [int(i) for i in input().split()]
S = input()

cumsum = [0]
for i in range(1, N):
    if (S[i-1], S[i]) == ("A", "C"):
        cumsum.append(cumsum[i-1]+1)
    else:
        cumsum.append(cumsum[i-1])

for i in range(Q):
    l, r = [int(i)-1 for i in input().split()]
    print(cumsum[r]-cumsum[l])
### BUGGY CODE ###

h, w = map(int, input().split())
s = []
s.append("#" * (w + 2))
for i in range(h):
    s.append("#" + input() + "#")
s.append("#" * (w + 2))

num = [[-1 for i in range(w + 2)] for i in range(h + 2)]
for i in range(1, h + 1):
    l = 0
    m = 0
    while l < w + 2:
        if s[i][l] == "#":
            l += 1
            continue
        else:
            m = l
            while s[i][m] == ".":
                m += 1
            else:
                for j in range(l, m):
                    num[i][j] += m - l
                l = m
for i in range(1, w + 1):
    l = 0
    m = 0
    while l < h + 2:
        if s[l][i] == "#":
            l += 1
            continue
        else:
            m = l
            while s[m][i] == ".":
                m += 1
            else:
                for j in range(l, m):
                    num[j][i] += m - l
                l = m
print(max([max([num[i][j] for j in range(w + 2)]) for i in range(h + 2)]))

### FIXED CODE ###

h, w = map(int, input().split())
s = []
s.append(["#"] * (w + 2))
for i in range(h):
    s.append(["#"] + list(input()) + ["#"])
s.append(["#"] * (w + 2))

num = [[-1 for i in range(w + 2)] for i in range(h + 2)]
for i in range(1, h + 1):
    l = 0
    m = 0
    while l < w + 2:
        if s[i][l] == "#":
            l += 1
            continue
        else:
            m = l
            while s[i][m] == ".":
                m += 1
            else:
                for j in range(l, m):
                    num[i][j] += m - l
                l = m
for i in range(1, w + 1):
    l = 0
    m = 0
    while l < h + 2:
        if s[l][i] == "#":
            l += 1
            continue
        else:
            m = l
            while s[m][i] == ".":
                m += 1
            else:
                for j in range(l, m):
                    num[j][i] += m - l
                l = m
print(max([max([num[i][j] for j in range(w + 2)]) for i in range(h + 2)]))
### BUGGY CODE ###

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

sum=0
for i in range(n):
    o = i+1
    while (o<n):
        sum=(a[i]*a[o]+sum)%1000000007
        o=o+1

print(sum)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
mod=1000000007
sum=0
tmp=0
o=0
while(o<n):
    tmp = (a[o]%mod + tmp%mod)%mod
    o += 1

for i in range(n):
    tmp=(tmp%mod-a[i]%mod)%mod
    sum=((a[i]%mod)*tmp)%mod+sum%mod



print(sum%mod)
### BUGGY CODE ###

import math
from functools import reduce

K = int(input())
list_a = []

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            list_a.append(gcd(i, j, k))

print(sum(list_a))


### FIXED CODE ###

import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 6)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")
al = "abcdefghijklmnopqrstuvwxyz"
AL = al.upper()

from math import *

K=k()
ans=0
for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      ans+=gcd(k,gcd(i,j))
print(ans)
### BUGGY CODE ###

def main():
    s = input()
    r = 0
    lens = len(s)
    for i1 in range(lens - 3):
        tint = int(s[i1:])
        while tint >= 2019:
            r += tint % 2019 == 0
            tint = tint //10
    print(r)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import Counter
def main():
    s = input()
    n = len(s)

    amari = [0] * n
    ketaamari = 1
    t = 0
    for i1 in range(n):
        t = (t + ketaamari * int(s[-i1 -1])) % 2019
        amari[-i1-1] = t
        ketaamari = (ketaamari * 10) % 2019
    amari.append(0)
    ac = Counter(amari)
    r = 0
    for v in ac.values():
        r += v * (v - 1) // 2
    print(r)

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

A, B, Q = map(int, input().split())
S = [int(input()) for _ in range(A)]
T = [int(input()) for _ in range(B)]
X = [int(input()) for _ in range(Q)]
INF = 10**12

def binary_search(query, arr):
    arr = [-INF] + arr + [INF]
    low = 0
    high = len(arr)
    while high-low>1:
        mid = (low+high)//2
        if query>arr[mid]:
            low = mid
        else:
            high = mid
    return arr[low], arr[high]

def main():
    for x in X:
        s1, s2 = binary_search(x, S)
        t1, t2 = binary_search(x, T)
        ans = [ abs(t-s)+min(abs(t-x), abs(s-x)) \
            for t in [t1, t2] for s in [s1, s2] ]
        print(min(ans))
    return

main()

### FIXED CODE ###

A, B, Q = map(int, input().split())
INF = 10**12
S = [-INF] + [int(input()) for _ in range(A)] + [INF]
T = [-INF] + [int(input()) for _ in range(B)] + [INF]
X = [int(input()) for _ in range(Q)]


def binary_search(query, arr):
    low = 0
    high = len(arr)
    while high-low>1:
        mid = (low+high)//2
        if query>arr[mid]:
            low = mid
        else:
            high = mid
    return arr[low], arr[high]

def main():
    for x in X:
        s1, s2 = binary_search(x, S)
        t1, t2 = binary_search(x, T)
        ans = [ abs(t-s)+min(abs(t-x), abs(s-x)) \
            for t in [t1, t2] for s in [s1, s2] ]
        print(min(ans))
    return

main()
### BUGGY CODE ###

def chmin(a,b):
    if a > b:
        a = b
    else:
        pass
    return a    
N, K = map(int, input().split())    
H = list(map(int, input().split()))

dp = [float("inf") for _ in range(N)]
dp[0] = 0

for i in range(N-1):
    for j in range(1, min(K+1, N-i)):
        dp[i+j] = chmin(dp[i+j], dp[i]+abs(H[i+j]-H[i]))

print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
*h, = map(int, input().split())
dp = [float("inf") for _ in range(N)]
dp[0] = 0
for i in range(N - 1):
	for j in range(1, min(K + 1, N - i)):
		dp[i + j] = min(dp[i + j], dp[i] + abs(h[i + j] - h[i]))
print(dp[N - 1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

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

def ers(a,cnt):
    if len(a) == 0:
        cnt = -1
        return cnt
    for i in range(len(a)):
        if i+1 != a[i]:
            a.pop(i)
            cnt+=1
            return ers(a,cnt)
    return cnt

res = ers(a,cnt)

print(str(res))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
cnt = 0
for i in range(N):
    if A[i] != i+1-cnt:
        cnt += 1
if cnt == N:
    print(-1)
else:
    print(cnt)
### BUGGY CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
AGC028 C
"""

import itertools
from operator import itemgetter

n = int(input())
abli0 = [tuple(map(int, input().split())) for i in range(n)]
eabli0 = enumerate(abli0)
abli1 = list(map(lambda t: ((t[1][0], t[0], 0), (t[1][1], t[0], 1)), eabli0))
abli = list(itertools.chain.from_iterable(abli1))
abli.sort(key=itemgetter(0))
tmpans0 = sum(map(lambda t: t[0], abli[:n]))
alist = [i for x, i, aorb in abli[:n] if not aorb]
blist = [i for x, i, aorb in abli[:n] if aorb]
flag = bool([i for i in range(n) if i in alist and i in blist])

y, j, arob2 = abli[n]
z, k, arob3 = abli[n+1]
if flag:
    tmpans = tmpans0
else:
    tmpans = 2**62
    for x, i, aorb in abli[:n]:
        if j != i:
            tmp = tmpans0-x+y
        else:
            tmp = tmpans0-x+z
        if tmpans > tmp:
            tmpans = tmp

leftsum = sum(map(lambda x: x[0], abli0))
rightsum = sum(map(lambda x: x[1], abli0))

print(min(leftsum, rightsum, tmpans))


### FIXED CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
AGC028 C
"""

from operator import itemgetter

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

abli.sort(key=itemgetter(0))
tmpans0 = sum(map(itemgetter(0), abli[:n]))
aiset = set([i for x, i, aorb in abli[:n] if not aorb])
biset = set([i for x, i, aorb in abli[:n] if aorb])
flag = bool(set.intersection(aiset, biset))


y, j, arob2 = abli[n]
z, k, arob3 = abli[n+1]

if flag:
    tmpans = tmpans0
else:
    min1 = y-max([x for x, i, aorb in abli[:n] if j != i])
    min2 = z-max([x for x, i, aorb in abli[:n] if j == i])
    tmpans = tmpans0 + min(min1, min2)

leftsum = sum([aa for aa, i, aorb in abli if not aorb])
rightsum = sum([bb for bb, i, aorb in abli if aorb])

print(min(leftsum, rightsum, tmpans))
### BUGGY CODE ###

while 1:
    w = raw_input()
    if w=="0000": break
    if int(w)%1111==0:
        print "NA"
        continue
    ans = 0
    while(w!="6174"):
        w = str(int("".join(sorted(w,reverse=True)))-int("".join(sorted(w))))
        ans += 1
    print ans

### FIXED CODE ###

while 1:
    w = raw_input()
    if w=="0000": break
    if int(w)%1111==0:
        print "NA"
        continue
    ans = 0
    while(w!="6174"):
        w = ("".join(sorted(w))).zfill(4)
        w = str(int(w[::-1])-int(w))
        ans += 1
    print ans
### BUGGY CODE ###

n=int(input())
x = [int(i) for i in input().split()]
x = sorted([[x[i], i] for i in range(n)])
#print(x)
ans = [0]*n
#print(ans)
for i in range(n):
  x_ = x[:i]+x[i+1:]
#  print(x_)
  ans[x[i][1]] = x_[n//2-1][0]
for i in range(n):
  print(ans[i])

### FIXED CODE ###

n=int(input())
x = [int(i) for i in input().split()]
x = sorted([[x[i], i] for i in range(n)])
#print(x)
ans = [0]*n
for i in range(n):
  if i < n//2:
    ans[x[i][1]] = x[n//2][0]
  else:
    ans[x[i][1]] = x[n//2-1][0]
for i in range(n):
  print(ans[i])
### BUGGY CODE ###

n, k = map(int, input().split())
l = list(map(int, input().split()))
set_l = list(set(l))
set_l_len = len(set_l)
count = {}
for i in range(set_l_len):
    count[str(set_l[i])] = l.count(set_l[i])
count_sorted = sorted(count.items(), key=lambda x: x[1])
sum = 0
for i in range(max(0, set_l_len - k)):
    sum += count_sorted[i][1]
print(sum)

### FIXED CODE ###

import collections
n, k = map(int, input().split())
l = list(map(int, input().split()))
S = collections.Counter(l)
S = sorted(S.values())
print(sum(S[:len(S)-k]))
### BUGGY CODE ###

from bisect import bisect_left as bs
N, M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()

while M > 0:
  i = A.pop(-1) // 2
  A.insert(bs(A, i), i)
  M -= 1

print(sum(A))

### FIXED CODE ###

from bisect import bisect_left as bs
#ソート順序を保ったまま値を挿入する
N, M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()

while M > 0:
  i = A.pop(-1) // 2
  A.insert(bs(A, i), i)
  M -= 1

print(sum(A))
### BUGGY CODE ###

X = input()

for _ in range(len(X)//2):
    X = X.replace('ST', '')

print(len(X))


### FIXED CODE ###

X = input()

S_count = 0
T_count = 0
for item in X:
    if item == 'S':
        S_count += 1
    elif item == 'T' and S_count > 0:
        S_count -= 1


print(2 * S_count)
### BUGGY CODE ###

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

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

for i in mi:
    if solve(0, i):
        print("yes")
    else:
        print("no")

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
q = int(input())
mi = map(int, input().split())
t = {}

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

for m in mi:
    if solve(0, m):
        print("yes")
    else:
        print("no")
### BUGGY CODE ###

N = int(input())

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

def leave(a,b,c):
	while a>b:
		b += c
	return b

for j in range(N-1):
	time = 0
	for i in range(j,N-1):
		if time <= X[i][1]:
			time = X[i][0]+X[i][1]
		else:
			time = leave(time,X[i][1],X[i][2])+X[i][0]
	print(time)
print(0)

### FIXED CODE ###

N = int(input())

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


for j in range(N-1):
	time = 0	
	for i in range(j,N-1):
		if time <= X[i][1]:
			time = X[i][0]+X[i][1]
		elif (time-X[i][1])%X[i][2] == 0:
			time += X[i][0]
		else:
			time += X[i][0]+(X[i][2]-(time-X[i][1])%X[i][2])
	print(time)
print(0)
### BUGGY CODE ###

n = int(input())
dist = [list(map(int,input().split())) for i in range(n)]
use = [[True for i in range(n)] for j in range(n)]
ans = 0

for i in range(n):
    for j in range(n):
        for k in range(n):
            if dist[j][k] > dist[j][i] + dist[i][k]:
                print(-1)
                exit()
            elif j != i and j != k and i != k and dist[j][k] == dist[j][i] + dist[i][k]:
                use[j][k] = False

for i in range(n):
    for j in range(n):
        if use[i][j]:
            ans += dist[i][j]

print(ans//2)

### FIXED CODE ###

n = int(input())
dist = [list(map(int,input().split())) for i in range(n)]
use = [[True for i in range(n)] for j in range(n)]
ans = 0

for i in range(n):
    for j in range(n):
        for k in range(n):
            if dist[j][k] > dist[j][i] + dist[i][k]:
                print(-1)
                exit()
            elif j != i and j != k and i != k and dist[j][k] == dist[j][i] + dist[i][k]:
                use[j][k] = False

for i in range(n):
    for j in range(n):
        if use[i][j]:
            ans += dist[i][j]

print(ans//2)