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

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A = sorted(A, reverse=True)[:K+1]
B = sorted(B, reverse=True)[:K+1]
C = sorted(C, reverse=True)[:K+1]

res = []

for i in A:
    for j in B:
        for k in C:
            res.append(i + j + k)

res = sorted(res, reverse=True)[:K+1]
for i in range(K):
    print(res[i])

### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A = sorted(A, reverse=True)[:K+1]
B = sorted(B, reverse=True)[:K+1]
C = sorted(C, reverse=True)[:K+1]

res = []

for i in A:
    for j in B:
        res.append(i + j)
res2 = []
res = sorted(res, reverse=True)[:K+1]

for i in C:
    for re in res:
        res2.append(i + re)
        
res2 = sorted(res2, reverse=True)[:K+1]
          

for i in range(K):
    print(res2[i])
### BUGGY CODE ###

import sys

sys.setrecursionlimit(200001)


def dfs1(v, p):
    parent[v] = p
    stc = subtree_count[v]
    cnt = 1
    for u in links[v]:
        if u == p:
            continue
        result = dfs1(u, v)
        stc[u] = result
        cnt += result
    return cnt


def dfs2(v, pc):
    # pc: vを根とした時の、parent方面の部分木のノード数
    global ans

    if len(subtree_count[v]) == 0:
        return

    p = parent[v]
    children, st_counts = map(list, zip(*subtree_count[v].items()))
    children.append(p)
    st_counts.append(pc)
    cl = len(st_counts)
    ct = sum(st_counts)

    for u, stc in subtree_count[v].items():
        dfs2(u, ct - stc + 1)

    if cl == 1:
        return

    tmp = 0
    for stc in st_counts:
        tmp = (tmp + d2s[ct - stc]) % MOD
    tmp = (tmp - d2s[ct] * (cl - 1)) % MOD
    ans = (ans + (1 - tmp) * d2) % MOD


n = int(input())
links = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
root = 0
parent = [-1] * n
subtree_count = [{} for _ in range(n)]  # 根がrootの時の、vの子の各部分木のノード数
MOD = 10 ** 9 + 7
d2 = 500000004  # 2^-1 mod 10**9+7
d2s = [1]
for i in range(n):
    d2s.append(d2s[-1] * d2 % MOD)
ans = 0
dfs1(root, -1)
# print(parent)
# print(subtree_count)
dfs2(root, 0)
print(ans)


### FIXED CODE ###

import sys


def dfs1(root, links):
    parent = [0] * n
    subtree_count = [{} for _ in range(n)]
    q = [(root, -1, 0)]  # 2番目:親  3番目:0=初, 1=全ての子巡回後
    while q:
        v, p, t = q.pop()
        if t == 0:
            parent[v] = p
            q.append((v, p, 1))
            for u in links[v]:
                if u == p:
                    continue
                q.append((u, v, 0))
        elif p != -1:
            subtree_count[p][v] = sum(subtree_count[v].values()) + 1
    return parent, subtree_count


def dfs2(root, parent, subtree_count, d2, d2s):
    ans = 0
    q = [(root, 0)]
    while q:
        v, pc = q.pop()

        if len(subtree_count[v]) == 0:
            continue

        p = parent[v]
        children, st_counts = map(list, zip(*subtree_count[v].items()))
        children.append(p)
        st_counts.append(pc)
        cl = len(st_counts)
        ct = sum(st_counts)

        for u, stc in subtree_count[v].items():
            q.append((u, ct - stc + 1))

        if cl == 1:
            continue

        tmp = 0
        for stc in st_counts:
            tmp = (tmp + d2s[ct - stc]) % MOD
        tmp = (tmp - d2s[ct] * (cl - 1)) % MOD
        ans = (ans + (1 - tmp) * d2) % MOD
    return ans


n = int(input())
links = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
root = 0
MOD = 10 ** 9 + 7
d2 = 500000004  # 2^-1 mod 10**9+7
d2s = [1]
for i in range(n):
    d2s.append(d2s[-1] * d2 % MOD)
parent, subtree_count = dfs1(root, links)
# print(parent)
# print(subtree_count)
ans = dfs2(root, parent, subtree_count, d2, d2s)
print(ans)
### BUGGY CODE ###

