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

#!/usr/bin python3
# -*- coding: utf-8 -*-

import numpy as np


def canReach(src, dst):
    dist = np.sum(np.abs([dst[1] - src[1], dst[2] - src[2]]))

    if (dst[0] - src[0]) - dist == 0:
        return True
    elif (dst[0] - src[0]) - dist > 0 and ((dst[0] - src[0]) - dist) % 2 == 0:
        return True
    return False


N = int(input())
dst = [[int(x) for x in input().split(" ")] for z in range(N)]

available = True
pos = [0, 0, 0]

for n in range(N):
    if not canReach(pos, dst[n]):
        available = False
        break
    else:
        pos = dst[n]

if available:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-

import numpy as np

N = int(input())
prev_dst = [0,0,0]

for n in range(N):
    t, x, y = map(int, input().split(" "))
    a = (t - prev_dst[0]) - (np.abs(prev_dst[1]-x) + np.abs(prev_dst[2]-y))
    if a >= 0 and a % 2 == 0:
        prev_dst = [t, x, y]
    else:
        print("No")
        exit(0)

print("Yes")
### BUGGY CODE ###


from collections import deque

n = int(input())
tree = [[] for i in range(n+1)]

for i in range(1,n):
    u, v, w = map(int, input().split())
    tree[u].append((v, w))
    tree[v].append((u, w))


stack = deque()
stack.append(1)
#stack=[1]
visitted=[]
ans=[0]*n

while stack:
    cur = stack.pop()
    pre=ans[cur-1]
    visitted.append(cur)
    for v, w in tree[cur]:
        if v in visitted:
            continue
        #if v in stack:
        #    continue
        if w % 2 == 1:
            ans[v-1]=(pre+1)%2
        else:
            ans[v-1]=pre
        stack.append(v)

print(*ans, sep='\n')

#for i in ans:
#    print(i)


### FIXED CODE ###

n = int(input())
tree = [[] for i in range(n+1)]

for i in range(1,n):
    u, v, w = map(int, input().split())
    tree[u].append((v, w))
    tree[v].append((u, w))

#print(tree)
stack=[1]
visitted={}
ans=[0]*n

while stack:
    cur = stack.pop()
    pre=ans[cur-1]
    visitted.setdefault(cur,1)
    #visitted.append(cur)
    for v, w in tree[cur]:
        if v in visitted:
            continue
        if w % 2 == 1:
            ans[v-1]=(pre+1)%2
        else:
            ans[v-1]=pre
        stack.append(v)

print(*ans, sep='\n')
### BUGGY CODE ###

N,M=map(int,input().split())
A=[list(map(int,input().split())) for i in range(M)]
D=[[]for i in range(N)]
for i in range(M):
  D[A[i][0]-1].append(A[i][1]-1)
  D[A[i][1]-1].append(A[i][0]-1)
for i in D[-1]:
  for j in D[0]:
    if i==j:
      print('POSSIBLE')
      exit()
print('IMPOSSIBLE')  

### FIXED CODE ###

N,M=map(int,input().split())
A=[list(map(int,input().split())) for i in range(M)]
D=[[]for i in range(N)]
for i in range(M):
  D[A[i][0]-1].append(A[i][1]-1)
  D[A[i][1]-1].append(A[i][0]-1)
a=len(D[-1])
b=len(D[0])
c=len(set(D[-1]+D[0]))
if a+b==c:
  print('IMPOSSIBLE')
else:
  print('POSSIBLE')
### BUGGY CODE ###

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

for i in range(M):
    A.sort()
    A[N-1] = int(A[N-1] / 2)

result = 0

for i in range(N):
    result += A[i]

print(result)

### FIXED CODE ###

import heapq
N,M = map(int , input().split(" "))
A = list(map(int, input().split(" ")))

A_q = list(map(lambda x:x*(-1),A))
heapq.heapify(A_q)

for i in range(M):

    max = heapq.heappop(A_q) * (-1) // 2
    heapq.heappush(A_q, -max)



result = 0
A_q = list(map(lambda x:x*(-1),A_q))

for i in range(N):
    result += A_q[i]

print(result)
### BUGGY CODE ###

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

cnt = 0
while True:
    flg = False
    for i in range(N):
        if a[i] % 2 == 0:
            a[i] /= 2
            break
        elif i == N - 1:
            print(cnt)
            flg = True
    if flg == True:
        break

    cnt += 1


