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

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

# 入力
lst = [[0] * (10 ** 5 + 10) for _ in range(C + 1)]
# lst = [[0] * (20) for _ in range(C + 1)]

for _ in range(N):
    s, t, c = map(int, input().split())
    lst[c][s] += 1
    lst[c][t + 1] -= 1

# # 累積和の計算
# import numpy as np
# A = np.array(lst)
# print (A)
# np.cumsum(A, axis = 1, out = A)
# print (A)
# np.cumsum(A, axis = 0)

# print (np.max(A[-1:]))
# print (A)

#番組ごとに毎分必要かどうかを判断する
for i in range(1, C + 1):
    for j in range(1, 10 ** 5 + 10): #いもす法で計算
    # for j in range(1, 20):
        lst[i][j] += lst[i][j - 1]
    for j in range(1, 10 ** 5 + 10): #重なっている時 = 連続して使う時
        lst[i][j] = min(1, lst[i][j])

# for i in lst:
#     print (i[:20])

for j in range(1, 10 ** 5 + 10):
# for j in range(1, 20):
    for i in range(1, C + 1):
        lst[i][j] += lst[i - 1][j]

print (max(lst[-1]))
    
# for i in lst:
#     print (i[:20])

### FIXED CODE ###

# 計算量 O(NC) = O(3 * 10 ** 6)
import sys
input = sys.stdin.readline

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

# 入力
lst = [[0] * (10 ** 5 + 10) for _ in range(C + 1)]

for _ in range(N):
    s, t, c = map(int, input().split())
    lst[c][s] += 1
    lst[c][t + 1] -= 1

#番組ごとに毎分必要かどうかを判断する
for i in range(1, C + 1):
    for j in range(1, 10 ** 5 + 10): #いもす法で計算
        lst[i][j] += lst[i][j - 1]
    for j in range(1, 10 ** 5 + 10): #重なっている時 = 連続して使う時
        lst[i][j] = min(1, lst[i][j])

for j in range(1, 10 ** 5 + 10):
    for i in range(1, C + 1):
        lst[i][j] += lst[i - 1][j]

