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

# 色の最大は辺が一番多い頂点
# 各頂点が現在持ってる色を覚える -> 2次元配列 : color_num = [[]*N]
# 答えを出力するための部分 -> 2次元配列 : ans = [[] * N for _ in range(N)]
# 答えの出し方はN-1ループでa[i], b[i]をansにいれる

from collections import deque
N = int(input())
graph = [[] * N for _ in range(N)]
A = [0] * (N-1)
B = [0] * (N-1)
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    A[i] = a
    B[i] = b

K = 0
for i in range(N):
    K = max(len(graph[i]), K)

# BFSのためのデータ構造
que = deque()
dist = [False] * N

# 初期条件
que.append(0)
color_num = [[0] * N for _ in range(N)]
dist[0] = True
# BFS開始
while que:
    v = que[0]
    que.popleft()
    tmp = 0
    for new_v in graph[v]:
        if dist[new_v]:
            continue
        # 新たな頂点 new_vについて距離情報を更新してキューを追加する
        dist[new_v] = True
        que.append(new_v)
        # 色を塗る
        for k in range(tmp+1, K+1):
            if k in color_num[v]:
                continue
            if k in color_num[new_v]:
                continue
            else:
                color_num[v][new_v] = k
                color_num[new_v][v] = k
                tmp = k
                break

# 答えの出力
print(K)
for i in range(N-1):
    print(color_num[A[i]][B[i]])

### FIXED CODE ###

#幅優先探索
from collections import deque
d=deque()
e=deque()
import sys
sys.setrecursionlimit(1000000000)
n=int(input())
start_node=0
querie=[]
edge={i:[]for i in range(1,n+1)}
for j in range(n-1):
    a,b=map(int,input().split())
    querie.append((a,b))
    edge[a].append(b)
    edge[b].append(a)
    if j==0:
        start_node=a  

d.append((start_node,0))

#はじめにdequeに入れておいて幅優先探索を行うものを決める。そして、塗り分けの結果はans_dictに保存する
#print(edge) 
ans_dict={i:{}for i in range(1,n+1)}
K=0
for some in edge.values():
    K=max(K,len(some))
    
#幅優先探索に使用する すでに訪れたか確認するためのリスト

visited=[False for i in range(n+1)]
visited[start_node]=True

#使う頂点の数を記録した
#nodeをリスト型にしたリストを返す
#start_nodeを記録しておく
def determine_edge_color(node,color):
    new_color=0
    for some in edge[node]:
        if visited[some]==False:
            visited[some]=True
            new_color+=1
            if new_color==color:
                new_color+=1
                ans_dict[node][some]=new_color
                ans_dict[some][node]=new_color
                e.append((some,new_color))
            else:
                ans_dict[node][some]=new_color
                ans_dict[some][node]=new_color
                e.append((some,new_color))
        else:
            pass
            
while d:
    for some in d:
        if visited[some[0]]==True:
            determine_edge_color(some[0],some[1])
        else:
            determine_edge_color(some[1],some[0])
    d=e
    e=deque()
    
#ans_dictの完成
print(K)
#答えの出力
for item in querie:
    a,b=item[0],item[1]
    print(ans_dict[a][b])
### BUGGY CODE ###

import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, K = il()
    A = il()

    tmp = 0
    for k in range(K, N + 1):
        ret = 1
        for a in A[k - K:k]:
            ret *= a

        if tmp != 0 and tmp < ret:
            print('Yes')
        elif tmp != 0 and tmp >= ret:
            print('No')

        tmp = ret


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, K = il()
    A = il()

    for k in range(K, N):
        if A[k - K] < A[k]:
            print('Yes')
        else:
            print('No')


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

