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

import copy
R, C, K = map(int,input().split())
i = [list(map(int,input().split())) for k in range(K)]
dp0 = []
for r in range(R):
   dp0.append([])
   for c in range(C):
      dp0[r].append([])
      dp0[r][c] = 0
location = copy.deepcopy(dp0)
dp1 = copy.deepcopy(dp0)
dp2 = copy.deepcopy(dp0)
dp3 = copy.deepcopy(dp0)
for k in range(K):
   location[i[k][0]-1][i[k][1]-1] = i[k][2]
dp1[0][0] = location[0][0]
if R > 1:
   for r in range(R-1):
      dp1[r+1][0] = location[r+1][0] + dp1[r][0]
      dp0[r+1][0] = dp1[r][0]
if C > 1:
   for c in range(C-1):
      dp0[0][c+1] = dp0[0][c]
      dp1[0][c+1] = max(location[0][c+1] + dp0[0][c], dp1[0][c])
      dp2[0][c+1] = max(location[0][c+1] + dp1[0][c], dp2[0][c])
      dp3[0][c+1] = max(location[0][c+1] + dp2[0][c], dp3[0][c])
   if R > 1:
      for r in range(R-1):
         for c in range(C-1):
            if location[r+1][c+1] > 0:
               dp0[r+1][c+1] = max(dp0[r+1][c], dp0[r][c+1], dp1[r][c+1], dp2[r][c+1], dp3[r][c+1])
               dp1[r+1][c+1] = max(dp0[r+1][c+1] + location[r+1][c+1], dp1[r+1][c])
               dp2[r+1][c+1] = max(dp1[r+1][c] + location[r+1][c+1], dp2[r+1][c])
               dp3[r+1][c+1] = max(dp2[r+1][c] + location[r+1][c+1], dp3[r+1][c])
            else:
               dp0[r+1][c+1] = max(dp0[r+1][c], dp0[r][c+1], dp1[r][c+1], dp2[r][c+1], dp3[r][c+1])
               dp1[r+1][c+1] = max(dp0[r+1][c+1], dp1[r+1][c])
               dp2[r+1][c+1] = max(dp1[r+1][c], dp2[r+1][c])
               dp3[r+1][c+1] = max(dp2[r+1][c], dp3[r+1][c])
if R==1 and C==1:
   ans = i[-1][-1]
else:
   ans = max(dp0[R-1][C-1], dp1[R-1][C-1], dp2[R-1][C-1], dp3[R-1][C-1])
print(ans)

### FIXED CODE ###

import sys
import copy
R, C, K = map(int, input().split())
item = [[0] * (C + 1) for _ in range(R + 1)]  # dp配列と合わせるために, 0行目, 0列目を追加している.
for s in sys.stdin.readlines():
    r, c, v = map(int, s.split())
    r -= 1
    c -= 1
    item[r][c] = v
    
dp0 = [[0] * (C+1) for r in range(R+1)]
dp1 = [[0] * (C+1) for r in range(R+1)]
dp2 = [[0] * (C+1) for r in range(R+1)]
dp3 = [[0] * (C+1) for r in range(R+1)]
 
for r in range(R):
   for c in range(C):
      dp3[r][c] = max(dp3[r][c], dp2[r][c] + item[r][c])
      dp2[r][c] = max(dp2[r][c], dp1[r][c] + item[r][c])
      dp1[r][c] = max(dp1[r][c], dp0[r][c] + item[r][c])
      dp1[r][c+1] = max(dp1[r][c], dp1[r][c+1])
      dp2[r][c+1] = max(dp2[r][c], dp2[r][c+1])
      dp3[r][c+1] = max(dp3[r][c], dp3[r][c+1])
      dp0[r+1][c] = max(dp0[r+1][c], dp1[r][c])
      dp0[r+1][c] = max(dp0[r+1][c], dp2[r][c])
      dp0[r+1][c] = max(dp0[r+1][c], dp3[r][c])