### FIXED CODE ###

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

cnt = 0
for i in range(N):
    while True:
        if a[i] % 2 != 0:
            break
        else:
            cnt+=1
            a[i] = a[i] / 2
print(cnt)
### BUGGY CODE ###

from math import factorial
from collections import defaultdict
n=int(input())
l=list(map(int,input().split()))
d=defaultdict(lambda :0)
d1=defaultdict(lambda :0)
for i in range(n):
    d[l[i]]+=1
for i in d:
    x=d[i]
    if d[i]<2:
        d1[i]=0
    else:
        d1[i]=factorial(x)/(factorial(x-2)*2)
sum=0
for i in d1:
    sum+=d1[i]
d2=defaultdict(lambda :0)
for i in l:
    ans=0
    if i in d2:
        print(d2[i])
    else:
        if d[i]<3:
            ans=sum-d1[i]
        else:
            ans=sum-d1[i]+(factorial(d[i]-1)/(factorial(d[i]-3)*2))
        d2[i]=int(ans)
        print(int(ans))
                


### FIXED CODE ###

from collections import Counter
n=int(input())
ar=list(map(int,input().split()))
x=Counter(ar)
dct={}
y=list(set(ar))
pair=0
#print(x)
for i in y:
    ct=x[i]-1
    pair+=(ct*(ct+1))//2
#print(pair)
for i in range(n):
    el=ar[i]
    ct=x[el]-1
    add=((ct*(ct+1))//2)-(((ct-1)*((ct-1)+1))//2)
    #print("fff",add)
    print(pair-add)
### BUGGY CODE ###

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

from collections import Counter
d=Counter(a)

for i in range(n):
    c=d.copy()
    c[a[i]]-=1
    ans=0
    for v in c.values():
        ans+=v*(v-1)/2
    print(int(ans))


### FIXED CODE ###

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

from collections import Counter
d=Counter(a)
f={}
for k,v in d.items():
    f[k]=v*(v-1)/2

ans={}
s=sum(f.values())
for k in f.keys():
    ans[k]=(d[k]-1)*(d[k]-2)/2 + s- f[k]

for i in range(n):
    print(int(ans[a[i]]))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, Q: int, S: str, l: "List[int]", r: "List[int]"):
    ans = []
    for i in range(Q):
        ts = S[l[i]-1:r[i]].count('AC')
        # print(S[l[i]-1:r[i]])
        ans.append(ts)

    for i in range(Q):
        print(ans[i])
    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    l = [int()] * (Q)  # type: "List[int]" 
    r = [int()] * (Q)  # type: "List[int]" 
    for i in range(Q):
        l[i] = int(next(tokens))
        r[i] = int(next(tokens))
    solve(N, Q, S, l, r)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, Q: int, S: str, l: "List[int]", r: "List[int]"):
    ans = []
    carray = [0] * N
    for i in range(1,N):
        if(S[i-1:i+1] == 'AC'):
            carray[i] = carray[i-1]+1 
            # carray[i:] = map(lambda x:x+1, carray[i:])
        else:
            carray[i] = carray[i-1]
    # print(carray)
    for i in range(Q):
        # print(carray[l[i]-1:r[i]])
        t = carray[r[i]-1] - carray[l[i]-1]
        ans.append(t)

    for i in range(Q):
        print(ans[i])
    return


# Generated by 1.1.3 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    l = [int()] * (Q)  # type: "List[int]" 
    r = [int()] * (Q)  # type: "List[int]" 
    for i in range(Q):
        l[i] = int(next(tokens))
        r[i] = int(next(tokens))
    solve(N, Q, S, l, r)

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

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ac = [0 for i in range(10**6+2)]



for i in a:
    ac[i] +=1
a = sorted(set(a))
count =0

for i in a:
    if ac[i]>0:
        if ac[i] == 1:
            count += 1
        for j in a:
            if j%i==0 and not ac[j]==0:
                ac[j]=0


print(count)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ac = [0 for i in range(10**6+2)]



for i in a:
    ac[i] +=1
a = sorted(set(a))
count =0

for i in a:
    if ac[i]>0:
        if ac[i] == 1:
            count += 1
        for j in range(i,10**6+2,i):
            if not ac[j]==0:
                ac[j]=0


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

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = [0]*Q
C = [0]*Q

for i in range(Q):
    B[i], C[i] = map(str, input().split())

