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

N,M = map(int, input().split())
citys = [list(map(int,input().split()))+[i] for i in range(M)]

citys.sort(key=lambda x: (x[0],x[1]))
states = []
for s in range(N):
    temp = list(filter(lambda x:x[0]==s+1,citys))
    states += [city+[i+1] for i,city in enumerate(temp)]

states.sort(key=lambda x: x[2])

def zero6(n):
    return ('0'*6+str(n))[-6:]

for city in states:
    print(zero6(city[0])+zero6(city[3]))

### FIXED CODE ###

N,M = map(int, input().split())
citys = [list(map(int,input().split()))+[i] for i in range(M)]

citys.sort(key = lambda x:x[1])
nums = [0]*(N+1)
states = [None]*M

for p,y,i in citys:
    nums[p] += 1
    states[i] = [str(p), str(nums[p])]

for s in states:
    print(s[0].zfill(6)+s[1].zfill(6))
### BUGGY CODE ###

import sys
from math import sqrt
input = sys.stdin.readline
N = int(input())
ps = [tuple(map(int, input().split())) for _ in range(N)]
rang = 0
for t in ps:
  rang = max(rang, abs(t[0]), abs(t[1]))
def calc(x, y):
  res = 0
  for t in ps:
    u, v = t
    res = max(res, sqrt((x - u) ** 2 + (y - v) ** 2))
  return res

x0 = -1000
x3 = 1000
x1 = (x0 * 2 + x3) / 3
x2 = (x0 + x3 * 2) / 3
res = float("inf")
xl = 0
yl = 0
for i in range(0, rang * 2 + 1, 10):
  u = i - rang
  for j in range(0, rang * 2 + 1, 10):
    v = j - rang
    if calc(xl, yl) > calc(u, v):
      xl = u
      yl = v
x0 = xl - 10
x3 = xl + 10
while x3 - x0 > 0.1 ** 12:
  x1 = (x0 * 2 + x3) / 3
  x2 = (x0 + x3 * 2) / 3

  cc1 = 0
  cc2 = 0

  y0 = yl - 10
  y3 = yl + 10
  y1 = (y0 * 2 + y3) / 3
  y2 = (y0 + y3 * 2) / 3

  while y3 - y0 > 0.1 ** 12:
    y1 = (y0 * 2 + y3) / 3
    y2 = (y0 + y3 * 2) / 3
    c1 = calc(x1, y1)
    c2 = calc(x1, y2)
    if c1 < c2: y3 = y2
    else: y0 = y1

  cy1 = y1 + 0

  y0 = yl - 10
  y3 = yl + 10
  y1 = (y0 * 2 + y3) / 3
  y2 = (y0 + y3 * 2) / 3

  while y3 - y0 > 0.1 ** 12:
    y1 = (y0 * 2 + y3) / 3
    y2 = (y0 + y3 * 2) / 3
    c1 = calc(x2, y1)
    c2 = calc(x2, y2)
    if c1 < c2: y3 = y2
    else: y0 = y1

  cy2 = y1 + 0

  cc1 = calc(x1, cy1)
  cc2 = calc(x2, cy2)
  if cc1 < cc2: x3 = x2
  else: x0 = x1
  res = min(cc1, cc2)

print(res)

### FIXED CODE ###

import sys
from math import sqrt
input = sys.stdin.readline
N = int(input())
ps = [tuple(map(int, input().split())) for _ in range(N)]
rang = 0
for t in ps:
  rang = max(rang, abs(t[0]), abs(t[1]))
def calc(x, y):
  res = 0
  for t in ps:
    u, v = t
    res = max(res, sqrt((x - u) ** 2 + (y - v) ** 2))
  return res

x0 = -1000
x3 = 1000
x1 = (x0 * 2 + x3) / 3
x2 = (x0 + x3 * 2) / 3
res = float("inf")
xl = 0
yl = 0
for i in range(0, rang * 2 + 1, 10):
  u = i - rang
  for j in range(0, rang * 2 + 1, 10):
    v = j - rang
    if calc(xl, yl) > calc(u, v):
      xl = u
      yl = v