ans = max(dp0[R-1][C-1], dp1[R-1][C-1])
ans = max(ans, dp3[R-1][C-1])
ans = max(ans, dp2[R-1][C-1])
print(ans)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
la=[]
for i in range(1,n+1):
  la.append(l.index(i)+1)
ans=[str(j) for j in la]
ans=" ".join(ans)
print(ans)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
la=[0]*n
for i in range(n):
  la[l[i]-1]=i+1
ans=[str(j) for j in la]
ans=" ".join(ans)
print(ans)
### BUGGY CODE ###

#https://qiita.com/vain0x/items/fbde8b66927b84080811
#http://kmjp.hatenablog.jp/entry/2019/09/01/1000
#2人の選手が互いに相手を次の対戦相手に指定しているとき以外組めない
#したがって貪欲で一意

n = int(input())
a = []

for i in range(n):
    ai = list(map(int, input().split( )))
    ai.reverse()
    for j in range(n-1):
        ai[j]-=1
    a.append(ai)

##キューの管理のどこがおかしいかわからなかったがあきらめる

can={i for i in range(n)}
nxt=set()
Done = set()
cnt = 0
rem=n*(n-1)//2
while rem:
    cnt+=1
    for i in can:
        if i not in Done and a[i]:
            p = a[i][-1]
            if p not in Done:##この判定しないと1日に複数回試合することになる
                if a[p][-1]==i:
                    a[p].pop();a[i].pop()
                    Done.add(p);Done.add(i)
                    rem-=1
                    nxt.add(i);nxt.add(p)

    can=nxt.copy()###copy
    Done=set()
    if not can:
        break
       
if rem:
    print(-1)
else:       
    print(cnt)
        
        
        


### FIXED CODE ###

#https://qiita.com/vain0x/items/fbde8b66927b84080811
#http://kmjp.hatenablog.jp/entry/2019/09/01/1000
#2人の選手が互いに相手を次の対戦相手に指定しているとき以外組めない
#したがって貪欲で一意

n = int(input())
a = []

for i in range(n):
    ai = list(map(int, input().split( )))
    ai.reverse()
    for j in range(n-1):
        ai[j]-=1
    a.append(ai)

##キューの管理のどこがおかしいかわからなかったがあきらめる

can={i for i in range(n)}
nxt=set()
cnt = 0
rem=n*(n-1)//2
while rem:
    cnt+=1
    for i in can:
        if i not in nxt and a[i]:
            p = a[i][-1]
            if p not in nxt:##この判定しないと1日に複数回試合することになる
                if a[p][-1]==i:
                    a[p].pop();a[i].pop()
                    nxt.add(i);nxt.add(p)
    rem-=len(nxt)//2

    can=nxt.copy()###copy
    nxt=set()
    if not can:
        break
       
if rem:
    print(-1)
else:       
    print(cnt)
### BUGGY CODE ###

def bsort(l):
  import random
  while 1:
    random.shuffle(l)
    for i in range(1,len(l)):
      if l[i]<l[i-1]:
        break
    else:
      return l
i=lambda:list(map(int,input().split()))
n,m,x,y=i()
if bsort(i()+[x])[-1]<bsort(i()+[y])[0]:
    print('No War')
else:
    print('War')

### FIXED CODE ###

x,y=input().split()[2:];print('No '*(max(map(int,input().split()+[x]))<min(map(int,input().split()+[y])))+'War')
### BUGGY CODE ###

def int_raw():
    return int(raw_input())

def ss_raw():
    return raw_input().split()

def ints_raw():
    return map(int, ss_raw())

INF = 1 << 29
DIV = 10**9 +7
N,X  = ints_raw()
Ss = ints_raw()

Ss.sort()

def rec(n,subSs):
    if len(subSs) ==1:
        return n%subSs[0]
    else:
        neoSub = subSs[:len(subSs)-1]
        return (rec(n,neoSub)*(len(subSs)-1) + rec(n%subSs[-1],neoSub))%DIV

def ans():
    return rec(X,Ss)

print ans()


### FIXED CODE ###

def int_raw():
    return int(raw_input())

def ss_raw():
    return raw_input().split()

