Harryxun/sft_time huggingface dataset:
### 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]*L[p]-XX[i]*C[p])/max(1,L[p]-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 = 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 collections import deque
N, Q = map(int, input().split())
count = [0 for i in range(N)]
graph = {i:[] for i in range(N)}

for i in range(N-1):
  a, b = map(int, input().split())
  graph[a-1]+=[b-1]
  graph[b-1]+=[a-1]

for i in range(Q):
  p, x = map(int, input().split())
  count[p-1] += x

q = deque([0])
log = [True]*N
log[0]=False
while q:
  v = q.popleft()
  ls = graph[v]
  for l in ls:
    if log[l]:
      q.append(l)
      log[l]=False
      count[l] += count[v]
ans = [str(i) for i in count]
print(' '.join(ans))

### FIXED CODE ###

from collections import deque
N, Q = map(int, input().split())
G = [[] for _ in range(N)]
count = [0]*N
for i in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
for i in range(Q):
    p, x = map(int, input().split())
    count[p-1]+=x
q = deque([0])
flag = [False]*N
while q:
    v = q.pop()
    flag[v] = True
    for e in G[v]:
        if flag[e]:
            continue
        count[e]+=count[v]
        q.append(e)
print(*count)
### BUGGY CODE ###

S = input()
Q = int(input())
for i in range(Q):
    q = list(input().split())
    if len(q)==1:
        S = S[::-1]
    elif int(q[1])==1:
        S = q[2]+S
    else:
        S += q[2]
print(S)

### FIXED CODE ###

S = input()
Q = int(input())
s = 0
s1 = []
s2 = []
for i in range(Q):
    q = list(input().split())
    s += int(q[0])
    if q[0]=='2':
        s_i = s + int(q[1]) 
        if s_i%2 == 0:
            s1.append(q[2])
        else:
            s2.append(q[2])
s1 = ''.join(s1)
s2 = ''.join(s2)
s2 = s2[::-1]
S = s2 + S + s1
if s%2 == 0:
    print(S)
else:
    print(S[::-1])
### BUGGY CODE ###

N, K = map(int, input().split())
points = [tuple(map(int, input().split())) for i in range(N)]

ptsX = sorted(points, key=lambda t: t[0])
ptsY = sorted(points, key=lambda t: t[1])

ans = float('inf')
for sideL in range(N):
    for sideR in range(sideL + 1, N):
        for sideB in range(N):
            for sideT in range(sideB + 1, N):

                area = (ptsX[sideR][0] - ptsX[sideL][0]) * (ptsY[sideT][1] - ptsY[sideB][1])

                setX = set(ptsX[sideL:sideR + 1])
                setY = set(ptsY[sideB:sideT + 1])
                num = len(setX & setY)

                if num == K:
                    ans = min(ans, area)

print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
points = [tuple(map(int, input().split())) for i in range(N)]

ptsX = sorted(points, key=lambda t: t[0])
ptsY = sorted(points, key=lambda t: t[1])

ans = float('inf')
for iLeft, ptLeft in enumerate(ptsX):
    setX = set(ptsX[iLeft:])

    for ptRight in ptsX[iLeft + 1:][::-1]:
        if len(setX) < K: break
        lenX = ptRight[0] - ptLeft[0]

        for iBottom, ptBottom in enumerate(ptsY):
            setY = set(ptsY[iBottom:])

            for ptTop in ptsY[iBottom + 1:][::-1]:
                if len(setY) < K: break

                num = len(setX & setY)
                if num < K: break

                if num == K:
                    lenY = ptTop[1] - ptBottom[1]
                    area = lenX * lenY
                    ans = min(ans, area)

                setY.remove(ptTop)

        setX.remove(ptRight)

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

def reversed_num(num):
  num_len=len(bin(num))-2
  f=2**num_len-1
  return num^f
n=int(input())
number=list(map(int,input().split()))
number.sort()
count=0
while len(number)>0:
  if reversed_num(number[-1])+1 in number and number[-1]!=reversed_num(number[-1])+1:
    number.remove(reversed_num(number[-1])+1)
    count+=1