A,B, K=map(int,input().split())
List_A = list(map(int, input().split()))
List_B = list(map(int, input().split()))
res = 0
a=0
b=0
inter = 0
n = max(A, B)
for i in range(n):
  if len(List_A)==0 and len(List_B)==0:
    break
  elif len(List_A)==0 and len(List_B)!=0:
    inter+=List_B.pop(0)
    if K < inter:
      break
    res +=1
  elif len(List_A) !=0 and len(List_B)==0:
    inter+=List_A.pop(0)
    if K < inter:
      break
    res +=1
  else:
    a = List_A.pop(0)
    b = List_B.pop(0)
    inter = inter + a+b
    if K < inter: 
      inter = inter -a
      if K < inter:
        inter = inter +a-b
        if K < inter:
          break
        else:
          res +=1
      else:
        res +=1
    else:
      res +=2
print(res)

### FIXED CODE ###

A,B,K=map(int,input().split())
List_A = list(map(int, input().split()))
List_B = list(map(int, input().split()))
SumListA=[]
SumListA.append(0)
SumListB=[]
SumListB.append(0)
res =0
a=0
for i in range(A):
  SumListA.append(SumListA[i]+List_A[i])
for i in range(B):
  SumListB.append(SumListB[i]+List_B[i])

j=B
for i in range(A+1):
  if SumListA[i] > K:
    break
  while K-SumListA[i] < SumListB[j]:
    j += -1
  res = max(i+j,res)
print(res)
### BUGGY CODE ###

import statistics
from collections import deque

d = deque()

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

#print(d)

for i in range(a):
  b = d.pop(0)
  print(statistics.median(d))
  d.append(b)
#  print(d)

### FIXED CODE ###

import copy

a = int(input())
l = list(map(int, input().split()))
l2 = sorted(copy.deepcopy(l))

#print(l2)