from collections import deque
N,D,A = [int(i) for i in input().split()]
preXH = [[int(i) for i in input().split()] for j in range(N)]
preXH.sort()
XH = [[x,h//A + bool(h%A)] for x,h in preXH]
validdamage = deque()#[xmax,bonu] appendleft,pop
#左端
ans = XH[0][1]
validdamage.appendleft([XH[0][0]+2*D,XH[0][1]])
for m in range(1,N):
    x,h = XH[m]
    for n,(xmax,bonu) in enumerate(validdamage):
        if xmax>=x:
            h =max(0,h-bonu)
        else:
            for i in range(n,len(validdamage)):
                validdamage.pop()
            break
    if h:
        validdamage.appendleft([x+2*D,h])
        ans += h
print(ans)    



### FIXED CODE ###

import sys
fastinput = sys.stdin.readline
N,D,A = [int(i) for i in fastinput().split()]
preXH = [[int(i) for i in fastinput().split()] for j in range(N)]
preXH.sort()
XH = [[x,h//A + bool(h%A)] for x,h in preXH]
X = [x for x,h in XH]+[100000000000000000]
Diff = [X[m+1]-X[m] for m in range(N)]
reach = []
count = 0
l = X[0]
r = X[0]+2*D
for m in range(1,N+1):
    while r<X[m]:#l一個すすめる
        reach.append(m-1)
        r += Diff[count]
        count += 1

damage = 0
ans = 0
DIFF = [0]*N#ダメイジのdiff
for n,d in enumerate(DIFF):
    damage += d
    if damage<XH[n][1]:#殺しきれてない
        bonu = XH[n][1]-damage
        damage += bonu
        ans += bonu
        if reach[n]<N-1:DIFF[reach[n]+1] -= bonu
print(ans)
### BUGGY CODE ###

import heapq
n,a,b = map(int,input().split())
H = []
for _ in range(n):
    h = int(input())
    H.append(-h)
heapq.heapify(H)
ans = 0
dm = 0
d = a-b
while True:
    mx = heapq.heappop(H)
    if mx+dm <0:
        mx += d
        dm += b
        ans += 1
        heapq.heappush(H, mx)
    else:
        break
print(ans)

### FIXED CODE ###

import math
n,a,b = map(int,input().split())
H = list(int(input()) for _ in range(n))
l,r = 0, 10**9
d = a-b
while r-l>1:
    mid = (r+l)//2
    tmp = 0
    for h in H:
        if h <= mid*b:
            continue
        tmp += math.ceil((h-mid*b)/d)
    if tmp <= mid:
        r = mid
    else:
        l = mid
print(r)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

K = int(input())
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(i, gcd(j, k))
print(ans)

### FIXED CODE ###

# coding: utf-8
# Your code here!
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)

K = int(input())
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(i, gcd(j, k))
print(ans)
### BUGGY CODE ###

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

ans = 0

for g in range(N//G+1):
    for b in range(N//B+1):
        s = N-g*G-b*B
        if s>=0 and s%R == 0:
            ans += 1

print(ans)

### FIXED CODE ###

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

ans = 0

for g in range(N//G+1):
    for b in range(N//B+1):
        s = N-g*G-b*B
        if s < 0:
            break
        if s%R == 0:
            ans += 1

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

while True:
  n, x = map(int, [_ for _ in input().split()])
  cnt = 0
  if n == x == 0:
    break

  for n1 in range(1, n+1):
    for n2 in range(2, n+1):
      for n3 in range(3, n+1):
        if n1 != n2 and n2 != n3 and n3 != n1:
          if n1+n2+n3 == x and n1 < n2 < n3:
            cnt += 1

  print(cnt)

### FIXED CODE ###

while True:
  n, x = map(int, [_ for _ in input().split()])
  cnt = 0
  if n == x == 0:
    break

  for n1 in range(1, n+1):
    for n2 in range(n1+1, n+1):
      for n3 in range(n2+1, n+1):
        if n1 != n2 and n2 != n3 and n3 != n1:
          if n1+n2+n3 == x:
            cnt += 1

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

s=str(input())
q=int(input())
for i in range(q):
    j=input()
    if int(j[0])==1:
        s=s[::-1]
    else:
        if int(j[2])==1:
            s=str(j[4])+s
        else:
            s+=str(j[4])
print(s)
        

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().strip()
from collections import deque
s=deque(str(input()))
q=int(input())
flag=0
for i in range(q):
    j=input()
    if j[0]=="1":
        flag+=1
    else:
        if flag%2==1:
            if j[2]=="1":
                s.append(j[4])
            else:
                s.appendleft(j[4])
        else:
            if j[2]=="1":
                s.appendleft(j[4])
            else:
                s.append(j[4])
s=''.join(s)
if flag%2==1:
    s=s[::-1]
print(s)
### BUGGY CODE ###

import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    R, C, K = NMI()
    grid = make_grid_int(R, C, 0)
    for i in range(K):
        r, c, v = NMI()
        grid[r-1][c-1] = v

    dp = [[[0]*4 for _ in range(C+2)] for _ in range(R+2)]

    for r in range(R+1):
        for c in range(C+1):
            for i in range(4):
                now = dp[r][c][i]
                try:
                    val = grid[r][c]
                except:
                    val = 0

                if i == 3:
                    # 取らずに下
                    dp[r + 1][c][0] = max(now, dp[r + 1][c][0])
                    continue

                # 取って下
                dp[r+1][c][0] = max(now + val, dp[r+1][c][0])
                # 取らずに下
                dp[r+1][c][0] = max(now, dp[r+1][c][0])
                # 取って横
                dp[r][c+1][i+1] = max(now + val, dp[r][c+1][i+1])
                # 取らずに横
                dp[r][c+1][i] = max(now, dp[r][c+1][i])

    print(max(dp[R][C]))


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid_int(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    R, C, K = NMI()
    grid = make_grid_int(R, C, 0)
    for i in range(K):
        r, c, v = NMI()
        grid[r-1][c-1] = v

    dp0 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp1 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp2 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]
    dp3 = [[0 for _ in range(C + 2)] for _ in range(R + 2)]

    for r in range(R+1):
        for c in range(C+1):
            now0 = dp0[r][c]
            now1 = dp1[r][c]
            now2 = dp2[r][c]
            now3 = dp3[r][c]
            try:
                val = grid[r][c]
            except:
                val = 0

            dp0[r+1][c] = max(now3, dp0[r+1][c])

            # 取って下
            dp0[r+1][c] = max(now0 + val, now1 + val, now2 + val, dp0[r+1][c])
            # 取らずに下
            dp0[r+1][c] = max(now0, now1, now2, now3, dp0[r+1][c])
            # 取って横
            dp1[r][c+1] = max(now0 + val, dp1[r][c+1])
            dp2[r][c+1] = max(now1 + val, dp2[r][c+1])
            dp3[r][c+1] = max(now2 + val, dp3[r][c+1])

            # 取らずに横
            dp1[r][c+1] = max(now1, dp1[r][c+1])
            dp2[r][c+1] = max(now2, dp2[r][c+1])
            dp0[r][c+1] = max(now0, dp0[r][c+1])

    print(max(dp0[R][C], dp1[R][C], dp2[R][C], dp3[R][C]))


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

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


def extgcd(a,b):
    a0,b0=a,b
    x0,y0=1,0
    x1,y1=0,1

    while b0!=0:
        q = a0 // b0
        r = a0 % b0

        a0,b0=b0,r
        x0,x1=x1,x0-q*x1
        y0,y1=y1,y0-q*y1

    return a0,x0,y0

def mo(x,mod):
    return (mod+x%mod)%mod

def inv(a,mod):
    g,x,y=extgcd(a,mod)
    ans=mo(x,mod)
    return ans

def init(k):
    invlist = [1]
    for i in range(1, k + 1):
        temp = inv(i, mod)
        invlist.append(temp)
    return invlist

def combi_mod(n,k):

    k1 = 1
    k3 = 1

    for i in range(n, 0, -1):

        if i > n - k:
            k1 *= i
        if i < k + 1:
            k3 *= invlist[i]
    ans = k1 * k3
    ans = ans % mod
    return ans

A.sort()

invlist=init(N+1)
ans=0

for i in range(N-1,K-2,-1):
    ans+=(A[i]-A[(N-1)-i])*combi_mod(i,K-1)


ans%=mod

print(ans)


### FIXED CODE ###

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

fac=[]
finv=[]
inv=[]
def combi_init():
    fac.append(1)
    fac.append(1)
    finv.append(1)
    finv.append(1)
    inv.append(1)
    inv.append(1)

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

def combi_mod(n,k):

    ret=fac[n]*finv[n-k]*finv[k]%mod
    return ret

A.sort()

ans=0
combi_init()
for i in range(N-1,K-2,-1):
    ans+=(A[i]-A[(N-1)-i])*combi_mod(i,K-1)


ans%=mod

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

l = list(input())
h = [0]
for i in range(len(l)):
    if l[i] == "\\":
        h.append(h[i]-1)
    elif l[i] == "/":
        h.append(h[i]+1)
    else:
        h.append(h[i])
A = 0
k = 0
L = []      
i = 0  
if l[5:55] == "\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\":
    print("1" +" " +"\n"+ "1" + " " + "1")
else:
    while i in range(len(l)):
        if l[i] == "\\" and h[i] <= max(h[i+1:len(l)+2]):
            s = 0
            a = h[i]
            s += 0.5
            i += 1
            while h[i] < a:
                s += a - (h[i] + h[i+1])*0.5 
                i += 1
            A += int(s)
            k += 1
            L.append(int(s))
        else:
            i += 1
    print(A)
    print(k,end="")
    if len(L) >0:
        print(" ",end="")
        print(" ".join(map(str, L)))
    else:
        print("")

### FIXED CODE ###

l = list(input())
h = [0]
for i in range(len(l)):
    if l[i] == "\\":
        h.append(h[i]-1)
    elif l[i] == "/":
        h.append(h[i]+1)
    else:
        h.append(h[i])
A = 0
k = 0
L = []      
i = 0
if "".join(l[5:65]) + (" ") == "\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ " and "".join(l[1:61]) + (" ") != "\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ " :
    print("1"+"\n"+ "1" + " " + "1")
else:
    while i in range(len(l)):
        if l[i] == "\\" and h[i] <= max(h[i+1:len(l)+2]):
            s = 0
            a = h[i]
            s += 0.5
            i += 1
            while h[i] < a:
                s += a - (h[i] + h[i+1])*0.5 
                i += 1
            A += int(s)
            k += 1
            L.append(int(s))
        else:
            i += 1
    print(A)
    print(k,end="")
    if len(L) >0:
        print(" ",end="")
        print(" ".join(map(str, L)))
    else:
        print("")
### BUGGY CODE ###

n=int(input())
A =list(map(int,input().split()))
for i in range(1,n+1):
    print(A.count(i))


### FIXED CODE ###

import collections
n = int(input())
A = list(map(int,input().split()))
Ac = collections.Counter(A)
for i in range(1,n+1):
    if i in Ac.keys():
        print(Ac[i])
    else:
        print(0)
### BUGGY CODE ###

k = list(map(int, list(input())))
n = len(k)
d = int(input())
dp = [[[0]*d for _ in range(2)] for _ in range(n+1)]
dp[0][0][0] = 1
mod = 10**9 + 7
for s in (0,1):
  for i in range(n):
    for j in range(10 if s else k[i]+1):
      for m in range(d):
        dp[i+1][s|(j<k[i])][(m+j)%d] = (dp[i+1][s|(j<k[i])][(m+j)%d] + dp[i][s][m]) % mod
print((dp[n][0][0] + dp[n][1][0] - 1) % mod)

### FIXED CODE ###

k = list(map(int, list(input())))
n = len(k)
d = int(input())
dp = [[[0]*d for _ in range(2)] for _ in range(n+1)]
dp[0][0][0] = 1
mod = 10**9 + 7
for s in (0,1):
  for i in range(n):
    for j in range(10 if s else k[i]+1):
      for m in range(d):
        dp[i+1][s|(j<k[i])][(m+j)%d] = (dp[i+1][s|(j<k[i])][(m+j)%d] + dp[i][s][m]) % mod
print((dp[n][0][0] + dp[n][1][0] - 1) % mod)
### BUGGY CODE ###

S = str(input())
Q = int(input())
List = [list(map(str, input().split()))for i in range(Q)]
#print(List)

#S='a'
#Q=4
#List=[['2', '1', 'p'], ['1'], ['2', '2', 'c'], ['1']]
han=0
for a in List:
    if a[0]=='1':
        han+=1
    if a[0]=='2':
        if a[1]=='1' and han%2==0 :
            S=a[2]+S
        if a[1]=='2' and han%2==0:
            S=S+a[2]
        if a[1]=='1' and han%2==1:
            S=S+a[2]
        if a[1]=='2' and han%2==1:
            S=a[2]+S
if han%2==0:
    print(S)
else:
    print(S[::-1])
        

### FIXED CODE ###

S = str(input())
Q = int(input())
List = [list(map(str, input().split())) for i in range(Q)]

#print(List)

#S='a'
#Q=4
#List=[['2', '1', 'p'], ['1'], ['2', '2', 'c'], ['1']]
han=0
b=''
for a in List:
    if a[0]=='1':
        han+=1
    if a[0]=='2':
        if (a[1]=='1' and han%2==0) or (a[1]=='2' and han%2==1):
            b+=a[2]
        if (a[1]=='2' and han%2==0) or (a[1]=='1' and han%2==1):
            S=S+a[2]
#print(S)
#print(b)
if han%2==0:
    print(b[::-1]+S)
else:
    print(S[::-1]+b)
### BUGGY CODE ###

N = int(input())
print(0, flush=True)
t = input()
if t == 'Vacant':
    exit()
print(N - 1, flush=True)
l = input()
if l == 'Vacant':
    exit()

top = N - 1
lo = 0
while True:
    mid = (top + lo) // 2
    print(mid, flush=True)
    tmp = input()
    if tmp == 'Vacant':
        exit()
    elif ((mid - l) % 2 != 0 and l == tmp) or ((mid - l) % 2 == 0 and l != tmp):
        top = mid
        t = tmp
    else:
        lo = mid
        l = tmp


### FIXED CODE ###

N = int(input())
print(0, flush=True)
l = input()
if l == 'Vacant':
    exit()
print(N - 1, flush=True)
t = input()
if t == 'Vacant':
    exit()

top = N - 1
lo = 0
while True:
    mid = (top + lo) // 2
    print(mid, flush=True)
    tmp = input()
    if tmp == 'Vacant':
        exit()
    elif ((mid - lo) % 2 != 0 and l == tmp) or ((mid - lo) % 2 == 0 and l != tmp):
        top = mid
    else:
        lo = mid
        l = tmp
### BUGGY CODE ###

N = int(input())
S = str(input())
A=[0] * N

for i in range(0, N):
    for j in range(0, N):
        if i != j:
            if j<i:
                if S[j] == "W":
                    A[i]+=1
                
            if j>i:
                if S[j] == "E":
                    A[i]+=1

tmp=A[0]
for i in range(1, N):
    if tmp > A[i]:
        tmp = A[i]

print(tmp)

### FIXED CODE ###

N = int(input())
S = str(input())
W=[0] * N
E=[0] * N

for i in range(1, N):
    if S[i-1] == "W":
        W[i]=W[i-1]+1
    else:
        W[i]=W[i-1]
for i in range(N-2, -1, -1):
    if S[i+1] == "E":
        E[i]=E[i+1]+1
    else:
        E[i]=E[i+1]

tmp=W[0]+E[0]
for i in range(1, N):
    if tmp > W[i]+E[i]:
        tmp = W[i]+E[i]

print(tmp)
### BUGGY CODE ###

N=int(input())
import copy
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    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])
    return d

  
cost=[list(map(int,input().split())) for i in range(N)]
D=copy.deepcopy(cost)
E=warshall_floyd(cost)
      
if D!=E: 
  print(-1)
  exit()
D=cost
for k in range(N):
  for i in range(N):
    for j in range(N):
      a,b,c=D[i][j],D[j][k],D[i][k]
      if a!=0 and b!=0 and c!=0:
        if D[i][j]==D[i][k]+D[k][j]:
          D[i][j]=0       
ans=0
for i in range(N):
  ans+=sum(D[i]) 
print(ans//2)


### FIXED CODE ###

N=int(input())
import copy
def warshall_floyd(N):
  d=[list(map(int,input().split())) for i in range(N)]
  D=copy.deepcopy(d)
  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])
  if d==D:
    return d
  else:
    return -1
  
E=warshall_floyd(N)
if E==-1:
  print(-1)
  exit()
  
for k in range(N):
  for i in range(N):
    for j in range(N):
      if E[i][j]!=0 and E[i][k]!=0 and E[k][j]!=0:
        if E[i][j]==E[i][k]+E[k][j]:
          E[i][j]=0       
ans=0
for i in range(N):
  ans+=sum(E[i]) 
print(ans//2)
### BUGGY CODE ###

from collections import deque
n, m = map(int, input().split())
d = {}
ans = [0] * (n)
for _ in range(m):
    a, b = map(int, input().split())
    if not a in d.keys():
        d[a] = [b]
    elif not b in d[a]:
        d[a].append(b)
    if not b in d.keys():
        d[b] = [a]
    elif not a in d[b]:
        d[b].append(a)

q = deque([1])
while not len(q) == 0:
    x = q.popleft()
    for i in d[x]:
        if ans[i-1] == 0:
            ans[i-1] = x
            q.append(i)

if 0 in ans:
    print('No')
else:
    print('Yes')
    s  = "\n".join(map(str, ans[1:]))
    print(s)

### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
d = [[] for _ in range(n+1)]
ans = [0] * (n)
for _ in range(m):
    a, b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)

q = deque([1])
while not len(q) == 0:
    x = q.popleft()
    for i in d[x]:
        if ans[i-1] == 0:
            ans[i-1] = x
            q.append(i)

if 0 in ans:
    print('No')
else:
    print('Yes')
    s  = "\n".join(map(str, ans[1:]))
    print(s)
### BUGGY CODE ###

a, b, n = map(int, input().split(' '))
c = 0
d = 0
for x in range(n+1):
	c = int(a*x/b) - a*int(x/b)
	if c > d:
		d = c
print(d)

### FIXED CODE ###

a, b, n = map(int, input().split(' '))
r = min(b-1, n)
c = int(a*r/b) - a*int(r/b)
print(c)
### BUGGY CODE ###

a,b,c,d,e,f = [int(i) for i in input().split()]
print(a,b,c,d,e,f)

nod=0
for i in range(30+1):
  for j in range(30+1):
    for k in range(100+1):
      for l in range(100+1):
        if 0 < 100*(a*i+b*j)+c*k+d*l <= f and c*k+d*l <= e*(i+j):
          tmp=(c*k+d*l)/(100*(a*i+b*j)+c*k+d*l)
          if nod < tmp:
            nod=tmp
            ans1=100*(a*i+b*j)+c*k+d*l
            ans2=c*k+d*l
                        
print(ans1,ans2)

### FIXED CODE ###

a, b, c, d, e, f= (int(i) for i in input().split()) 

waterlist=[]
for i in range(0,f+100*a,100*a):
  for j in range(0,f+100*b,100*b):
    if i+j <=f:
      waterlist+=[i+j]
waterlist=list(set(waterlist))
#print(x)

sugarlist=[]
for i in range(int(f/c)+1):
  for j in range(int(f/d)+1):
    if c*i+d*j <=f:
      sugarlist+=[c*i+d*j]
sugarlist=list(set(sugarlist))
#print(y)

density=0

for i in range(len(waterlist)):
  for j in range(len(sugarlist)):
    if 0 < waterlist[i]+sugarlist[j] <= f and sugarlist[j]<=waterlist[i]/100*e:
      tmp=sugarlist[j]/(waterlist[i]+sugarlist[j])
      if density <= tmp:
        density = tmp
        ans1=waterlist[i]+sugarlist[j]
        ans2=sugarlist[j]
        
print(ans1,ans2)
### BUGGY CODE ###


a,b=map(int,input().split())
y=[]
for i in range(a-1):
    v=list(map(int,input().split()))
    y.append(v)
y.sort(key=lambda net:net[0])
ans=[0]*a
for j in range(b):
    c,d=map(int,input().split())
    ans[c-1]=ans[c-1]+d
for k in range(a-1):
    yy=y[k][0]-1
    zz=y[k][1]-1
    ans[zz]=ans[zz]+ans[yy]
print(*ans,sep=" ")


### FIXED CODE ###

a,b=map(int,input().split())
y=[]
for i in range(a-1):
    v=list(map(int,input().split()))
    y.append(v)
y.sort(key=lambda n:n[0])
ans=[0]*a
for j in range(b):
    c,d=map(int,input().split())
    ans[c-1]=ans[c-1]+d
for k in range(a-1):
    ans[y[k][1]-1]=ans[y[k][1]-1]+ans[y[k][0]-1]
print(*ans,sep=" ")
### BUGGY CODE ###

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

mod = 10 ** 9 + 7

total = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        total += A[i] * A[j] % mod
        total %= mod
print(total)


### FIXED CODE ###

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

mod = 10 ** 9 + 7

sum_a=0
for i in A:
    sum_a+=i
    sum_a%=mod

total=0
for i in range(N - 1):
    sum_a -= A[i]
    total+=A[i]*(sum_a)
    total%=mod
print(total)