def ints_raw():
    return map(int, ss_raw())

INF = 1 << 29
DIV = 10**9 +7
N,X  = ints_raw()
dp = [{} for x in xrange(X+1)]

Ss = ints_raw()

Ss.sort()


def rec(n,idx):
    if idx == 0:
        return n%Ss[0]
    elif idx in dp[n]:
        return dp[n][idx]
    else:
        ans = (rec(n,idx-1)*idx + rec(n%Ss[idx],idx-1))%DIV
        dp[n][idx]=ans
        return ans

def ans():
    return rec(X,N-1)

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

import sys
input = sys.stdin.readline

k,q=map(int,input().split())
D=tuple(map(int,input().split()))

for query in range(q):
    n,x,m=map(int,input().split())

    D2=[d%m for d in  D]
    S=sum(D2)
    D0=D2.count(0)
    R=(n-1)//k
    ANS=R*(k-D0) - (R*S+x%m)//m 

    x2=(x+S*R)%m
    rest=n-R*k-1
    S2=sum(D2[:rest])
    DR0=D2[:rest].count(0)
    ANSR=rest - DR0 - (x2+S2)//m

    print(ANS+ANSR)
    


### FIXED CODE ###

import sys
input = sys.stdin.readline

k,q=map(int,input().split())
D=tuple(map(int,input().split()))

def sum_count(A):
    S=0
    C=0
    for a in A:
        if a==0:
            C+=1
        else:
            S+=a
    return S,C

for query in range(q):
    n,x,m=map(int,input().split())

    D2=[d%m for d in  D]
    S,D0=sum_count(D2)
    R=(n-1)//k
    ANS=R*(k-D0) - (R*S+x%m)//m 
    x2=(x+S*R)%m
    rest=n-R*k-1
    S2,DR0=sum_count(D2[:rest])
    ANSR=rest - DR0 - (x2+S2)//m

    print(ANS+ANSR)
### BUGGY CODE ###

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

def main(N, lst_A):

    sum_comb = 0
    lst_cntA = []

    for i in range(1, N+1):
        cntA  = lst_A.count(i)
        combA = (cntA * (cntA-1)) // 2
        
        sum_comb += combA
        lst_cntA.append(cntA)

    for A in lst_A:
        print(sum_comb - (lst_cntA[A-1]-1))

    return 0

if __name__ == "__main__":

    main(N, lst_A)
    

### FIXED CODE ###

from collections import Counter

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

def main(N, lst_A):

    dct_cntA = Counter(lst_A)
    sum_comb = 0

    for cntA in dct_cntA.values():
        comb = (cntA * (cntA - 1)) // 2
        sum_comb += comb

    for A in lst_A:
        print(sum_comb - (dct_cntA[A] - 1))

    return 0

if __name__ == "__main__":

    main(N, lst_A)
### BUGGY CODE ###

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

cnt = 0

for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
         if   i + j + k == S:
            cnt += 1

print(cnt)

### FIXED CODE ###

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

cnt = 0

for i in range(K+1):
    for j in range(K+1):
        z = S - i - j
        if 0 <= z <= K:
            cnt += 1

print(cnt)
### BUGGY CODE ###

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

if (N == 0):
    print(N)
elif (N == K):
    print(0)
elif (K == 1):
    print(0)
elif (K == 2 and N % 2 == 0):
    print(0)
elif (K == 2 and N % 2 == 1):
    print(1)
else:
    while (N >= 0):
        if (N > abs(N - K)):
            N = abs(N - K)
        else:
            print(N)
            break

### FIXED CODE ###

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

N = N % K

if (N == 0):
    print(N)
elif (N == K):
    print(0)
elif (K == 1):
    print(0)
else:
    while (N >= 0):
        if (N > abs(N - K)):
            N = abs(N - K)
        else:
            print(N)
            break
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = INT()
l = 0
r = n - 1
print(l)
sys.stdout.flush()
ltmp = STR() #初期状態 偶数席
if ltmp == 'Vacant':
    exit()