print(count)


### FIXED CODE ###

import bisect
def reversed_num(num):
  num_len=len(bin(num))-2
  f=2**num_len-1
  return num^f
n=int(input())
number=list(map(int,input().split()))
number.sort()
count=0
while len(number)>0:
  k=number.pop()
  if len(number)==0:
    break
  if k==int(k):
    x=reversed_num(k)+1
    y=bisect.bisect_left(number,x)
    if x>number[-1]:
      y-=1
    if number[y] ==x:
      number[y]-=0.5
      count+=1
print(count)
### BUGGY CODE ###

from math import factorial as f

def nCr(n, r):
    return int(f(n) / (f(r) * f(n-r)))
    
N = int(input())
lisA = list(map(int, input().split()))

lisB = [0]
m = 0
for e in lisA:
    m += e
    lisB.append(m)

lisRed = [nCr(lisB.count(e), 2) for e in set(lisB) if lisB.count(e) > 1]
ans = sum(lisRed)

print(ans)


### FIXED CODE ###

from collections import defaultdict as dd
from math import factorial as f

def nCr(n, r):
    return int(f(n) / (f(r) * f(n-r)))
    
N = int(input())
lisA = list(map(int, input().split()))

lisB = [0]
m = 0
for e in lisA:
    m += e
    lisB.append(m)

d = dd(int)

for e in lisB:
    d[e] += 1

ans = 0
for e in d.values():
    if e > 1:
        ans += nCr(e,2)

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

from bisect import insort_left
N, M=map(int, input().split())
A=[]
Y=[[] for _ in range(N)] #県
for i in range(M):
  p,y=map(int, input().split())
  A.append((p,y))
  Y[p-1].append(y)

for i in range(N):
  if Y[i]:
    Y[i].sort()

for i in range(M):
  p,y=A[i]
  y=str(Y[p-1].index(y)+1)
  p=str(p)
  ans="0"*(6-len(p))+p+"0"*(6-len(y))+y
  print(ans)

### FIXED CODE ###


N, M=map(int, input().split())
#A=[]
Y=[[] for _ in range(N)] #県
for i in range(M):
  p,y=map(int, input().split())
  #A.append((p,y))
  Y[p-1].append([y,i+1])

for i in range(N):
  if Y[i]:
    Y[i].sort(key=lambda x: x[0])
#indexは時間かかる
ans=[]
for i in range(N):
  for j,L in enumerate(Y[i]):
    p,y,n=i+1, L[0],L[1]
    ans.append((n,p,j+1))
ans=sorted(ans)
for n,p,y in ans:
  a=(6-len(str(p)))*"0"+str(p)+(6-len(str(y)))*"0"+str(y)
  print(a)
### BUGGY CODE ###

N=int(input())
s=False
for i in range(1,3501):
    for j in range(1,3501):
        if (4*i*j-N*i-N*j)==0:
            continue
        else:
            w=(N*i*j)/(4*i*j-N*i-N*j)
            flag=w.is_integer()
            if flag==True and w>0:
                p=i
                q=j
                s=True
                break
            else:
                continue
    if s==True:
        break

print("{} {} {}".format(p,q,int(w)))

### FIXED CODE ###

N=int(input())
s=False
for i in range(1,3501):
    for j in range(1,3501):
        if (4*i*j-N*i-N*j)>0:
            w=(N*i*j)/(4*i*j-N*i-N*j)
            if w%1==0:
                p=i
                q=j
                s=True
                break
    if s==True:
        break

print("{} {} {}".format(p,q,int(w)))
### BUGGY CODE ###

n=int(input())
b=[sorted(list(input())) for i in range(n)]
g=0
for i in b:
    g+=(b.count(i)-1)
print(int(g*0.5))

### FIXED CODE ###

import math
import collections