x0 = xl - 10
x3 = xl + 10
while x3 - x0 > 0.1 ** 12:
  x1 = (x0 * 2 + x3) / 3
  x2 = (x0 + x3 * 2) / 3

  cc1 = 0
  cc2 = 0

  y0 = yl - 10
  y3 = yl + 10
  y1 = (y0 * 2 + y3) / 3
  y2 = (y0 + y3 * 2) / 3

  while y3 - y0 > 0.1 ** 12:
    y1 = (y0 * 2 + y3) / 3
    y2 = (y0 + y3 * 2) / 3
    c1 = calc(x1, y1)
    c2 = calc(x1, y2)
    if c1 < c2: y3 = y2
    else: y0 = y1

  cy1 = y1 + 0

  y0 = yl - 10
  y3 = yl + 10
  y1 = (y0 * 2 + y3) / 3
  y2 = (y0 + y3 * 2) / 3

  while y3 - y0 > 0.1 ** 12:
    y1 = (y0 * 2 + y3) / 3
    y2 = (y0 + y3 * 2) / 3
    c1 = calc(x2, y1)
    c2 = calc(x2, y2)
    if c1 < c2: y3 = y2
    else: y0 = y1

  cy2 = y1 + 0

  cc1 = calc(x1, cy1)
  cc2 = calc(x2, cy2)
  if cc1 < cc2: x3 = x2
  else: x0 = x1
  res = min(cc1, cc2)

print(res)
### BUGGY CODE ###

MODINT = 1000000007
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]
        ans %= MODINT
print(ans)


### FIXED CODE ###

MODINT = 1000000007
n = int(input())
A = list(map(int,input().split()))
prodsum = [0]*n
prodsum[0] = A[0]
for i in range(1,n):
    prodsum[i] = prodsum[i-1]+A[i]
# print(prodsum)
ans = 0
for i in range(n-1):
    ans += A[i]*(prodsum[-1]-prodsum[i])
print(ans%MODINT)
### BUGGY CODE ###

def main():
    N,X,M = map(int,input().split())
    A = X
    ans = A
    LIST = [A]
    C = 0
    flag = False
    for n in range(N-1):
        A = (A**2)%M
        if A in LIST:
            ind = LIST.index(A)
            C = sum(LIST[:ind])
            LIST = LIST[ind:]
            flag = True
            break
        else:
            LIST.append(A)
        ans += A
    else:
        print(ans)
        
    if flag:
        ANS = [0]
        S = 0
        for L in LIST:
            S += L
            ANS.append(S)
            
        a = (N - ind) // len(LIST)
        b = (N - ind) % len(LIST)
        ans = sum(LIST)*a + ANS[b] + C
        
        print(ans)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N,X,M = map(int,input().split())
    A = X
    ans = A
    LIST = [A]
    C = 0
    flag = False
    for n in range(N-1):
        A = (A**2)%M
        if A in LIST:
            ind = LIST.index(A)
            C = sum(LIST[:ind])
            LIST = LIST[ind:]
            flag = True
            break
        else:
            LIST.append(A)
        ans += A
    else:
        print(ans)
        
    if flag:
        ANS = [0]
        S = 0
        for L in LIST:
            S += L
            ANS.append(S)
            
        a = (N - ind) // len(LIST)
        b = (N - ind) % len(LIST)
        ans = sum(LIST)*a + ANS[b] + C
        
        print(ans)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import math

def searchPrimeNum(N):
    maxV=int(math.sqrt(N))
    searchList=[i for i in range(2, N+1)]
    primeNum=[]
    while searchList[0]<=maxV:
        primeNum.append(searchList[0])
        tmp=searchList[0]
        searchList=[i for i in searchList if i%tmp!=0]
    primeNum.extend(searchList)
    return primeNum