for i in range(Q):
    A = list(map(str, A))
    if B[i] in A:
        A = [a.replace(B[i], C[i]) for a in A]
    
    A = list(map(int, A))
    print(sum(A))

### FIXED CODE ###

from collections import Counter

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

cntA = Counter(A)

ans = sum(A)

for i in range(Q):
    B, C = map(int, input().split())

    ans += cntA[B]*(C - B)
    cntA[C] += cntA[B]
    cntA[B] = 0
    
    print(ans)
### BUGGY CODE ###

def solve():
    N, M = map(int, input().split())
    
    if M == 1:
        return 0
    
    n = N
    c = 0
    while True:
        n = n-M
        c = (abs(n) - M)
        
        if c <= 0:
            break

    return min(abs(n), abs(c))

print(solve())

### FIXED CODE ###

def solve():
    N, M = map(int, input().split())
    
    if N % M == 0:
        return 0
    
    a = N % M

    return min(a, abs(a-M))

print(solve())
### BUGGY CODE ###

from scipy.optimize import fmin

N,K = map(int,input().split())
XYC = [list(map(int,input().split())) for _ in [0]*N]

def f(xy):
    x,y = xy
    ret = []
    for X,Y,C in XYC:
        ret.append(C*(((X-x)**2+(Y-y)**2))**(0.5))
    ret.sort()
    return ret[K-1]

init = (0,0)
ans = f(init)
for x in range(-1000,1001,10):
    for y in range(-1000,1001,10):
        tmp = f((x,y))
        if ans > tmp:
            ans = tmp
            init = (x,y)

opt = fmin(f,init,ftol = 1e-7,disp=0)
ans = f(opt)

print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
XYC = [list(map(int,input().split())) for _ in [0]*N]
eps = 1e-7
def f(x,y,t):
    ret = 0
    for X,Y,C in XYC:
        if ((x-X)**2+(y-Y)**2)<=(t/C)**2+eps: ret += 1
    return ret

def get_cross_section(x1,y1,r1,x2,y2,r2):
    d = ((x1-x2)**2+(y1-y2)**2)**0.5
    X = (d*d+r1*r1-r2*r2)/(2*d)
    Y = max(0,(r1*r1-X*X))**0.5
    dx = (x2-x1)/d
    dy = (y2-y1)/d
    ret = [(x1+X*dx+Y*dy,y1+X*dy-Y*dx)]
    if Y>0 : ret.append((x1+X*dx-Y*dy,y1+X*dy+Y*dx))
    return ret
def check(t):
    kouho = []
    for i in range(N):
        x1,y1,c1 = XYC[i]
        kouho.append((x1,y1))
        for j in range(i+1,N):
            x2,y2,c2 = XYC[j]
            tmp = get_cross_section(x1,y1,t/c1,x2,y2,t/c2)
            for tmp2 in tmp:
                kouho.append(tmp2)
    for tmp in kouho:
        if f(tmp[0],tmp[1],t) >= K:return True
    return False

l=0
r=1000000
for _ in range(100):
    i = (l+r)/2
    if check(i):
        r = i
    else:
        l = i
print(r)
### BUGGY CODE ###

line = input().split(" ")
k = int(line[0])
s = int(line[1])
count = 0
for i in range(k+1):
  for j in range(k+1):
    for l in range(k+1):
      if s == i + j + l:
        count += 1
print(count)

### FIXED CODE ###

line = input().split(" ")
k = int(line[0])
s = int(line[1])
count = 0
for i in range(k+1):
  for j in range(k+1):
    if s - i - j <= k and s - i - j >= 0:
      count += 1
print(count)
### BUGGY CODE ###

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

L = ['R', 'G', 'B']
accum = [[0] * N for i in range(3)]
for i in range(3):
    l = L[i]
    if S[0] == l:
        accum[i][0] = 1
    for j in range(1, N):
        accum[i][j] = accum[i][j - 1] + (1 if S[j] == l else 0)

ans = 0
for j in range(1, N - 1):
    for i in range(j):
        if S[i] == S[j]:
            continue
        for k in range(3):
            if L[k] != S[i] and L[k] != S[j]:
                lk = L[k]
                ik = k
        ans += accum[ik][N - 1] - accum[ik][j]
        if 2 * (j + 1) - (i + 1) <= N and S[2 * (j + 1) - (i + 1) - 1] == lk:
            ans -= 1