n=int(input())
a=[list(input()) for i in range(n)]
b=[str(sorted(list(i))) for i in a]
count=list(collections.Counter(b).values())
count=[i for i in count if i>1]
print(int(sum([math.factorial(x)/(math.factorial(x-2)*2) for x in count])))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,k = map(int, input().split())
num = list(map(int, input().split()))
cns = set(num)
f = [num.count(i) for i in cns]
f.sort(reverse=True)
print(sum(f[k::]))

### FIXED CODE ###

import sys
input = sys.stdin.readline
import collections
n,k = map(int, input().split())
num = list(map(int, input().split()))
cns = collections.Counter(num)
f = [cns[i] for i in cns]
f.sort(reverse=True)
print(sum(f[k::]))
### BUGGY CODE ###

import numpy as np
import copy

n = int(input())
c = np.zeros((n-1), dtype=np.int)
s = np.zeros((n-1), dtype=np.int)
f = np.zeros((n-1), dtype=np.int)
for i in range(n-1):
    c[i], s[i], f[i] = map(int, input().split(" "))

t = np.zeros(n, dtype=np.int)
for i in range(n-1):
    w = np.zeros((n-1), dtype=np.int)
    w = copy.deepcopy(s)
    t[i] = s[i] + c[i]
    for j in range((i+1), (n-1), 1):
        k = 0
        while(True):
            if(w[j] >= t[i]):
                t[i] = w[j]
                break
            for l in range(j, (n-1), 1):
                if(t[i] > w[l]):
                    w[l] += f[l]
        t[i] += c[j]

for i in range(n):
    print(t[i])

### FIXED CODE ###

import numpy as np
import copy

n = int(input())
c = np.zeros((n-1), dtype=np.int)
s = np.zeros((n-1), dtype=np.int)
f = np.zeros((n-1), dtype=np.int)
for i in range(n-1):
    c[i], s[i], f[i] = map(int, input().split(" "))

t = np.zeros(n, dtype=np.int)
for i in range(n-1):
    t[i] = s[i] + c[i]
    for j in range((i+1), (n-1), 1):
        if(s[j] >= t[i]):
            t[i] = s[j]
        elif(t[i] % f[j] != 0):
            t[i] += f[j] - (t[i] % f[j])
        t[i] += c[j]

for i in range(n):
    print(t[i])
### BUGGY CODE ###

import sys,random
input = sys.stdin.readline


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

    if n <= 10000:
        p = 0
        q = 0
        for eA,eB in zip(a,b):
            p = (p+eA)<<30
            q = (q+eB)<<30
        p = p>>30
        q = q>>30


        for k in range(n):
            hyp = b[0]^a[k]
            judge = p^q
            if (judge^((judge>>30)<<30)) == hyp and (judge^((judge>>60)<<60))>>30 == hyp:
                print(k,hyp)
            q = (q>>30) + (b[n-1-k]<<(30*(n-1)))
    else:
        for k in range(n):
            hyp = b[0]^a[k]
            judge = True
            for _ in [0]*300:
                w = random.randrange(n)
                if b[w] != a[(w+k)%n]^hyp:
                    judge = False
                    break
            if judge:
                print(k,hyp)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

#Z[i]:length of the longest list starting from S[i] which is also a prefix of S
def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg


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


BAA = []
for i in range(n-1):
    BAA.append(b[i]^b[i+1])
BAA.append(b[0]^b[-1])

BAA.append(-1)

for i in range(n-1):
    BAA.append(a[i]^a[i+1])
BAA.append(a[0]^a[-1])
for i in range(n-1):
    BAA.append(a[i]^a[i+1])
BAA.append(a[0]^a[-1])

z = Z_algorithm(BAA)

for k in range(n):
    if z[n+k+1] >= n:
        print(k,b[0]^a[k])
### BUGGY CODE ###

s = input()

ans = 0
start = 0

for i in range(3, len(s)):
    for j in range(i+1, len(s)+1):
        if int(s[start:j]) % 2019 == 0:
            ans += 1

    start += 1
    
print(ans)

### FIXED CODE ###

from collections import Counter
s = input()