for i in l:
  if i < l2[a//2]:
    print(l2[a//2])
  else:
    print(l2[a//2 - 1])
### BUGGY CODE ###

import numpy as np
import sys

H,W,A,B = map(int,input().split())

if H//2 < B or W//2 < A:
    print("No")
    sys.exit()

ans = np.zeros([H,W],dtype = int)
ans[0:B,0:A]=1
ans[B:,A:]=1
for i in range(H):
    S = ans[i,:]
    ans2=''
    for s in S:
         ans2 = ans2 + str(s)
    print(ans2)


### FIXED CODE ###

import sys

H,W,A,B = map(int,input().split())

if H//2 < B or W//2 < A:
    print("No")
    sys.exit()

ans1 = ''
ans2 = ''
for i in range(W):
    if i < A:
        ans1 = ans1 + '1'
        ans2 = ans2 + '0'
    else:
        ans1 = ans1 + '0'
        ans2 = ans2 + '1'

for _ in range(B):print(ans1)
for _ in range(H-B):print(ans2)
### BUGGY CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for i in range(Q)]
for i in range(1, N + 1):
    if A.count(i) > Q - K:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

N, K, Q = map(int, input().split())
A = [0] * N
for i in range(Q):
    A[int(input()) - 1] += 1 
for i in range(N):
    if A[i] > Q - K:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

limit=10**18
n=int(input())
A=list(map(int,input().split()))
ans=1
for a in A:
  ans*=a
print(ans if ans<=limit else -1)

### FIXED CODE ###

limit=10**18
n=int(input())
A=list(map(int,input().split()))
ans=1
if 0 in A:
  ans=0
else:
  for a in A:
    ans*=a
    if ans > limit:
      ans=-1
      break
print(ans)
### BUGGY CODE ###

import sys
n, k = map(int, input().split())
A = list(map(int, input().split()))
C = [n for i in range(n)]
for r in range(k):
    B = [0 for i in range(n+1)]
    for i in range(n):    
        d_min = max(0, i - A[i])
        d_max = min(n, i + A[i] + 1)
        B[d_min] += 1
        B[d_max] -= 1
        # print(d_min, d_max, B)
    t = 0
    flag = True
    for i in range(n):
        t += B[i]
        #if A[i] != t:
        #    flag = False
        A[i] = t
    #if flag:
    #    break
    if A == C:
        break
    # print(A, B)

print(' '.join(map(str, A)))

### FIXED CODE ###

# 東京海上日動 プログラミングコンテスト2020 C
import numpy as np
from numba import njit
n, k = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=np.int64)

@njit
def imos(n, A):
    B = np.zeros(n+1, dtype=np.int64)
    for i in range(n):
        left = max(0, i - A[i])
        right = min(n, i + A[i] + 1)
        B[left] += 1
        B[right] -= 1
    B = np.cumsum(B)
    return B[:-1]

def solve(n,k,A):
    for i in range(k):
        A = imos(n, A)
        min_A = min(A)
        if min_A == n:
            return A
    return A

ANS = solve(n, k, A)
print(' '.join(map(str, ANS)))
### BUGGY CODE ###

N, K = map(int, input().split())
a = list(map(int, input().split()))
l = set(a)
bucket = sorted([a.count(i) for i in l])
print(sum(bucket[0:len(bucket) - K:] + [0]))

### FIXED CODE ###

from collections import Counter
N, K = map(int, input().split())
a = Counter(list(map(int, input().split())))
if N == K:
    print(0)
else:
    num = list(a.values())
    if len(num) <= K:
        print(0)
    else:
        print(sum(sorted(num)[:-K]))
### BUGGY CODE ###

from collections import defaultdict, deque


N = int(input())
d = defaultdict(int)
for i in range(N):
    d[i+1] = int(input())

#print(d)

q = []
q.append(1)

point = 1
count = 1

while True:
    if d[point] in q:
        print(-1)
        break
    elif d[point] == 2:
        print(count)
        break
        
    q.append(d[point])
    point = d[point]
    count += 1

### FIXED CODE ###

from collections import defaultdict, deque
import sys

N = int(input())
d = defaultdict(int)
for i in range(N):
    d[i+1] = int(input())

#print(d)

q = deque()
q.append(1)

point = 1
count = 1

while N > 0:
    if d[point] == 2:
        print(count)
        sys.exit()
        
    q.append(d[point])
    point = d[point]
    count += 1
    N -= 1

print(-1)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

def main():
    n = int(input())
    v = list(map(int, input().split()))
    c = list(map(int, input().split()))
    ans = 0
    
    for i in range(2**n):
        value, cost = 0, 0
        for j in range(n):
            if i >> j & 1:
                value += v[j]
                cost += c[j]
        ans = max(ans, value - cost)
    print(ans)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

def main():
    n = int(input())
    v = list(map(int, input().split()))
    c = list(map(int, input().split()))
    ans = 0
    for i in range(n):
        if v[i] > c[i]:
            ans += v[i] - c[i]
    print(ans)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import math
n, k = map(int, input().split())
aas = list(map(int, input().split()))
left = 1
right = 10**9
def judge(mid):
    cut = 0
    for i in aas:
        cut += math.ceil(i / mid) - 1
    if cut <= k:
        return True
    else:
        return False
while left < right:
    mid = (left + right) / 2
    if math.ceil(left) == math.ceil(right):
        break
    elif judge(mid):
        right = mid
    else:
        left = mid
print(math.ceil(left))

### FIXED CODE ###

import math
n, k = map(int, input().split())
aas = list(map(int, input().split()))
diff = pow(10,-6)
left = 1
right = 10**9
def judge(mid):
    cut = 0
    for i in aas:
        cut += math.ceil(i / mid) - 1
    if cut <= k:
        return True
    else:
        return False
while left < right:
    mid = (left + right) / 2
    if (left <= right <= left + diff) or (right <= left <= right + diff):
        break
    elif judge(mid):
        right = mid
    else:
        left = mid
print(math.ceil(left))
### BUGGY CODE ###

import math
N = int(input())
def f(n):
    count=0
    for x in range(1,int(math.sqrt(n))):
        for y in range(1,int(math.sqrt(n))):
            for z in range(1,int(math.sqrt(n))):
                if x*x+y*y+z*z+x*y+y*z+z*x==n:
                    count +=1
    print(count)

for i in range(1,N+1):
    f(i)

### FIXED CODE ###

a=[0]*int(input())
r=range(1,99)
for x in r:
    for y in r:
        for z in r:
            n=x*(x+y+z)+y*(y+z)+z*z-1
            if n<len(a):
                a[n]+=1
print(*a)
### BUGGY CODE ###

import itertools
X, Y, Z, K = map(int, input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]

D = []
for a, b in itertools.product(A, B):
    d = a + b
    D.append(d)

E = []
for c, d in itertools.product(C, D):
    e = c + d
    E.append(e)
    
E.sort(reverse = True)
for e in E[:K]:
    print(e)

### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = sorted([int(i) for i in input().split()], reverse = True)
B = sorted([int(i) for i in input().split()], reverse = True)
C = sorted([int(i) for i in input().split()], reverse = True)

D = []
for i in range(X):
    for j in range(Y):
        if (i + 1) * (j + 1) > K:
            break
        for k in range(Z):
            if (i + 1) * (j + 1) * (k + 1) > K:
                break
            D.append(A[i] + B[j] + C[k])
            #print(A[i] + B[j] + C[k], i, j, k)
            
D.sort(reverse = True)
for d in D[:K]:
    print(d)
### BUGGY CODE ###

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

if '0' in a:
    s = 0
else:
    for i in range(n):
        s = s * a[i]
    if s > 10 ** 18:
        s = -1
print(s)

### FIXED CODE ###

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

if 0 in a:
    s = 0
else:
    for i in range(n):
        s = s * a[i]
        if s > 10 ** 18:
            s = -1
            break
print(s)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

instr = input()
target = int(input())

# 部分文字列の一覧リストを作成
str_list = []
for i in range(len(instr)):

	for j in range(len(instr)+1):
		
		# 開始位置iの方が大きいものはやる必要がないのでjを増やす
		if i >= j:
			j = i + 1
		
		# targetよりも大きい文字数のものは処理しない
		if j-i > target:
			break

		# 候補となる部分文字列の格納
		str_list.append(instr[i:j])
		j += 1
	i += 1

# 重複削除
str_list = list(set(str_list))
# 昇順ソート
str_list.sort()

print(str_list[target-1])

### FIXED CODE ###

# -*- coding: utf-8 -*-

instr = input()
target = int(input())

# 部分文字列の一覧リストを作成
str_list = []
for i in range(len(instr)):

	for j in range(i, len(instr)+1):
		
		# targetよりも大きい文字数のものは処理しない
		if j-i > target:
			break

		# 候補となる部分文字列の格納
		if i < j:
			str_list.append(instr[i:j])

		j += 1
	i += 1

# 重複削除
str_list = list(set(str_list))
# 昇順ソート
str_list.sort()

print(str_list[target-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
if True:
    n = int(input())
    an= list(map(int, input().split()))

else:
   # n=5
   # an=[1,1,2,1,2]
    n=8
    an=[1,2,1,4,2,1,4,1]


for k in range(0,n):
    an2 = an[:]
    del an2[k]
    an2.sort()
    # print(an2)
    before = ""
    ans = 0
    same_count = 0
    for a in an2:
        if a == before:
            same_count += 1
        elif same_count > 0:
            # print(same_count)
            ans += same_count * (same_count+1)/2
            same_count = 0
        before = a
    if same_count > 0:
        ans += same_count * int((same_count+1)/2)
    print(int(ans))
    an2.clear()



### FIXED CODE ###

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

datas = [0] * (n+1)
for a in an:
    datas[a] += 1

ans = 0
for i in range(1,n+1):
    if datas[i] > 1:
        ans += datas[i] * (datas[i]-1)/2
ans = int(ans)

for k in range(0,n):
    if datas[an[k]] > 1:
        print(int(ans - datas[an[k]] * (datas[an[k]]-1)/2 + (datas[an[k]]-1) * (datas[an[k]]-2)/2))
    else:
        print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n,q = map(int,input().split())
tree = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

ans = [0 for _ in range(n)]
for _ in range(q):
    p,x = map(int,input().split())
    p -= 1
    ans[p] += x

#入力

def dfs(pre,now,w):
    ans[now] += w
    for i in tree[now]:
        if i != pre:
            dfs(now,i,ans[now])

dfs(-1,0,0)

print(*ans)

### FIXED CODE ###

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

ans = [0 for i in range(n)]
for i in range(q):
    p,x = map(int,input().split())
    p -= 1
    ans[p] += x

#入力

stack = [0]
while len(stack) > 0:
    now = stack.pop()
    for i in tree[now]:
        ans[i] += ans[now]
        stack.append(i)

for i in range(n):
    print(ans[i],end=" ")
print()
### BUGGY CODE ###

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

knap = [0 for i in range(W+1)]
mono = []

for i in range(N):
    w,v = map(int, input().split())
    mono.append([w,v])
mono.sort(key = lambda x:x[1], reverse=True)
for w, v in mono:
    for i in range(w, W+1)[::-1]:
        if knap[i] < knap[i-w] + v:
            knap[i] = knap[i-w] + v
print(knap[W])


### FIXED CODE ###

from itertools import accumulate
n,w=map(int, input().split())
items = {}
for _ in range(n):
    u,v = map(int, input().split())
    if u not in items:
        items[u] = []
    items[u].append(v)
cost = 0
acc = []
minkey = min(items.keys())
for i in range(4):
    if minkey + i in items:
        items[minkey + i].sort(reverse=True)
        acc.append([0] + list(accumulate(items[minkey + i])))
    else:
        acc.append([0])

ans = 0
for i in range(len(acc[0])):
    a = (i) * minkey
    if w < a:
        continue
    for j in range(len(acc[1])):
        b = (j) * (minkey+1)
        if w < a + b:
            continue
        for k in range(len(acc[2])):
            c = (k) * (minkey+2)
            if w < a + b + c:
                continue
            for l in range(len(acc[3])):
                d = (l) * (minkey+3)
                if w < a + b + c + d:
                    continue
                cost = acc[0][i] + acc[1][j] + acc[2][k] + acc[3][l]
                if cost > ans :
                    ans = cost

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

n = int(input())
re =1

list = [int(s) for s in input().split()]

for i in list:
    re *= i
    
if(re > 1000000000000000000):
    print("-1")
else:
    print(re)

### FIXED CODE ###

n =int(input())
limit = 10**18
re =1
 
l = list(map(int, input().split()))
 
l.sort()
#print(l)
if(l[0] == 0):
    re = 0
else:
  for i in l:
    re *= i
    #print(re)
    if(re > limit):
      re = -1
      break
print(re)
### BUGGY CODE ###

S = input()
Q = int(input())
a = 0
b = 0
for i in range(Q):
  q = list(input().split())
  if q[0] == '1':
    b += 1
    
  elif (q[1] == '1' and b%2 == 0) or (q[1] == '2' and b%2 == 1):
    S= q[2]+S
    
    
  else:
    S = S+q[2]
    
if b%2 == 1 and len(S) > 1:
  S = S[::-1]
    

print(S)

### FIXED CODE ###

S = list(input())
Q = int(input())
a = 0
A = []
B = []
for i in range(Q):
  q = list(input().split())
  q[0] = int(q[0])
  if q[0] == 1:
    if a == 0:
      a = 1
    else:
      a = 0
  else:
    q[1] = int(q[1])
    if (q[1] == 1 and a == 0) or (q[1] == 2 and a == 1):
      B.append(q[2])
    else:
      A.append(q[2])
B = B[::-1]
ans = B + S + A
if a == 1:
  ans = ans[::-1]
ans = ''.join(ans)
print(ans)
### BUGGY CODE ###

A, B, K = map(int, input().split())
l = [int(x) for x in range(A, B + 1)]
if 2 * K > B - A + 1:
	for i in l:
		print(i)
else:
	for i in range(A, A + K):
		print(i)
	for j in range(B - K + 1, B + 1):
		print(j)

### FIXED CODE ###

A, B, K = map(int, input().split())
if 2 * K > B - A + 1:
	for i in range(A, B + 1):
		print(i)
else:
	for i in range(A, A + K):
		print(i)
	for j in range(B - K + 1, B + 1):
		print(j)
### BUGGY CODE ###

n=int(input())
L=list(map(int,input().split()))
L.sort()

count=0
list.sort(L, reverse=True)

for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            if L[k]>L[i]-L[j]:
                count += 1

print(count)


### FIXED CODE ###

import bisect

n=int(input())
L=[int(i) for i in input().split()]

L.sort()

s=0
for i in range(n-1):
      for j in range(i+1,n):
            index=bisect.bisect_left(L,L[i]+L[j])
            s+=index-(j+1)
print(s)
### BUGGY CODE ###

import math
num = 100000
s = set([i for i in range(2,num+1)])
p = set()
mi = 0
while mi<=math.sqrt(num):
    mi = min(s)
    t = set([i*mi for i in range(1,num//mi+1)])
    p.add(mi)
    s-=t
p = p|s

q = int(input())
for i in range(q):
    l , r = map(int, input().split())
    s2 = set([i for i in range(l,r+1)])
    s2 = s2 & p
    s3 = set([(i+1)/2 for i in s2])
    s3 = s3 & p
    print(len(s3))

### FIXED CODE ###

import math
num = 100000
s = set([i for i in range(2,num+1)])
p = set()
mi = 0
while mi<=math.sqrt(num):
    mi = min(s)
    t = set([i*mi for i in range(1,num//mi+1)])
    p.add(mi)
    s-=t
p = p|s
p2 = set([i for i in p if (i+1)//2 in p])
c = 0
x = [0]*100001
for i in range(1,num+1):
    if i in p2:
        c+=1
    x[i]=c

q = int(input())
for i in range(q):
    l , r = map(int, input().split())
    ans = x[r]-x[l-1]
    print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
data=[]
for i in range(m):
  a,b=map(int,input().split())
  if a==1:
    if b not in data:
      data.append(b)
    else:
      print('POSSIBLE')
      exit()
  elif b==n:
    if a not in data:
      data.append(a)
    else:
      print('POSSIBLE')
      exit()
print('IMPOSSIBLE')

### FIXED CODE ###

n,m=map(int,input().split())
data=[0]*n
for i in range(m):
  a,b=map(int,input().split())
  if a==1:
    data[b-1]+=1
    if data[b-1]==2:
      print('POSSIBLE')
      exit()
  if b==n:
    data[a-1]+=1
    if data[a-1]==2:
      print('POSSIBLE')
      exit()
print('IMPOSSIBLE')
### BUGGY CODE ###

N,K,Q = [int(x) for x in input().split()]

all_result = []
for a_i in range(Q):
    all_result.append(int(input()))

for num in range(N):
    point = all_result.count(num + 1)
    if (K - Q + point) > 0:
        print('Yes')
    else:
        print('No')



### FIXED CODE ###

import collections

N,K,Q = [int(x) for x in input().split()]

all_result = []
for a_i in range(Q):
    all_result.append(int(input()))

c = collections.Counter(all_result)

for num in range(N):
    point = c[num + 1]
    if (K - Q + point) > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

from itertools import combinations

MOD = 10**9 + 7

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

ans = 0
for x, y in combinations(arr, 2):
    ans += x * y
    ans %= MOD

print(ans)

### FIXED CODE ###

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

MOD = 10**9 + 7

ans = 0
sum_arr = sum(arr)

for x in arr:
    sum_arr -= x
    ans += x * sum_arr
    ans %= MOD

print(ans)