print(ans)


### FIXED CODE ###

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

L = ['R', 'G', 'B']
accum = [[0] * N for i in range(3)]
for i in range(3):
    l = L[i]
    if S[0] == l:
        accum[i][0] = 1
    for j in range(1, N):
        accum[i][j] = accum[i][j - 1] + (1 if S[j] == l else 0)

ans = 0
for j in range(1, N - 1):
    for i in range(j):
        if S[i] == S[j]:
            continue
        for k in range(3):
            if L[k] != S[i] and L[k] != S[j]:
                lk = L[k]
                ik = k
        ans += accum[ik][N - 1] - accum[ik][j]
        if 2 * (j + 1) - (i + 1) <= N and S[2 * (j + 1) - (i + 1) - 1] == lk:
            ans -= 1
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
ans = 0
for i in range(0, N-K+1):
    ans = max((sum(p[i:i+K])+K)/2, ans)
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
ans = (sum(p[0:K])+K)/2
pre = ans
for i in range(1, N-K+1):
    pre -= (p[i-1]-p[i+K-1])/2
    ans = max(pre, ans)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)


def dfs(now, prev=-1):
    for next in tree[now]:
        # 1個前のノードを参照した時はcontinue
        if next == prev:
            continue

        # 現在のポイントを次のノードへ加算して累積和をとる
        point[next] += point[now]

        # 次のノードへ
        dfs(next, now)


N, Q = map(int, input().split())
tree = [[] for _ in range(N)]
point = [0]*N

# 木構造を2次元配列で表現。要素Xのノードからつながっているノード番号が格納される。
for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

# 各ノードのポイントを求める
for _ in range(Q):
    p, x = map(int, input().split())
    point[p-1] += x

dfs(0)
print(*point)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)


def input():
    return sys.stdin.readline()[:-1]


def dfs(now, prev=-1):
    for next in tree[now]:
        # 1個前のノードを参照した時はcontinue
        if next == prev:
            continue

        # 現在のポイントを次のノードへ加算して累積和をとる
        point[next] += point[now]

        # 次のノードへ
        dfs(next, now)


N, Q = map(int, input().split())
tree = [[] for _ in range(N)]
point = [0]*N

# 木構造を2次元配列で表現。要素Xのノードからつながっているノード番号が格納される。
for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)

# 各ノードのポイントを求める
for _ in range(Q):
    p, x = map(int, input().split())
    point[p-1] += x

dfs(0)
print(*point)
### BUGGY CODE ###