s = s[::-1]

x = 1
mod = 2019
total = 0
ans = 0
cnt = Counter()

for i in range(len(s)):
    cnt[total] += 1
    total = total + int(s[i])*x
    total %= mod
    ans += cnt[total]
    x = x*10%mod

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

A,B,C,D,E,F = map(int,input().split())

W = []
S = []

#水の重さのリストW
for i in range(F+1):
    for j in range(F+1):
        x = 100*A*i + 100*B*j
        W.append(x)

#砂糖の重さのリストS
for i in range(F+1):
    for j in range(F+1):
        y = C*i + D*j
        S.append(y)

maxcon = 0
limitcon = 100*E/(100+E)
ans1 = 0
ans2 = 0


for i in range(1,len(W)):
    for j in range(1,len(S)):
        sw = W[i] + S[j]
        con = 100*S[j] / sw
        if (sw <= F) and (con <= limitcon) and (maxcon < con):
            maxcon = con
            ans1 = sw
            ans2 = S[j]



print("%s %s"%(ans1,ans2))

### FIXED CODE ###

A,B,C,D,E,F=map(int,input().split())

best_sugarwater = 100*A
best_sugar = 0
best_con = 0
max_con = E/(100+E)

maxA = F//(100*A)
for i in range(maxA+1):
    maxB = (F-100*A*i)//(100*B)
    for j in range(maxB+1):
        water = 100*A*i+100*B*j
        maxC = (F-100*A*i-100*B*j)//C
        for k in range(maxC+1):
            maxD = (F-100*A*i-100*B*j-C*k)//D
            for l in range (maxD+1):
                sugar = C*k+D*l
                if sugar + water == 0 :
                    pass
                elif (best_con < sugar/(sugar + water) <= max_con ):
                    best_sugarwater = sugar + water
                    best_sugar = sugar
                    best_con = sugar/(sugar + water)

print(best_sugarwater,best_sugar)
### BUGGY CODE ###

N = int(input())
tmp = [[] for i in range(N + 1)]
tmp[0] = [0]
chk = []
s = [1]

for i in range(5):
    s.append(9** (i + 1))
for i in range(6):
    s.append(6** (i + 1))
s.sort()

for i in range(1, N + 1):
    t_l = []
    for j in range(len(tmp[i - 1])):
        for k in range(12):
            a = tmp[i - 1][j] + s[k]
            if a <= N and a not in chk:
                t_l.append(a)
                chk.extend(t_l)
    tmp[i].extend(t_l)
    if N in tmp[i]:
        break
print(i)

### FIXED CODE ###

N = int(input())
tmp = [-1 for i in range(N + 1)]
tmp[0] = 0
s = [1]

for i in range(5):
    s.append(9** (i + 1))
for i in range(6):
    s.append(6** (i + 1))

for i in range(1, N+1):
    for j in range(N+1):
        if tmp[j] == i - 1:
            for k in range(12):
                a = j + s[k]
                if a <= N and tmp[a] == -1:
                    tmp[a] = i
    if tmp[N] > -1:
        break
print(i)
### BUGGY CODE ###

import sys
class Tree():
    def __init__(self):
        self.root = None
    def insert(self, key):
        z = Node(key)
        y = None
        x = self.root
        while x:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y
        if y == None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z
    def print(self):
        for order in ['Inorder', 'Preorder']:
            print('',' '.join([str(node.key) for node in self.root.walk(order)]))
    
class Node():
    def __init__(self, key):
        self.key = key
        self.parent = self.left = self.right = None
    def walk(self, order):
        orders = {'Preorder':[self, self.left, self.right], 'Inorder':[self.left, self, self.right], 'Postorder':[self.left, self.right, self]}
        
        for node in orders[order]:
            if node == self:
                yield node
            elif node:
                for childnode in node.walk(order):
                    yield childnode

                    
                    
tree = Tree()
n = sys.stdin.readline()
for line in sys.stdin:
    if line[0] == 'i':
        tree.insert(int(line.split()[1]))
    else:
        tree.print()