print(r)
sys.stdout.flush()
rtmp = STR() #最終状態 奇数
if rtmp == 'Vacant':
    exit()
cnt = 2
while l < r:
    cnt += 1
    c = (l + r) // 2
    print(c)
    sys.stdout.flush()
    tmp = STR()
    if tmp == 'Vacant':
        exit()
    if c % 2 == l % 2:
        if tmp == ltmp:
            l = c
        else:
            r = c
    else:
        if tmp == ltmp:
            r = c
        else:
            l = c

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = INT()
l = 0
r = n - 1
print(l, flush=True)
ltmp = STR()
if ltmp == 'Vacant':
    exit()
print(r, flush=True)
rtmp = STR()
if rtmp == 'Vacant':
    exit()
for i in range(2, 20):
    c = (l + r) // 2
    print(c, flush=True)
    tmp = STR()
    if tmp == 'Vacant':
        exit()
    if c % 2 == l % 2:
        if tmp == ltmp:
            l = c
            ltmp = tmp
        else:
            r = c
    else:
        if tmp == ltmp:
            r = c
        else:
            l = c
            ltmp = tmp
### BUGGY CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = list(map(int, input().split()))
P =[]
Y = []
for i in range(M):
    P.append(0)
    Y.append(0)
    P[i], Y[i] = list(map(int, input().split()))

dic = {}
for i in range(M):
    dic[P[i]] = [Y[i]] if not P[i] in dic else dic[P[i]] + [Y[i]]
    dic[P[i]] = sorted(dic[P[i]])

# print(dic)
import numpy as np
for i in range(M):
    num = dic[P[i]].index(Y[i]) + 1
    # num = sorted(dic[P[i]]).index(Y[i]) + 1
    print("{0:06d}{1:06d}".format(P[i], num))

### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = list(map(int, input().split()))
P =[]
Y = []
yp = [(0,0,0)] * M
for i in range(M):
    P.append(0)
    Y.append(0)
    P[i], Y[i] = list(map(int, input().split()))
    yp[i] = (Y[i], P[i], i)

yp.sort()
dic = {}
# for i in range(M):
#     dic[P[i]] = [Y[i]] if not P[i] in dic else dic[P[i]] + [Y[i]]
#     dic[P[i]] = sorted(dic[P[i]])

# print(yp)
pre = [0] * (N+1)
ansnum = [0] * M
for (y,p,i) in yp:
    pre[p] += 1
    ansnum[i] = "{0:06d}{1:06d}".format(p, pre[p])

import numpy as np
for i in range(M):
    print(ansnum[i])
    # num = yp[]
    # num = dic[P[i]].index(Y[i]) + 1
    # print("{0:06d}{1:06d}".format(P[i], num))
### BUGGY CODE ###

N=int(input())
A=[]
for _ in range(N):
  A.append(int(input()))

for i in range(N):
  b=A.pop(i)
  print(max(A))
  A.insert(i,b)
  

### FIXED CODE ###

N=int(input())
A=[]
for _ in range(N):
  A.append(int(input()))

value=max(A)
index = A.index(max(A))
for i in range(N):
  if i==index:
    b=A.pop(i)
    print(max(A))
  else:
      print(value)
### BUGGY CODE ###

N,a,b=map(int,input().split())
mod=10**9+7


def rapid_comb(N,K):
    bunsi=bunbo=1
    for i in range(K):
        bunsi*=(N-i)%mod
        bunbo*=(i+1)%mod
    return bunsi//bunbo

ans=((pow(2,N,mod)-1)%mod-rapid_comb(N,a)%mod-rapid_comb(N,b)%mod)%mod

print(ans%mod)

### FIXED CODE ###

N,a,b=map(int,input().split())
mod=10**9+7

def cmb(N,K):
    r=1

    for i in range(K):
        r=r*(N-i)*pow(i+1,mod-2,mod)%mod

    return r
ans=((pow(2,N,mod)-1)%mod-cmb(N,a)-cmb(N,b))%mod
#逆元の割り算のmodは、分子*逆元（分母)%modと等価　フェルマーの小定理から、 逆元はpow(b,mod-2,mod)となる
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
table = []
for i in range(m):
    nest_table = []
    l, r = map(int, input().split())
    nest_table.append(l)
    nest_table.append(r)
    table.append(nest_table)