n,m = map(int,input().split())
if m%n==0:
    print(int(m//n))
    exit()
else:
  a = m//n
  for i in range(a,0,-1):
    s = m-n*i
    if (s+i)%i==0:
      print(i)
      exit()
    elif a>10**8 and i == 10**3:
      print(1)
      exit()

### FIXED CODE ###

n,m = map(int,input().split())
if m%n==0:
    print(int(m//n))
    exit()
else:
  a = m/n
  l = []
  for i in range(int(m**0.5),0,-1):
    if m%i==0:
      l.append(i)
      l.append(m//i)
  l = sorted(l)[::-1]
  for j  in l:
    if j<=a:
      print(j)
      exit()
  else:
    print(1)
### BUGGY CODE ###

def comb(n, r):
  result = 1
  
  for i in range(n, n - r, -1):
    result *= i
  for i in range(r, 1, -1):
    result //= i
  
  return result

n = int(input())
a = list(int(i) for i in input().split())

a.sort()
a.reverse()
max = 0

for i in range(1, n):
  c = comb(a[0], a[i])
  if c > max:
    max = c
  else:
    i -= 1
    break

print(a[0], a[i])


### FIXED CODE ###

n = int(input())
a = list(int(i) for i in input().split())

a.sort()
a.reverse()
max = 0

for i in range(1, n):
  m = min(a[0] - a[i], a[i])
  #c = comb(a[0], a[i])
  if m > max:
    max = m
  else:
    i -= 1
    break

if i == 0:
  print(a[0], a[1])
else:
  print(a[0], a[i])
### BUGGY CODE ###

N = int(input())
sum_N = 0

for i in range(len(str(N))):
  sum_N += int(str(N)[i])
  
if sum_N % 9 == 0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N = int(input())
sum_N = 0
S = str(N)

for i in range(len(S)):
  sum_N += int(S[i])
  
if sum_N % 9 == 0:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

mod = 998244353
N = int(input())
D = list(map(int, input().split()))
cnt_list = []
if D[0] != 0:
    print(0)
    exit()
for i in range(0, N):
    tmp = D.count(i)
    if tmp == 0:
        break
    cnt_list.append(tmp)
##print(cnt_list)
if len(cnt_list) != len(set(D)):
    print(0)
    exit()
if cnt_list[0] != 1:
    print(0)
    exit()
##print(cnt_list)
ans = 1
for i in range(1, len(cnt_list)):
    ans *= cnt_list[i-1] ** cnt_list[i]
    ans = ans % mod
print(ans)

### FIXED CODE ###

import collections
mod = 998244353
N = int(input())
D = list(map(int, input().split()))
if D[0] != 0:
    print(0)
    exit()
c = collections.Counter(D)
if c[0] != 1:
    print(0)
    exit()
##print(c)
ans = 1
##print(max(D))
for i in range(1, max(D)+1):
    if c[i] == 0:
        ans = 0
        break
    ans *= c[i-1] ** c[i]
    ans = ans % mod
    ##print(ans)
print(ans)
### BUGGY CODE ###

from collections import Counter, deque
n = int(input())
a = list(map(int, input().split()))
a.sort()

na = a[::]
ans = 0
while na:
    st = 0
    if len(na)>1 and na[0] == na[1]:
        st = 1
    else:
        st = 0
        ans += 1
    nna = []
    for i in range(st, len(na)):
        if na[i] % na[0] > 0:
            nna.append(na[i])
    na = nna
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = sorted(list(map(int, input().split())))
m = max(a)+1

numbers = [0] * m

for i in a:
    numbers[i] += 1

    if numbers[i] == 1:
        for j in range(2*i, m, i):
            numbers[j] += 2

print(numbers.count(1))
### BUGGY CODE ###

x,k,d = map(int,input().split())

if abs(x)//d <= k :
  z = k - (abs(x)//d)
  x = abs(x)%d
  if z % 2 == 0:
    print(x)
    exit()
  else:
    if abs(x) + d <= abs(abs(x) - d):
      print(abs(x)+d)
      exit()
    else:
      print(abs(abs(x)-d))
      exit()
      
else:
  for i in range(1,k+1):
    if abs(x) >= abs(abs(x) - d):
      x = abs(x) - d
    else:
      if (k-i-1)%2 == 0:
        print(abs(x))
        exit()
      else:
        if abs(x) + d <= abs(abs(x) - d):
          print(abs(x)+d)
          exit()
        else:
          print(abs(abs(x)-d))
          exit()
print(abs(x))

### FIXED CODE ###

x,k,d = map(int,input().split())

if abs(x)//d <= k and k>1000 :
  z = k - (abs(x)//d)
  x = abs(x)%d
  if z % 2 == 0:
    print(x)
    exit()
  else:
    if abs(x) + d <= abs(abs(x) - d):
      print(abs(x)+d)
      exit()
    else:
      print(abs(abs(x)-d))
      exit()
elif abs(x)//d > k and k>1000 :
  x = abs(x) - k*d
  print(abs(x))
  exit()
else:
  for i in range(1,k+1):
    if abs(x) >= abs(abs(x) - d):
      x = abs(x) - d
    else:
      if (k-i-1)%2 == 0:
        print(abs(x))
        exit()
      else:
        if abs(x) + d <= abs(abs(x) - d):
          print(abs(x)+d)
          exit()
        else:
          print(abs(abs(x)-d))
          exit()
print(abs(x))
### BUGGY CODE ###

r,g,b,n=map(int,input().split())
ans=0
for i in range(3001):
	for j in range(3001):
		if (n-r*i-g*j)%b==0 and \
		n-r*i-g*j>=0:
			ans+=1
print(ans)

### FIXED CODE ###

r,g,b,n=map(int,input().split())
ans=0
for i in range(3001):
	for j in range(3001):
		if (n-r*i-g*j)%b==0 and \
		n-r*i-g*j>=0:
			ans+=1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
N, K = map(int, input().split())
h = np.array(input().split(), dtype=np.int64)
h = np.append(h, [0]*K)

dp = np.full(N+K, np.inf)
dp[0] = 0

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

print(int(dp[N-1]))

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
for j in range(K):
    h.append(0)
INF = float('inf')
dp = [INF] * (N+K)
dp[0] = 0

for i in range(N):
    for j in range(1, K+1):
        dp[i+j] = min(dp[i+j], dp[i] + abs(h[i]-h[i+j]))
print(dp[N-1])
### BUGGY CODE ###

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

comb = len(a) * (len(a) - 1) / 2
comb = int(comb)

sum = 0

for i in range(comb):
    #print(a)
    for i in range(1, len(a)):
        #print(a[i])
        sum = sum + a[0] * a[i]
    a = a[1:]
    #print(a)

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

### FIXED CODE ###

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

su = sum(a)
sus = 0

for i in a:
    su = su - i
    sus = sus + i * su

print(sus % (10**9 + 7))
### BUGGY CODE ###

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

import collections
import sys
input = sys.stdin.readline


def main():
    n = int(input())
    s = [None] * n
    for i in range(n):
        s[i] = str(input()).replace("\n", "")

    ans = [None] * n
    index = 0
    for i in s:
        count_word = dict()
        sorted_word = list()
        for j in i:
            if not j in sorted_word:
                count_word[j] = i.count(j)
                sorted_word.append(j)

        ans[index] = count_word
        index += 1

    pairs = 0
    sorted_num = list()
    for i in range(n):
        if i in sorted_num:
            continue
        count = 0
        for j in range(i + 1, n):
            if ans[i] == ans[j]:
                sorted_num.append(j)
                count += 1
        if count >= 2:
            pairs += int(count * (count - 1) / 2) + count
        else:
            pairs += count

    print(pairs)


if __name__ == '__main__':
    main()


### FIXED CODE ###

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

import sys
input = sys.stdin.readline


def main():
    n = int(input())
    s = [None] * n
    for i in range(n):
        s[i] = str(input()).replace("\n", "")

    ans = dict()
    pairs = 0
    for i in s:
        i = ''.join(sorted(list(i)))

        if i in ans:
            pairs += ans[i]
            ans[i] += 1
            continue

        ans[i] = 1

    print(pairs)


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

from collections import deque, defaultdict
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(M)]
Q = int(input())
vdc = [list(map(int,input().split())) for i in range(Q)]

g = defaultdict(set)
for a,b in ab:
    g[a].add(b)
    g[b].add(a)

ans = [0]*(N+1)
colored = [False]*(N+1)

for v,d,c in vdc[::-1]:
    visited = [False]*(N+1)
    visited[v] = True
    vs = [v]
    if ans[v] == 0:
        ans[v] = c 
    for i in range(d):
        temp = []
        for pv in vs:
            for nv in g[pv]:
                if not visited[nv]:
                    visited[nv] = True
                    if ans[nv] == 0:
                        ans[nv] = c
                    temp.append(nv)
        vs = temp

for a in ans[1:]:
    print(a)






### FIXED CODE ###

from collections import deque, defaultdict
import sys
input = sys.stdin.readline
N,M = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(M)]
Q = int(input())
vdc = [list(map(int,input().split())) for i in range(Q)]
g = defaultdict(set)

for a,b in ab:
    g[a].add(b)
    g[b].add(a)
'''
from random import randint as ri
import networkx as nx
N,M = 10**5,10**5
g = nx.gnm_random_graph(N,M)
g = nx.to_dict_of_lists(g)
g = {v+1:[nv+1 for nv in g[v]] for v in g}
Q = 20**3
vdc = [[ri(1,N),ri(0,10),ri(1,10**5)] for i in range(Q)]
'''

def dpinit(ps, val=0):
    import copy
    res = [val for i in [0]*ps[-1]]
    for i in ps[:-1][::-1]:
        res = [copy.deepcopy(res) for k in [0]*i]
    return res

ans = [0]*(N+1)
visited = dpinit([N+1,11],False)

for v,d,c in vdc[::-1]:
    if visited[v][d]:
        continue
    for t in range(d+1):
        visited[v][t] = True
    if ans[v] == 0:
        ans[v] = c 
    vs = [v]
    for i in range(d-1,-1,-1):
        temp = []
        for pv in vs:
            for nv in g[pv]:
                if not visited[nv][i]:
                    for t in range(i+1):
                        visited[nv][t] = True
                    if ans[nv] == 0:
                        ans[nv] = c
                    temp.append(nv)
        vs = temp
 
for a in ans[1:]:
    print(a)