### FIXED CODE ###

import sys
class Tree():
    def __init__(self):
        self.root = None
    def insert(self, key):
        z = Node(key)
        y = None
        x = self.root
        while x:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y
        if y == None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z
    def print(self):
        print('',' '.join(map(str, self.root.inwalk())))
        print('',' '.join(map(str, self.root.prewalk())))
    
class Node():
    def __init__(self, key):
        self.key = key
        self.parent = self.left = self.right = None
    def prewalk(self):
        ret = [self.key]
        if self.left:
            ret += self.left.prewalk()
        if self.right:
            ret += self.right.prewalk()
        return ret
    def inwalk(self):
        ret = []
        if self.left:
            ret += self.left.inwalk()
        ret += [self.key]
        if self.right:
            ret += self.right.inwalk()
        return ret
tree = Tree()
n = sys.stdin.readline()
for line in sys.stdin:
    if line[0] == 'i':
        tree.insert(int(line.split()[1]))
    else:
        tree.print()
### BUGGY CODE ###

import sys
input=sys.stdin.readline

n,m,r=map(int,input().split())
iku=list(map(int,input().split()))
iku=list(map(lambda x:x-1,iku))
iku="".join(list(map(str,iku)))

g=[[float("inf")]*n for _ in range(n)]

for _ in range(m):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    g[a][b]=c
    g[b][a]=c

for i in range(n):
    g[i][i]=0

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
warshall_floyd(g)

from itertools import permutations
x=list(permutations(iku,len(iku)))
ans=float("inf")
for l in x:
    ans2=0
    for i in range(1,r):
        ans2+=g[int(l[i-1])][int(l[i])]
    ans=min(ans,ans2)

print(ans)


### FIXED CODE ###

from scipy.sparse.csgraph import shortest_path
import numpy as np
import itertools

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

edge=np.zeros((n+1,n+1))
for i in range(m):
    a,b,c=map(int,input().split())
    edge[a,b]=c

dist=shortest_path(edge,directed=False).astype(int)

ans=10**18
for v in itertools.permutations(r):
    ans2=0
    p=v[0]
    for x in v[1:]:
        if p!=None:
            ans2+=dist[p,x]
        p=x
    ans=min(ans,ans2)

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

import bisect

N = int(input())
L = list(map(int, input().split()))
assert len(L) == N

L.sort()

n = 0

# Choose two edges
for i in range(N):
    for j in range(i + 1, N):
        a = L[i] + L[j]
        k = bisect.bisect_left(L, a, lo=j + 1)
        #   assert all(v < a for v in L[:k]) and all(v >= a for v in L[k:])
        # the number of candidates of the third edge
        n += k - (j + 1)

print(n)


### FIXED CODE ###

import bisect

N = int(input())
L = list(map(int, input().split()))
assert len(L) == N

L.sort()

n = 0
# Choose two edges
for i in range(N):
    for j in range(i + 1, N):
        a = L[i] + L[j]
        k = bisect.bisect_left(L, a, lo=j + 1)
        #   assert all(v < a for v in L[:k]) and all(v >= a for v in L[k:])
        # the number of candidates of the third edge
        n += k - (j + 1)

print(n)
### BUGGY CODE ###

k,s = map(int,input().split())

count = 0
for x in range(k+1):
  for y in range(k+1):
    for z in range(k+1):
      if x + y + z == s:
        count += 1

print(count)

### FIXED CODE ###

k,s = map(int,input().split())

count = 0
for x in range(k+1):
  for y in range(k+1):
    a = s - x - y
    if a >= 0 and a <= k:
      count += 1

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


N, Q = map(int, input().split())
S = input()
for _ in range(Q):
    l, r = map(int, input().split())
    p = S[l-1:r]

    print(p.replace('AC', 'x').count('x'))

### FIXED CODE ###


N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)