ans = 0 
for j in range(n):
    for k in range(m):
        frag = 0
        if j+1 >= table[k][0] and j+1 <= table[k][1]:
            pass
        else:
            frag += 1
            break
    if frag == 0:
        ans += 1
print(ans)   

### FIXED CODE ###

n, m = map(int, input().split())
lower = 1
upper = 100000
for i in range(m):
    l, r = map(int, input().split())
    if l >= lower:
        lower = l
    if r <= upper:
        upper = r
        
if lower > upper:
    print(0)
else:    
    if n < upper:
        upper = n
    print(upper - lower + 1)
### BUGGY CODE ###

n=int(input())
li = list(map(int,input().split()))
ans=[]
a=""
for i in range(1,n+1):
  print(li.index(i)+1,end=" ")

### FIXED CODE ###

n=int(input())
li = list(map(int,input().split()))
ans=[0]*n
a=""
for (i,x) in zip(range(0,n), li):
  ans[x-1]=i+1
print(' '.join(map(str, ans)))
### BUGGY CODE ###

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

R = []
G = []
B = []

for i in range(N):
    if S[i] == 'R':
        R.append(i+1)
    elif S[i] == 'G':
        G.append(i+1)
    else:
        B.append(i+1)

#print(R, G, B)
res = 0

for i in R:
    for j in G:
        for k in B:
            l = [i, j, k]
            l.sort()
            if l[1] - l[0] != l[2] - l[1]:
                res += 1

print(res)

### FIXED CODE ###

from collections import defaultdict
N = int(input())
S = input()

R = []
G = []
B = []

d = defaultdict(int)
for i in range(N):
    if S[i] == 'R':
        R.append(i+1)
    elif S[i] == 'G':
        G.append(i+1)
    else:
        B.append(i+1)
        d[i+1] = 1

res = 0
bl = len(B)
sb = set(B)
for r in R:
    for g in G:
        for b in [2*r-g, 2*g-r, g+(r-g)/2]:
            res -= d[b]
        res += bl


#        for k in B:
#            res += 1

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

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

def ALDS1_5A():
    n, A, q = int(input()), list(map(int, input().split())), int(input())
    for Mj in input().split():
        if CanItBeCreated(A, n, 0, int(Mj)):
            print('yes')
        else:
            print('no')
if __name__ == '__main__':
    ALDS1_5A()

### FIXED CODE ###

def ALDS1_5A():
    n, A, q = int(input()), list(map(int, input().split())), int(input())
    S=[False for i in range(2001)]
    for a in A:
        for i in range(2001-a, 0, -1):
            if S[i]: S[i+a] = True
        S[a] = True
    for mi in input().split():
        if S[int(mi)]:
            print('yes')
        else:
            print('no')

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

M=10**9+7
N=int(input())
la=list(map(int,input().split()))
ans=0
for i in range(60):
    n0=0
    n1=0
    for j in range(N):
        if la[j]&1:
            n1+=1
        else:
            n0+=1
        la[j]>>=1
    ans=(ans+n0*n1%M*(2**i%M))%M
print(ans)


### FIXED CODE ###

M=10**9+7
N=int(input())
la=list(map(int,input().split()))
ans=0
for i in range(60):
    n0=0
    n1=0
    for j in range(N):
        if la[j]&1:
            n1+=1
        else:
            n0+=1
        la[j]>>=1
    ans=(ans+n0*n1%M*(2**i%M))%M
print(ans)
### BUGGY CODE ###

from collections import deque

K, N = map(int, input().split())
S=deque(list(map(int, input().split())))

ans = [S[-1] - S[0]]
for i in range(N-1):
    s = max(S) - K
    del S[-1]
    S.appendleft(s)
    ans.append(S[-1] - S[0])


print(min(ans))

### FIXED CODE ###