A, B=map(int, input().split())
primeNum=searchPrimeNum(max(A, B)//2+10)
ans=1
for p in primeNum:
    if p*p>min(A, B):
        break
    if A%p==0 and B%p==0:
        ans+=1
print(ans)

### FIXED CODE ###

def make_divisors(n):
  divisors=[]
  for i in range(1, int(n**0.5)+1):
    if n%i==0:
      divisors.append(i)
      if i!=n//i:
        divisors.append(n//i)
  return divisors

def make_cd(x, y):
  div1=make_divisors(x)
  div2=make_divisors(y)
  cd=[]
  for i in div1:
    for j in div2:
      if i==j:
        cd.append(i)
        break
  cd.sort()
  return cd

A, B=map(int, input().split())
if A<B:
  A,B=B,A
cd=make_cd(A, B)
ok=[True for _ in range(len(cd))]
for i in range(1, len(cd)):
  if not ok[i]:
    continue
  for j in range(i+1, len(cd)):
    if cd[j]%cd[i]==0:
      ok[j]=False
print(sum([1 if ok[i] else 0 for i in range(len(cd))]))
### BUGGY CODE ###

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, Ma, Mb, ABC):
    ans = 10**10
    for p in range(1, 1 << N):
        ta, tb, tc = 0, 0, 0
        for i in range(N):
            if p & (1 << i):
                a, b, c = ABC[i]
                ta += a
                tb += b
                tc += c
        if ta * Mb == tb * Ma:
            ans = min(ans, tc)
    if ans == 10**10:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, Ma, Mb = map(int, input().split())
    ABC = [tuple(map(int, input().split())) for _ in range(N)]
    main(N, Ma, Mb, ABC)


### FIXED CODE ###

# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
INF = 10**10
def main(N, Ma, Mb, ABC):
    MX = 10 * N
    dp = [[[INF] * (MX + 1) for _ in range(MX + 1)] for __ in range(N + 1)]
    dp[0][0][0] = 0
    for i in range(N):
        ni = i + 1
        ma, mb, mc = ABC[i]
        for na in range(MX + 1):
            a = na - ma
            for nb in range(MX + 1):
                b = nb - mb
                dp[ni][na][nb] = dp[i][na][nb]
                if a >= 0 and b >= 0:
                    dp[ni][na][nb] = min(dp[ni][na][nb], dp[i][a][b] + mc)

    ans = INF
    for a in range(MX + 1):
        for b in range(MX + 1):
            if a == 0 and b == 0: continue
            if a * Mb == b * Ma:
                ans = min(ans, dp[N][a][b])
    if ans == INF:
        print(-1)
    else:
        print(ans)

if __name__ == '__main__':
    input = sys.stdin.readline
    N, Ma, Mb = map(int, input().split())
    ABC = [tuple(map(int, input().split())) for _ in range(N)]
    main(N, Ma, Mb, ABC)
### BUGGY CODE ###

import sys
n, m = map(int, input().split())
a = []
ans = [0 for _ in range(n)]
for i in range(m):
    a.append(int(input()))
for i in range(m-1):
    if a[i+1]-a[i] == 1:
        print(0)
        sys.exit()
for i in range(n):
    if i+1 in a:
        ans[i] = 0
    else:
        if i == 0:
            ans[i] = 1
        elif i == 1:
            ans[i] = 1+ans[i-1]
        else:
            ans[i] = ans[i-1]+ans[i-2]
print(ans[-1]%(10**9+7))


### FIXED CODE ###

import sys
n, m = map(int, input().split())
a=set(int(input()) for i in range(m))
ans = [0 for _ in range(n)]

for i in range(n):
    if i+1 in a:
        ans[i] = 0
    else:
        if i == 0:
            ans[i] = 1
        elif i == 1:
            ans[i] = 1+ans[i-1]
        else:
            ans[i] = (ans[i-1]+ans[i-2])%(10**9+7)
print(ans[-1])
### BUGGY CODE ###

import math
k=int(input())
s=0
for x in range(1,k+1):
  for y in range(1,k+1):
    for z in range(1,k+1):
      s+=math.gcd(x,math.gcd(y,z))
print(s)

### FIXED CODE ###

import math
k=int(input())
l=[]
s=0
for x in range(1,k+1):
  for y in range(1,k+1):
    l.append(math.gcd(x,y))

for x in range(len(l)):
  for y in range(1,k+1):
    s+=math.gcd(l[x],y)
print(s)
### BUGGY CODE ###

n = int(input())
p = list(map(float , input().split()))

dp = [[0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
    for j in range(n):
        dp[i + 1][j + 1] += dp[i][j] * p[i]
        dp[i + 1][j] += dp[i][j] * (1 - p[i])

ans=0
for i in range(n // 2 + 1, n + 1):
    ans += dp[n][i]
print(ans)

### FIXED CODE ###

n = int(input())
p = list(map(float , input().split()))

dp = [[0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
    for j in range(n):
        dp[i + 1][j + 1] += dp[i][j] * p[i]
        dp[i + 1][j] += dp[i][j] * (1 - p[i])

ans=0
for i in range(n // 2 + 1, n + 1):
    ans += dp[n][i]
print(ans)
### BUGGY CODE ###


N = int(input())
#N,K = map(int, input().split())
dct = {}
for z in range(N):
    x = input()
    if x in dct.keys():
        dct[x] += 1
    else:
        dct[x] = 1
mx = dct[max(dct, key=dct.get)]
ans = []
for key in dct.keys():
    if dct[key] == mx:
        ans.append(key)
ans.sort()
for elem in ans:
    print(elem)


### FIXED CODE ###

N = int(input())
#N,K = map(int, input().split())
dct = {}
mx = 0
for z in range(N):
    x = input()
    try:
        dct[x] += 1
    except:
        dct[x] = 1
    mx = max(mx, dct[x])
keys = list(dct.keys())
ans = []
for key in keys :
    if dct[key] == mx:
        ans.append(key)
ans.sort()
for elem in ans:
    print(elem)
### BUGGY CODE ###

N = int(input())

res = []
for i in range(N) :
  s = input()
  if(s in res) :
    continue
  else :
    res.append(s)
    
    
print(len(res))

### FIXED CODE ###

N = int(input())

mydict = {}

for i in range(N) :
  s = input()
  if(s in mydict) :
    continue
  else :
    mydict[s] = 1
    
    
print(len(mydict))
### BUGGY CODE ###

x = list(map(int, input().split()))
cnt = 0
for i in range(x[0]+1):
  for j in range(x[0]+1):
    for k in range(x[0]+1):
      p = i+j+k
      if p == x[1]:
        cnt += 1
print(cnt)

### FIXED CODE ###

x = list(map(int, input().split()))
cnt = 0
for i in range(x[0]+1):
  for j in range(x[0]+1):
    p = i+j
    if (p <= x[1]) and (x[0]+p) >= x[1]:
      cnt += 1
print(cnt)
### BUGGY CODE ###

L,R = list(map(int,input().split()))
mod_min = L*R % 2019
for i in range(L, R):
    for j in range(i+1, R+1):
        mod = (i * j) % 2019
        if mod < mod_min:
            mod_min = mod
            if mod_min == 0:
                break
print(mod_min)


### FIXED CODE ###

L,R = list(map(int,input().split()))
def main(L,R):
    mod_min = 2019
    if L // mod_min == R // mod_min:
        L %= mod_min
        R %= mod_min
        for i in range(L,R):
            for j in range(i+1, R+1):
                Y = i*j % 2019
                if Y < mod_min:
                    mod_min = Y
    else:
        mod_min = 0
    return mod_min
print(main(L,R))
### BUGGY CODE ###

def comb(n,k,p):
	from math import factorial
	if n<0 or k<0 or n<k: return 0
	if n==0 or k==0: return 1
	a,b,c = factorial(n)%p,factorial(k)%p,factorial(n-k)%p
	return (a*pf(b,p-2,p)*pf(c,p-2,p))%p
def pf(a,b,p):
	if b==0: return 1
	if b%2==0:
		d = pf(a,b//2,p)
		return d**2%p
	if b%2==1: return (a*pf(a,b-1,p))%p
n,a,b,k = (int(i) for i in input().split())
mod,ans = 998244353,0
for i in range(n+1):
	if (k-a*i)%b==0:
		j = (k-a*i)//b
		ans = (ans+comb(n,i,mod)*comb(n,j,mod))%mod
print(ans)

### FIXED CODE ###

n,a,b,k = (int(i) for i in input().split())
mod,ans = 998244353,0
fn,fk = [1]*n,[1]*n
for i in range(n-1): fn[i+1] = (fn[i]*(i+2))%mod
def power(n,k):
	if k==1: return n
	elif k%2==0: return power((n**2)%mod,k//2)
	else: return (n*power(n,k-1))%mod
def comb(n,k):
	if n==0 or k==0 or n==k: return 1
	else: return (((fn[n-1]*fk[n-k-1])%mod)*fk[k-1])%mod
fk[-1] = power(fn[-1],mod-2)
for i in range(2,n+1): fk[-i] = (fk[-i+1]*(n+2-i))%mod
for i in range(n+1):
	if (k-a*i)%b==0 and k-a*i>=0 and (k-a*i)//b<=n:
		j = (k-a*i)//b
		ans = (ans+(comb(n,i)*comb(n,j))%mod)%mod
print(ans)
### BUGGY CODE ###

a, b, x = map(int, input().split())
count=0
for i in range(a, b+1):
    if i%x==0:
        count+=1
print(count)

### FIXED CODE ###

a, b, x = map(int, input().split())

print( b//x - (a-1)//x )
### BUGGY CODE ###

N, K, Q = map(int,input().split())
A_list = [int(input()) for _ in range (Q)]

result_list = []
for idx in range(N):
    result_list.append("Yes" if K - Q + A_list.count(idx+1) > 0 else "No")

for idx in range(N):
    print(result_list[idx])

### FIXED CODE ###

import collections

N, K, Q = map(int,input().split())
A_list = [int(input())-1 for _ in range (Q)]

A_dic = collections.Counter(A_list)

for idx in range(N):
    print("Yes" if K - Q + A_dic[idx] > 0 else "No")
### BUGGY CODE ###

n = int(input())
ps  = [int(elem) for elem in input().split()]

res = []
for i, p in enumerate(ps):
  if ps[:i] == []:
    res.append(p)
  else:
    if res[-1] > p:
      res.append(p)
print(len(res))

### FIXED CODE ###

n = int(input())
ps  = [int(elem) for elem in input().split()]

cnt = 0
for i, p in enumerate(ps):
  if i == 0:
    last = p
    cnt += 1
  else:
    if last > p:
      last = p
      cnt += 1
print(cnt)
### BUGGY CODE ###

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

h, n = map(int, input().split())
a = ["" for _ in range(n)]
b = ["" for _ in range(n)]

for i in range(n):
    a[i], b[i] = map(int, input().split())

inf = 10**12
dp = [[inf for j in range(h+1)] for i in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0
#print("dp", dp)
 
for i in range(n):
    for j in range(1,h+1):
        #print("-"*50)
        #print("i, j", i, j)
        if j <= a[i]:
            #print(str(j)+" <= a["+str(i)+"]", a[i])
            #print("b[i]", b[i])
            #print("dp[i][j]", dp[i][j])
            #print("dp[i+1][j] = min(): ", min(b[i], dp[i][j]))
            dp[i+1][j] = min(b[i], dp[i][j])
            
        else:
            #print(str(j)+" > a["+str(i)+"]", a[i])
            #print("dp[i][j]", dp[i][j])
            #print("dp[i+1][j - a[i]]+b[i]", dp[i+1][j - a[i]]+b[i])
            #print("dp[i+1][j] = min(): ", min(dp[i][j], dp[i+1][j - a[i]]+b[i]))
            dp[i+1][j] = min(dp[i][j], dp[i+1][j - a[i]]+b[i])
    #print(dp)
 
#print(dp)
print(dp[n][h])

### FIXED CODE ###

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

h, n = map(int, input().split())
a = ["" for _ in range(n)]
b = ["" for _ in range(n)]

for i in range(n):
    a[i], b[i] = map(int, input().split())

inf = 10**12
dp = [[inf for j in range(h+1)] for i in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0
#print("dp", dp)
 
for i in range(n):
    for j in range(1,h+1):
        #print("-"*50)
        #print("i, j", i, j)
        if j <= a[i]:
            #print(str(j)+" <= a["+str(i)+"]", a[i])
            #print("b[i]", b[i])
            #print("dp[i][j]", dp[i][j])
            #print("dp[i+1][j] = min(): ", min(b[i], dp[i][j]))
            dp[i+1][j] = min(b[i], dp[i][j])
            
        else:
            #print(str(j)+" > a["+str(i)+"]", a[i])
            #print("dp[i][j]", dp[i][j])
            #print("dp[i+1][j - a[i]]+b[i]", dp[i+1][j - a[i]]+b[i])
            #print("dp[i+1][j] = min(): ", min(dp[i][j], dp[i+1][j - a[i]]+b[i]))
            dp[i+1][j] = min(dp[i][j], dp[i+1][j - a[i]]+b[i])
    #print(dp)
 
#print(dp)
print(dp[n][h])
### BUGGY CODE ###

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

### FIXED CODE ###

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

from operator import mul
from functools import reduce
N=int(input())
A = list(map(int,input().split()))
c=reduce(mul, A)
if c > 10**18:
    print(-1)
else:
    print(c)


### FIXED CODE ###

N=int(input())
A = list(map(int,input().split()))
A.sort()
x=1
y=True
for i in A:
    x= x*i
    if x > 10**18:
        print('-1')
        y=False
        break
if y:
    print(x)
### BUGGY CODE ###

n,q = map(int, input().split())
s =input()
A = [[int(j) for j in input().split()] for i in range(q)]
ls = [0] * (n+1)
for i in range(n-1):
    if s[i] == 'A' and s[i+1] == 'C':
        ls[i]= 1

for k in range(q):
    print(sum(ls[A[k][0]-1:A[k][1]-1]))

### FIXED CODE ###

n,q = map(int, input().split())
s =input()
A = [[int(j) for j in input().split()] for i in range(q)]
ls = [0] * (n+1)
for i in range(n-1):
    if s[i] == 'A' and s[i+1] == 'C':
        ls[i+1]= ls[i]+1
    else:
        ls[i+1]= ls[i]

for k in range(q):
    print(ls[A[k][1]-1]-ls[A[k][0]-1])
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]

ans=[]
for i in a:
    if i in ans:
        ans.remove(i)
    else:
        ans.append(i)

print(len(ans))

### FIXED CODE ###

from collections import Counter

n = int(input())
a = [int(input()) for _ in range(n)]

c = Counter(a)

ans = 0
for key, value in c.most_common():
    if value % 2 != 0:
        ans += 1

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

N, K = map(int, input().split())
h = list(map(int, input().split()))
c = [0]*N
for i in range(1, N):
    c[i] = min([c[j] + abs(h[i]-h[j]) for j in range(max(0, i-K), i)])
print(c[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
c = [0]*N
for i in range(1, N):
    c[i] = min([c[j] + abs(h[i]-h[j]) for j in range(max(0, i-K), i)])
print(c[N-1])
### BUGGY CODE ###

#coding:utf-8
def comb(x):
    return x * (x-1) / 2
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
class aUnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]


    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[x])


    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)
N,M = map(int,input().split())
AB = []
for m in range(M):
    ab = list(map(int,input().split()))
    ab[0] -=1
    ab[1] -=1
    AB.append(ab) 

u = UnionFind(N)
ans = []
for ab in AB[::-1]:
#    print (ab)
    a,b = ab
    c1 = comb(sum(u.find(a) == u.find(i) for i in range(N)))
    c2 = comb(sum(u.find(b) == u.find(i) for i in range(N)))
    u.union(a,b)
    
    c3 = comb(sum(u.find(a) == u.find(i) for i in range(N)))
    ans.append(int(c3-c1-c2))
sum = 0
for i in ans[::-1]:
    if i > 0:
        sum += i
    print (sum)


### FIXED CODE ###

N, M = map(int, input().split())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
 
 
class UnionFind:
    def __init__(self,size):
        self.rank = [-1 for _ in range(size)]
        self.number = [1 for _ in range(size)]
 
    def find(self,x):
        while self.rank[x] >= 0:
            x = self.rank[x]
        return x
 
    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 == s2:
            return
        if self.rank[s1] == self.rank[s2]:
            self.rank[s1] -= 1
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        elif self.rank[s1] < self.rank[s2]:
            self.rank[s2] = s1
            self.number[s1] += self.number[s2]
        else:
            self.rank[s1] = s2
            self.number[s2] += self.number[s1]
 
 
def main():
    uf = UnionFind(N)
    p = N * (N - 1) // 2
    ans = [p]
    for x, y in reversed(ab):
        px = uf.find(x)
        py = uf.find(y)
        if px != py:
            p -= uf.number[px] * uf.number[py]
            uf.union(px, py)
        ans.append(p)
 
    for a in reversed(ans[:-1]):
        print(a)
 
 
main()
### BUGGY CODE ###

N,K,Q=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
a=[]
for q in range(Q):
    a.append(int(input()))

cnt=0
for n in range(N):
    if K - (Q - a.count(n+1)) > 0:    
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

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

a=[]
for q in range(Q):
    a.append(int(input()))

cnt=[0]*N
for q in range(Q):
    cnt[int(a[q])-1]+=1

for n in range(N):
    if K - (Q - cnt[n]) > 0:    
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import bisect
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
a=[int(i) for i in input().split()]
a.sort()

for _ in range(m):
    b=a[-1]
    a.pop()
    bisect.insort(a,b/2)
print(sum( int( i//1) for i in a ))

### FIXED CODE ###

import heapq
n,m=map(int,input().split())
a=[-int(i) for i in input().split()]
heapq.heapify(a)
for i in range(m):
    b=-heapq.heappop(a)
    heapq.heappush(a,-b/2)
print(int( sum(-i//1 for i in a)) )
### BUGGY CODE ###

n,t = [int(i) for i in raw_input().split()]

a = [int(i) for i in raw_input().split()]

good = []

for i in range(len(a)-1):
    good.append(max(a[i+1:])-a[i])

m = max(good)

count = 0

for g in good:
    if g==m:count+=1

print count


### FIXED CODE ###

n,t = [int(i) for i in raw_input().split()]

a = [int(i) for i in raw_input().split()]

good = []

mmm = []

mmm.append(a[n-1])

for i in range(n-1):
    mmm.append(max(mmm[i],a[n-i-2]))

mmm.reverse()

for i in range(len(a)-1):
    good.append(mmm[i+1]-a[i])

m = max(good)

count = 0

for g in good:
    if g==m:count+=1

print count
### BUGGY CODE ###

n = int(input())
num_list = [int(i) for i in input().split()]
ans = 0

for i in range(n-1):
    for j in range(i+1,n):
        ans += num_list[i] * num_list[j]

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

### FIXED CODE ###

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

s = sum(a**2 for a in n_list)
ans = sum(n_list) ** 2 - s

print((ans//2)%(10**9+7))