print (max(lst[-1]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
N , Q = map(int,input().split())
graph = [[] for _ in range(N)]
point = [0] * N
for _ in range(N - 1):
    a , b = map(int,input().split())
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
#print(graph)
for _ in range(Q):
    a , b = map(int,input().split())
    a = a - 1
    point[a] += b

# dfsを用いて累積和を計算する
# 初期状態だと前の値がないためデフォルト引数に-1を代入
def dfs(now , prev = -1):
    for next in graph[now]:
        # 次のノードが前に参照した値の時はcontinue
        if next == prev:
            continue

        # 現在の値を次のポイントに加算することで累積和をとる
        point[next] += point[now]

        # 次のノードと現在のノードを引数にdfsを継続する
        dfs(next , now)

dfs(0)
print(*point)

### FIXED CODE ###

import sys

sys.setrecursionlimit(5 * 10**5)
input=sys.stdin.readline

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

M = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = list(map(int, input().split()))
    M[a-1].append(b-1)
    M[b-1].append(a-1)

ans = [0] * N
for _ in range(Q):
    p, x = list(map(int, input().split()))
    ans[p-1] += x

Q = [0]

while Q:
    current = Q.pop()

    for i in M[current]:
        ans[i] += ans[current]
        M[i].remove(current)

    Q += M[current]

print(' '.join(map(str, ans)))
### BUGGY CODE ###

from pprint import pprint
n = int(input())
a = map(int, input().split())
a = sorted(((ax, x) for x, ax in enumerate(a)), reverse=True)
dp = [[-1] * (n+1) for _ in range(n+1)]
dp[0][0] = 0
for i, (ax, x) in enumerate(a):
    for j in range(i+1):
        dp[j+1][i-j] = max(dp[j+1][i-j], dp[j][i-j] + ax*abs(x-j))
        dp[j][i-j+1] = max(dp[j][i-j+1], dp[j][i-j] + ax*abs(n-1-x-i+j))
# pprint(dp)
print(max(dp[i][n-i] for i in range(n+1)))


### FIXED CODE ###

#  from pprint import pprint
n = int(input())
a = map(int, input().split())
a = sorted(((ax, x) for x, ax in enumerate(a)), reverse=True)
dp = [[-1] * (n+1) for _ in range(n+1)]
dp[0][0] = 0
for i, (ax, x) in enumerate(a):
    for j in range(i+1):
        dp[j+1][i-j] = max(dp[j+1][i-j], dp[j][i-j] + ax*abs(x-j))
        dp[j][i-j+1] = max(dp[j][i-j+1], dp[j][i-j] + ax*abs(n-1-x-i+j))
# pprint(dp)
print(max(dp[i][n-i] for i in range(n+1)))
### BUGGY CODE ###

from pprint import pprint
from collections import deque, defaultdict


def solve(n, q, edges, p):
    # counter = defaultdict(int)
    counter = [0] * n

    parents = deque()
    # parents.append(0)
    # parents = []
    parents.append(0)
    visited = set()
    while parents:
        parent = parents.popleft()
        # parent = parents.pop()
        if parent in visited:
            continue
        visited.add(parent)
        counter[parent] += p[parent]
        # print("parent")
        # print(parent, counter[parent])
        for child in edges[parent]:
            if child in visited:
                continue
            # if counter[child] != 0:
            #    continue
            counter[child] = counter[parent]
            # print("child")
            # print(child, counter[child])
            parents.append(child)
            # parents.add(child)

    #print(" ".join(list(map(str, counter.values()))))
    print(" ".join(list(map(str, counter))))

if __name__ == "__main__":
    n, q = list(map(int, input().strip().split(" ")))
    edges = defaultdict(set)
    for _ in range(n-1):
        a_i, b_i = list(map(int, input().strip().split(" ")))
        # edges[a_i-1].append(b_i-1)
        # edges[b_i-1].append(a_i-1)
        edges[a_i-1].add(b_i-1)
        edges[b_i-1].add(a_i-1)

    # p = defaultdict(int)
    p = [0] * n
    x = []
    for _ in range(q):
        p_i, x_i = list(map(int, input().strip().split(" ")))
        p[p_i-1] += x_i

    solve(n, q, edges, p)

### FIXED CODE ###

from collections import deque


def solve(n, q, a, b, p, x):
    counter = [0] * n
    q_sum = [0] * n
    for i in range(q):
        q_sum[p[i]] += x[i]
    # pprint(q_sum)

    edges = {}
    for i in range(n-1):
        if a[i] not in edges:
            edges[a[i]] = []
        edges[a[i]].append(b[i])
    # pprint(edges)

    counter[0] = q_sum[0]
    children = deque()
    for child in edges[0]:
        counter[child] = q_sum[0]
        children.append(child)
    while children:
        child = children.popleft()
        counter[child] += q_sum[child]
        # print("child")
        # print(child, counter[child])
        if child in edges:
            for c in edges[child]:
                counter[c] = counter[child]
                # print("c")
                # print(c, counter[c])
                children.append(c)

    print(" ".join(list(map(str, counter))))

if __name__ == "__main__":
    n, q = list(map(int, input().strip().split(" ")))
    a = []
    b = []
    for _ in range(n-1):
        a_i, b_i = list(map(int, input().strip().split(" ")))
        a.append(a_i - 1)
        b.append(b_i - 1)

    p = []
    x = []
    for _ in range(q):
        p_i, x_i = list(map(int, input().strip().split(" ")))
        p.append(p_i-1)
        x.append(x_i)
    solve(n, q, a, b, p, x)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, K = map(int, input().split())

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

dots = XY[:]

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            if ans > area:
                ans = area
            
print(ans)


### FIXED CODE ###

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

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
dots = XY[:]

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            if ans > area:
                ans = area
            
print(ans)
### BUGGY CODE ###

num=input().rstrip().split(" ")
num1=int(num[0])
num2=int(num[1])
result=1
list0=[num1]
while result>0:
  result=num1-num2
  if result<0:
    result=-result
    list0.append(result)
    break
  else:
     list0.append(result)
list0=sorted(list0)
print(list0[0])

### FIXED CODE ###

num=input().rstrip().split(" ")
num1=int(num[0])
num2=int(num[1])
if num1%num2==0:
  print(0)
else:
  date0=num1%num2
  date1=num2-date0
  if date0>date1:
    print(date1)
  else:
    print(date0)
### BUGGY CODE ###

h, w = map(int, input().split())
a_array = [input() for x in range(h)]
black = set()
white = set()
for row in range(h):
    for column in range(w):
        if a_array[row][column] == "#":
            black.add((row, column))
        else:
            white.add((row, column))

move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
cnt = 0
next = black.copy()
while not (white <= black):
    tmp = set()
    cnt += 1
    for row, column in next:
        for i, j in move:
            if (row + i, column + j) in black or not (0 <= row + i < h and 0 <= column + j < w):
                continue
            black.add((row + i, column + j))
            tmp.add((row + i, column + j))
    next = tmp.copy()
print(cnt)


### FIXED CODE ###

h, w = map(int, input().split())
a_array = [input() for x in range(h)]
black = [[False for x in range(w)] for y in range(h)]
next = set()
for row in range(h):
    for column in range(w):
        if a_array[row][column] == "#":
            black[row][column] = True
            next.add((row, column))

move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
cnt = 0
while next:
    tmp = set()
    # print(next)
    cnt += 1
    for row, column in next:
        for i, j in move:
            if not (0 <= row + i < h and 0 <= column + j < w) or black[row+i][column+j]:
                continue
            black[row+i][column+j] = True
            tmp.add((row + i, column + j))
    next = tmp
print(cnt-1)
### BUGGY CODE ###

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

B = []
for i in range(1,N+1):
    S = A.count(i)
    B.append((i,int(S)))
B = sorted(B ,key = lambda x : x[1] ,reverse = True)
#print(B)

ans = 0
for i in range(K,N-K):
    ans += B[i][1]
print(ans)

### FIXED CODE ###

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

from collections import Counter
from operator import itemgetter


ac = Counter(a)
aci = list(ac.items())
aci = sorted(aci,key=itemgetter(1),reverse = False)  
#print(aci)

ans = aci[:-k]
cnt=0
for i in range(len(ans)):
    cnt += ans[i][1]
print(cnt)
### BUGGY CODE ###

n, k = map(int, input().split())
A = [*map(int, input().split())]
# print(n,k)
# print(A)

pre = 1
for i in range(k):
    pre *= A[i]


now = pre
for i in range(k,n):
    now *= A[i]
    now /= A[i-k]
    if pre < now:
        print('Yes')
    else:
        print('No')
    pre = now


### FIXED CODE ###

n, k = map(int, input().split())
A = [*map(int, input().split())]
for i in range(k, n):
    if A[i-k] < A[i]: print('Yes')
    else: print('No')
### BUGGY CODE ###

N, M= map(int, input().split())
A = []
B = []
for i in range(N):
    a,b = map(int, input().split())
    A.append(a)
    B.append(b)
count = 0
cost = 0
while count < M:
    pos = A.index(min(A))
    if B[pos] <= M - count:
        count += B[pos]
        cost += A[pos] * B[pos]
        A.pop(pos)
        B.pop(pos)
    else:
        cost += A[pos] * (M - count)
        count = M
        
print(cost)

### FIXED CODE ###

N, M= map(int, input().split())
A = []
for i in range(N):
    a = list(map(int, input().split()))
    A.append(a)
A = sorted(A)
count = 0
cost = 0
i = 0
while count < M:
    cost += A[i][0] * min(A[i][1],M-count)
    count += min(A[i][1],M-count)
    i += 1    
print(cost)
### BUGGY CODE ###

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

checked = [False for _ in range(N)]
ans = 0
for i in range(N):
    if checked[i]:
        continue

    checked[i] = True
    A = G[i]
    tmp = 1
    while len(A) > 0:
        e = A.pop()
        if checked[e]:
            continue
        checked[e] = True
        tmp += 1
        A = A + G[e]

    ans = max(ans, tmp)

print(ans)

### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, v):
        if self.parents[v] < 0:
            return v
        else:
            self.parents[v] = self.find(self.parents[v])
            return self.parents[v]

    def unite(self, u, v):
        u = self.find(u)
        v = self.find(v)

        if u == v:
            return

        if self.parents[u] > self.parents[v]:
            u, v = v, u

        self.parents[u] += self.parents[v]
        self.parents[v] = u

    def size(self, v):
        return -self.parents[self.find(v)]

    def same(self, u, v):
        return self.find(u) == self.find(v)

N, M = map(int, input().split())
uf = UnionFind(N)
for i in range(M):
    a, b = map(int, input().split())
    uf.unite(a-1, b-1)

ans = 0
for i in range(N):
    ans = max(ans, uf.size(i))

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

k, s = [int(i) for i in input().split()]
answer = 0
for x in range(k+1):
  for y in range(k+1):
    for z in range(k+1):
      if x+y+z==s:
        answer += 1
        break

print(answer)

### FIXED CODE ###

k, s = [int(i) for i in input().split()]

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

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

import sys
from collections import deque, defaultdict, Counter
from itertools import accumulate, product, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush
from math import ceil, floor, sqrt, gcd, inf
from copy import deepcopy
import numpy as np
import scipy as sp

def trial_division(n):
    a = []
    f = 2
    while n > 1:
        if n % f == 0:
            a.append(f)
            n /= f
        else:
            f += 1
    return a

INF = inf
MOD = 1000000007

n = int(input())

tmp = 0
res = 0

cnt = Counter(trial_division(n))
for i in cnt.values():
    res += floor((-1 + sqrt(1 + 8 * i)) / 2)

print(res)


### FIXED CODE ###

import numpy as np
import math
import scipy as sp
import queue
import collections

MOD = 10 ** 9 + 7
INF = 10 ** 9

def main(kwargs):
    n = kwargs["n"]
    arr = factorization(n)

    res = 0

    for i in arr:
        res += sankaku(i[1])

    if n == 1:
        res = 0

    return res

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

def sankaku(n):
    res = 1

    while True:
        if res * (res + 1) // 2 <= n < (res + 1) * (res + 2) // 2:
            break

        res += 1

    return res

if __name__ == "__main__":
    kwargs = {}

    cin = input().split()
    kwargs["n"] = [int(i) for i in cin][0]

    cout = main(kwargs)
    print(cout)
### BUGGY CODE ###

import copy
nu = int(input())
data = list(map(int,input().split()))
al = 0
for i in range(nu):
  ta = copy.deepcopy(data)
  da = ta.pop(i)
  for j in range(nu - 2):
    al += abs(ta[j + 1] - ta[j])
  if i == 0:
    al += abs(data[1]) + abs(data[nu - 1])
  elif i == nu - 1:
    al += abs(data[0]) + abs(data[nu - 2])
  else:
    al += abs(data[0]) + abs(data[nu - 1])
  print(al)
  al = 0



### FIXED CODE ###

n = int(input())

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

su = 0
su += abs(a[0])
for i in range(n-1):
    su += abs(a[i+1] - a[i])
su += abs(a[-1])
for i in range(n):
    if i == 0:
        print(su - abs(a[0]) - abs(a[0] - a[1])+ abs(a[1]))
    elif i == n-1:
        print(su - abs(a[-1]) - abs(a[-1] - a[-2]) + abs(a[-2]))
    else:
        print(su - abs(a[i] - a[i-1]) - abs(a[i] - a[i+1]) + abs(a[i+1] - a[i-1]))
### BUGGY CODE ###

a, b, k = map(int, input().split(' '))
ab = [i for i in range(a, b+1)]
#print(ab)
for i in ab:
  if i in ab[k:-k]:
  	continue
  else:
    print(i)

### FIXED CODE ###

a, b, k = map(int, input().split(' '))
if b - a + 1 < 2 * k:
  for i in range(a, b + 1):
    print(i) 
else:
  for i in range(a, a + k):
    print(i)
  for i in range(b - k + 1, b + 1):
    print(i)
### BUGGY CODE ###

def check(a,b):
    if a==b:
        a=-1

A1=list(map(int,input().split()))
A2=list(map(int,input().split()))
A3=list(map(int,input().split()))
N=int(input())

i = 0
j = 0
while i<N:
    b = int(input())
    while j<3:
        check(A1[j],b)
    while j<3:
        check(A2[j],b)
    while j<3:
        check(A3[j],b)

if A1[0]==A1[1]==A1[2] or A2[0]==A2[1]==A2[2] or A3[0]==A3[1]==A3[2] or A1[0]==A2[0]==A3[0] or A1[1]==A2[1]==A3[1] or A1[2]==A2[2]==A3[2] or A1[0]==A2[1]==A3[2] or A1[2]==A2[1]==A3[0]:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

A1=list(map(int,input().split()))
A2=list(map(int,input().split()))
A3=list(map(int,input().split()))
N=int(input())

i = 0
for i in range(N):
    b = int(input())
    j = 0
    while j<3:
        if A1[j]==b:
            A1[j]=-1
        j+=1
    j = 0
    while j<3:
        if A2[j]==b:
            A2[j]=-1
        j+=1
    j = 0
    while j<3:
        if A3[j]==b:
            A3[j]=-1
        j+=1


if A1[0]==A1[1]==A1[2] or A2[0]==A2[1]==A2[2] or A3[0]==A3[1]==A3[2] or A1[0]==A2[0]==A3[0] or A1[1]==A2[1]==A3[1] or A1[2]==A2[2]==A3[2] or A1[0]==A2[1]==A3[2] or A1[2]==A2[1]==A3[0]:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

from itertools import permutations
N, C = map(int, input().split())
D = [list(map(int,input().split())) for _ in range(C)]
c = [list(map(int,input().split())) for _ in range(N)]
acc = [[0]*C for _ in range(3)]
for i in range(N):
    for j in range(N):
        for k in range(C):
            acc[(i+j) % 3][k] += D[c[i][j]-1][k]
ans = float("inf")
for i,j,k in permutations(range(C), r=3):
    ans = min(ans, acc[0][i]+acc[1][j]+acc[2][k])
print(ans)

### FIXED CODE ###

from itertools import permutations
import numpy as np
N, C = map(int, input().split())
D = np.ndarray((C, C), dtype=int)
c = np.ndarray((N, N), dtype=int)
for i in range(C):
    D[i] = list(map(int,input().split()))
for i in range(N):
    c[i] = list(map(int,input().split()))
c -= 1
acc = np.zeros((3, C), dtype=int)
for i in range(N):
    for j in range(N):
        acc[(i+j) % 3] += D[c[i][j]]
ans = float("inf")
for i,j,k in permutations(range(C), r=3):
    ans = min(ans, acc[0][i]+acc[1][j]+acc[2][k])
print(ans)
### BUGGY CODE ###

N = int(input())
As = list(map(int, input().strip().split()))

for i in range(1, N+1):
    num_sub = As.count(i)
    As = [a for a in As if a != i]
    print(num_sub)

### FIXED CODE ###

# coding: utf-8
# Your code here!

N = int(input())
As = list(map(int, input().split()))
ans = [0 for _ in range(N)]
 
for a in As:
    ans[a-1] += 1

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

n = int(input())
def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct

fact = factorize(n)
dif = []
from itertools import combinations as com
for i in range((len(fact) + 1) // 2 + 1):
  for cands in com(fact, i):
    ans = 1
    for cand in cands:
      ans *= cand
    dif.append(n//ans + ans - 2)
print(min(dif))


### FIXED CODE ###

n = int(input())

end = int(n**0.5) + 2
dif = []
for i in range(1, end):
  if n % i == 0:
    dif.append(abs(n//i + i) - 2)
print(min(dif))
### BUGGY CODE ###

# coding: utf-8

def f(n, wv, W):
    dp = [0] * (W + 1)
    for wi, vi in wv:
        for w in range(W, wi - 1, -1):
            dp[w] = max(dp[w], dp[w - wi] + vi)
    return(dp[-1])

n, w = map(int, input().split()) # 1 <= n <= 100, 1 <= w <= 10^5
wv = [[int(x) for x in input().split()] for _ in range(n)]

print(f(n, wv, w))


### FIXED CODE ###

# coding: utf-8
import sys
input = sys.stdin.readline

def f(n, wlimit):
    dp = [-1] * (wlimit + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        wi, vi = map(int, input().rstrip().split())
        dp_ = list(dp)
        for w in range(wlimit + 1):
            if dp[w] >= 0:
                w_ = w + wi
                v_ = dp[w] + vi
                if w_ <= wlimit and dp[w_] < v_:
                    dp_[w_] = v_
        dp = dp_
    return(max(dp))

n, w = map(int, input().rstrip().split()) # 1 <= n <= 100, 1 <= w <= 10^5

print(f(n, w))
### BUGGY CODE ###

A,B = map(int,input().split())
ans = int(0)
for i in range(max(A,B)):
    if (A-i)**2 == (B-i)**2:
        ans = i
if (ans == 0):
    print("IMPOSSIBLE")
else:
    print(ans)

### FIXED CODE ###

A,B = map(int,input().split())
k = (A+B)
if k%2 == 0:
    print(int(k/2))
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
mod = 10 ** 9 + 7


def main():
    ans = 0
    p = []
    for i in range(n):
        for j in range(i + 1, n):
            ans += (a[i] * a[j])% mod
            ans %= mod
            p.append((i, j))
    return ans


n, *a = map(int, read().split())
a = main()
print(a)


### FIXED CODE ###

import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
mod = 10 ** 9 + 7


def main():
    ans = 0
    cs = np.cumsum(np.array(a))
    for i in range(n-1):
        s = (cs[-1] - cs[i]) % mod
        ans = (ans+(a[i]*int(s)) % mod) % mod
    return ans


n, *a = map(int, read().split())
a = main()
print(a)
### BUGGY CODE ###

#python3
from collections import deque
from collections import Counter
from collections import defaultdict
INF = int(1e9)
def main():
    n, x, y = map(int, input().split())
    x-=1
    y-=1
    g = [[] for _ in range(n)]
    for i in range(n-1):
        g[i].append(i+1)
        g[i+1].append(i)
    g[x].append(y)
    g[y].append(x)
    ans = defaultdict(int)
    q = deque()
    pns = []
    for i in range(n):
        #i番目から探索を始める
        #distがkになったときカウントする
        #キューが空になったら次のノードをスタートとして探索する
        dist = [INF for _ in range(n)]
        q.append(i)
        dist[i] = 0
        while len(q):
            node_s = q.popleft() 
            for j in range(len(g[node_s])):
                if dist[g[node_s][j]] != INF:
                    continue
                q.append(g[node_s][j])
                dist[g[node_s][j]] = dist[node_s] + 1
        for k in range(n): 
            pns.append(dist[k])
    
    ans = Counter(pns) 
    for k in range(1, n):
        print(ans[k]//2)
main()

### FIXED CODE ###


from collections import deque
from collections import Counter
from collections import defaultdict
INF = int(1e9)
def main():
    n, x, y = map(int, input().split())
    x-=1
    y-=1
    g = [[] for _ in range(n)]
    for i in range(n-1):
        g[i].append(i+1)
        g[i+1].append(i)
    g[x].append(y)
    g[y].append(x)
    ans = defaultdict(int)
    q = deque()
    pns = []
    for i in range(n):
        dist = [INF for _ in range(n)]
        q.append(i)
        dist[i] = 0
        while len(q):
            node_s = q.popleft() 
            for j in range(len(g[node_s])):
                if dist[g[node_s][j]] != INF:
                    continue
                q.append(g[node_s][j])
                dist[g[node_s][j]] = dist[node_s] + 1
        for k in range(n): 
            pns.append(dist[k])
    
    ans = Counter(pns) 
    for k in range(1, n):
        print(ans[k]//2)
main()
### BUGGY CODE ###

a, b, k = map(int, input().split())
for i in range(a,b+1):
    if i < a + k or i > b - k:
        print(i)

### FIXED CODE ###

a, b, k = map(int, input().split())
ans = set()
for i in range(a,a+k):
    if i <= b:
        ans.add(i)
for i in range(b-k+1,b+1):
    if i >= a:
        ans.add(i)
ans = list(ans)
ans.sort()
for i in range(len(ans)):
    print(ans[i])