from collections import deque
K, N = map(int, input().split())
S=deque(list(map(int, input().split())))
ans = [S[-1] - S[0]]
for i in range(N-1):
    ans.append(S[i]- S[i+1] + K)
print(min(ans))
### BUGGY CODE ###

import copy
n=int(input())
A=sorted([int(i) for i in input().split()])
list_a=copy.deepcopy(A)
set_A=set(list_a)
ans=0
for i in set_A:
    a=A.count(i)
    if a<i:
        ans+=a
    elif i<a:
        ans+=a-i

print(ans)


### FIXED CODE ###

from collections import Counter
n=int(input())
A=Counter([int(i) for i in input().split()])
#print(A)
ans=0
for i in A.items():
#    print(i)
    k=i[0]
    l=i[1]
    if k<l:
        ans+=l-k
    elif l<k:
        ans+=l

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

import sys
input = sys.stdin.readline
from collections import deque, Counter

N = int(input())
X = [[] for i in range(N)]
L = [0]*N
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)
    L[x-1] += 1
    L[y-1] += 1

P = [-1] * N
Q = deque([0])
R = []
while Q:
    i = deque.popleft(Q)
    R.append(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            X[a].remove(i)
            deque.append(Q, a)

C = Counter(P)
##### Settings
unit = 0
merge = lambda a, b: a + b
adj_bu = lambda a, i: (a+1)/C[P[i]]
adj_td = lambda a, i, p: ((XX[P[i]]*L[P[i]]-XX[i]*C[P[i]])/max(1,L[P[i]]-1)+1)/max(1,C[i])
adj_fin = lambda a, i: a*max(1,C[i])/L[i]
#####

ME = [unit] * N
XX = [0] * N
TD = [unit] * N
for i in R[1:][::-1]:
    XX[i] = adj_bu(ME[i], i)
    p = P[i]
    ME[p] = merge(ME[p], XX[i])
XX[R[0]] = adj_fin(ME[R[0]], R[0])

for i in R:
    ac = TD[i]
    for j in X[i]:
        TD[j] = ac
        ac = merge(ac, XX[j])

    ac = unit
    for j in reversed(X[i]):
        TD[j] = adj_td(merge(TD[j], ac), j, i)
        ac = merge(ac, XX[j])
        XX[j] = adj_fin(merge(ME[j], TD[j]), j)

print(*XX, sep = "\n")

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque, Counter

N = int(input())
X = [[] for i in range(N)]
L = [0]*N
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)
    L[x-1] += 1
    L[y-1] += 1