'''
累積和
t[1] = t[0] + (if S[0]からの2文字がACなら1 or 0) → AC の C 位置なら1
t[2] = t[1] + (if S[1]からの2文字がACなら1 or 0)
t[3] = t[2] + (if S[2]からの2文字がACなら1 or 0)
t[4] = t[3] + (if S[3]からの2文字がACなら1 or 0)
t[5] = t[4] + (if S[4]からの2文字がACなら1 or 0)
t[6] = t[5] + (if S[5]からの2文字がACなら1 or 0)
t[7] = t[6] + (if S[6]からの2文字がACなら1 or 0)
t[8] = t[7] + (if S[7]からの2文字がACなら1 or 0)

# 01234567
# ACACTACG
# 011222333
'''

for i in range(N):
    t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)

#print(t)

for i in range(Q):
    l, r = map(int, input().split())

    # 3, 7 なら、t[7-1] - t[3-1]
    #  → t[5]以下の数 - t[1]以下の数
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

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

B = A.copy()
B.remove(max(A))
second_max = max(B)
for i in range(N):
    if A[i] == max(A):
        print(second_max)
    else:
        print(max(A))

### FIXED CODE ###

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

B = sorted(A)
A_max, A_second_max = B[-1], B[-2] 
for i in A:
    if i == A_max:
        print(A_second_max)
    else:
        print(A_max)
### BUGGY CODE ###

from itertools import permutations

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

r=list(map(int,input().split()))

for i in range(len(r)):
    r[i]-=1
    
A=[]
a=[]
for i in range(N):
    for j in range(N):
        a.append(1000000)
    A.append(a)
    a=[]
#print(A)

for i in range(M):
    a,b,c=map(int,input().split())
    A[a-1][b-1]=c
    A[b-1][a-1]=c
#print(A)

for c in range(N):
    for a in range(N):
        for b in range(N):
            A[a][b]=min(A[a][b],A[a][c]+A[c][b])
#print(A)

ans=10000000
for i in permutations(r,len(r)):
    cnt=0
    for j in range(len(i)-1):
        cnt+=A[i[j]][i[j+1]]
    if ans>cnt:
        ans=cnt
print(ans)


### FIXED CODE ###

import itertools
N,M,R=map(int,input().split())
r=list(map(int,input().split()))

L=[[10**15 for i in range(N)]for j in range(N)]
for i in range(N):
    L[i][i]=0
for a in range(M):
    A,B,C=map(int,input().split())
    L[A-1][B-1]=C
    L[B-1][A-1]=C

#print(L)

for c in range(N):
    for a in range(N):
        for b in range(N):
            L[a][b]=min(L[a][b],L[a][c]+L[c][b])
#print(L)
LIS=list(itertools.permutations(r))
#print(LIS)
ans=10**15
#print(LIS[0][2])
for i in range(len(LIS)):
    cnt=0
    for x in range(1,len(r)):
        #print(i,x)
        cnt+=L[LIS[i][x-1]-1][LIS[i][x]-1]
    if cnt<ans:
        ans=cnt
print(ans)
### BUGGY CODE ###

S = list(map(int,list(input())))
N = len(S)
dp = [[0 for i in range(2019)] for j in range(N + 1)]
for i in range(N):
    for j in range(2019):
        dp[i+1][(10 * j + S[i]) % 2019] += dp[i][j]
    dp[i+1][S[i]] += 1
ans = 0
for i in range(N+1):
    ans += dp[i][0]
print(ans)

### FIXED CODE ###

from collections import Counter

S = list(map(int,list(input())))
S.reverse()
N = len(S)
L = [0]
power = 1
for i in range(N):
    L.append((L[-1] + S[i] * power) % 2019)
    power *= 10
    power %= 2019
count = Counter(L)
ans = 0
for value in count.values():
    ans += value * (value - 1) // 2
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    ans+=((a[i]*a[j])%(10**9+7))
ans=ans%(10**9+7)

print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
t=sum(a)
s=0
for i in range(n):
  s+=a[i]*a[i]

ans=(t*t-s)//2
ans=ans%(10**9+7)



print(ans)