P = [-1] * N
Q = deque([0])
R = []
while Q:
    i = deque.popleft(Q)
    R.append(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            X[a].remove(i)
            deque.append(Q, a)

C = Counter(P)
##### Settings
unit = 0
merge = lambda a, b: a + b
adj_bu = lambda a, i: (a+1)/C[P[i]]
adj_td = lambda a, i, p: ((XX[P[i]]*L[P[i]]-XX[i]*C[P[i]])/max(1,L[P[i]]-1)+1)/max(1,C[i])
adj_fin = lambda a, i: a*max(1,C[i])/L[i]
#####

ME = [unit] * N
XX = [0] * N
TD = [unit] * N
for i in R[1:][::-1]:
    XX[i] = adj_bu(ME[i], i)
    p = P[i]
    ME[p] = merge(ME[p], XX[i])
XX[R[0]] = adj_fin(ME[R[0]], R[0])

for i in R:
    ac = TD[i]
    for j in X[i]:
        TD[j] = ac
        ac = merge(ac, XX[j])

    ac = unit
    for j in reversed(X[i]):
        TD[j] = adj_td(merge(TD[j], ac), j, i)
        ac = merge(ac, XX[j])
        XX[j] = adj_fin(merge(ME[j], TD[j]), j)

print(*XX, sep = "\n")
### BUGGY CODE ###

from math import *
a,b,c,d = map(int,input().split())
f =(c*d)//gcd(c,d)
r = f
rock = 2
compteur= 0
while f<=b:
  if f>=a and f<=b:
    compteur +=1
  f = r*rock
  rock += 1
div1 = ((b//c)-(a//c))
div2 = ((b//d)-(a//d))
if  a%c == 0:
  div1+=1
if a%d ==0:
  div2 +=1
roger =(div1+div2)-compteur
mm = (b-a)+1
print(mm-roger)

### FIXED CODE ###

from math import *
a,b,c,d = map(int,input().split())
f =(c*d)//gcd(c,d)
r = f
rock = 2
compteur= (b//f)-(a//f)
if a%f==0:
  compteur +=1
div1 = ((b//c)-(a//c))
div2 = ((b//d)-(a//d))
if  a%c == 0:
  div1+=1
if a%d ==0:
  div2 +=1
roger =(div1+div2)-compteur
mm = (b-a)+1
print(mm-roger)
### BUGGY CODE ###

def main():
    n = int(input())
    As = list(map(int, input().split()))

    ans = 1
    for i in range(n):
        ans *= As[i]
        if ans == 0:
            break

    if ans > 10**18:
        ans = -1

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    As = list(map(int, input().split()))

    ans = 1
    if 0 in As:
        print(0)
        exit()

    for i in range(n):
        ans *= As[i]
        if ans > 10**18:
            ans = -1
            break

    print(ans)


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

N = input()
a=(map(int, raw_input().split()))

o=[]
e=[]

if len(a)%2==0:
  mid=N/2
  for i in range(mid):
    e.append(str(a[2*i]))
    o.insert(0, str(a[2*i+1]))
else:
  mid=N/2
  for i in range(mid):
    o.insert(0,str(a[2*i]))
    e.append(str(a[2*i+1]))
  o.insert(0, str(a[-1]))

print ' '.join(o)+' '+' '.join(e)


### FIXED CODE ###

N = input()
a=(map(str, raw_input().split()))

odd=a[1::2]
even=a[0::2]

if N%2==0:
    print ' '.join(reversed(odd))+' '+' '.join(even)
else:
    print ' '.join(reversed(even))+' '+' '.join(odd)
### BUGGY CODE ###

def inlist(lista,item):
    for i in lista:
        if item==i:
            return True
    return False


itemsList=[]
num=int(input())
for i in range(num):
    temp=input()
    if not inlist(itemsList,temp):
        itemsList.append(temp)
print(len(itemsList))


### FIXED CODE ###



itemsList={}
num=int(input())
for i in range(num):
    temp=input()
    if not temp in itemsList:
        itemsList[temp]=1
print(len(itemsList))
### BUGGY CODE ###


import numpy as np

n = int(input().strip())
l = list(map(int, input().split()))
l = np.array(l)

tot = 0
for i in range(n):
    tot += (l[i] * (np.sum(l[i+1:n], dtype = 'int64') % (10**9 + 7))) % (10**9 + 7)
    '''
    if tot >= 10**9 + 7:
        tot %= (10**9 + 7)
    '''

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

### FIXED CODE ###



def main():
    n = int(input().strip())
    l = list(map(int, input().split()))
    stack = [0]*n

    totstack = 0
    for i in range(n-1):
        totstack += l[n-i-1]
        stack[n-i-2] = totstack

    tot = 0
    for i in range(n):
        tot += (l[i] * (stack[i] % (10 ** 9 + 7))) % (10 ** 9 + 7)

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


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

n=int(input())
a=list(map(int,(input().split())))
l=1
for i in range(n):
    l*=a[i]
if l>10**18:
    print('-1')
else:
    print(l)


### FIXED CODE ###

n=int(input())
a=list(map(int,(input().split())))
l=1
a=sorted(a)
for i in range(n):
    l*=a[i]
    if l>10**18:
        print('-1')
        exit()
print(l)
### BUGGY CODE ###

#d
import copy
n = int(input())
n_list = []
ans = 0
for i in range(1,n+1):
    n_list.append(i)
m_list = copy.copy(n_list)
tmp = m_list.pop(n-1)

print(sum(m_list))

### FIXED CODE ###

n = int(input())
ans = (n*(n-1))//2
print(ans)