Harryxun/stf_run huggingface dataset:
# -*- coding: utf-8 -*-
# 整数の入力
import copy

a = input()
a=int(a)
ball=[]
mydict={}
DPdict={}
temp=input().split(" ")
for i in range(a):
    if not (temp[i] in mydict):
        mydict[temp[i]]=1
    else:
        mydict[temp[i]]+=1
    ball.append(temp[i])

for i in range(len(ball)):
    rettemp=0
    if i in DPdict:
        print(int(DPdict[i]))
        continue
    for j in mydict.keys():

        if ball[i]==j:
            rettemp+=(mydict[j]-1)*(mydict[j]-2)/2
        else :
            rettemp+=(mydict[j]-1)*(mydict[j])/2
    DPdict[i]=rettemp
    print(int(rettemp))


### FIXED CODE ###

# -*- coding: utf-8 -*-
# 整数の入力

a = input()
# スペース区切りの整数の入力
H,W=a.split(" ")
N=int(H)
M=int(W)
retnum=0
for i in range(N):
    retnum+=i
retnum+=M*(M-1)/2
print(int(retnum))
import math
from functools import reduce
import sys

def gcd(number_list):
    return reduce(math.gcd, number_list)

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

if N == 2:
    print(int(max(Numbers)))
    sys.exit()
else:
    gcd_list = []
    for i in range(N):
        tmp_list = Numbers[:i] + Numbers[i + 1:]
        gcd_list.append(gcd(tmp_list))
    print(int(max(gcd_list)))


### FIXED CODE ###

from functools import reduce
from itertools import combinations
from fractions import gcd

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


Left = [0] * (N + 1)
Right = [0] * (N + 1)

for i in range(N):
    Left[i + 1] = gcd(Left[i], A[i])
    Right[N - i - 1] = gcd(Right[N - i], A[N - i - 1])
ans = 0
for i in range(N):
    ans = max(ans, gcd(Left[i], Right[i + 1]))
    
print(ans)
import sys

K = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip('\n')

# ## COMBINATION (MOD) ###
N_MAX = 10**6  # 問題サイズに合わせて変えておく
MOD = 10**9 + 7

inv = [0] * (N_MAX + 2)
inv[0] = 0  # 逆元テーブル計算用テーブル
inv[1] = 1

for i in range(2, N_MAX + 2):
    q, r = divmod(MOD, i)
    inv[i] = -inv[r] * q % MOD


# K 文字追加
ans = 0

ln = len(S)

p = pow(26, K, MOD)

st = time.time()
for i in range(1, K + 2):

    ans += p % MOD
    ans %= MOD

    # pre
    p = p * (ln + i - 1) * inv[i] * 25 * inv[26] % MOD

    # suf
    # s2 = (s2 * inv[26]) % MOD
en = time.time()

print(ans)

### FIXED CODE ###

import sys

K = int(sys.stdin.readline())
S = sys.stdin.readline().rstrip('\n')

# ## COMBINATION (MOD) ###
N_MAX = 10**6  # 問題サイズに合わせて変えておく
MOD = 10**9 + 7

inv = [0, 1]  # 逆元テーブル計算用テーブル

for i in range(2, N_MAX + 2):
    inv.append((-inv[MOD % i] * (MOD // i)) % MOD)

# K 文字追加
ans = 0

ln = len(S)

p1 = 1
p2 = 1
s2 = pow(26, K, MOD)

for i in range(1, K + 2):

    ans += (p1 * p2 * s2) % MOD
    ans %= MOD

    # print(p1, p2, s2)

    # pre
    p1 = (p1 * (ln + i - 1) * inv[i]) % MOD
    p2 = (p2 * 25) % MOD

    # suf
    s2 = (s2 * inv[26]) % MOD

print(ans)
3
acornistnt
peanutbomb
constraint

### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('- {} -> {}'.format(name, val), file=sys.stderr)
            return None

N = _I()
S = []
for i in range(N):
    S.append(input())

"""
a-zの文字数カウントする
[1,1,0,,,]
[1,1,0,,,]
[1,2,1,,,]

などのリストが得られる。
setしてカウント
"""

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
#  ex = [chr(ord('a') + i) for i in range(26)]
#  s_counts = []
#  for s in S:
#      s_count = []
#      for a in ex:
#          s_count.append(s.count(a))
#      s_counts.append(s_count)

#  #  print(s_counts)

#  ans = 0
#  done_list = []
#  for s_count in s_counts:
#      if s_count in done_list:
#          continue
#      else:
#          done_list.append(s_count)
#          cnt = s_counts.count(s_count)
#          if cnt == 1:
#              continue
#          else:
#              ans += combinations_count(cnt, 2)
chars = []
for s in S:
    char_list = []
    for char in s:
        char_list.append(char)
    char_list.sort()
    char_list = ''.join(char_list)
    chars.append(char_list)
#  print(chars)
ans = 0
done_list = []
char_counts = {}
for char in chars:
    if char in char_counts.keys():
        char_counts[char] += 1
    else:
        char_counts[char] = 1
for char_count in char_counts.values():
    if char_count == 1: continue


    ans += combinations_count(char_count, 2)
print(ans)
import math
def lcm_list(numbers):
    answer=numbers[0]
    for number in numbers:
        answer=(answer*number/math.gcd(answer,number))
    return answer
nm=list(map(int, input().split()))
a=list(map(int, input().split()))
n=nm[0]
m=nm[1]
b=0
while a[0]%2==0:
    for i in range(len(a)):
        if a[i]%2==0:
            a[i]=int(a[i]/2)
        else:
            b=1
            break
if b==1:
    print(0)
else:
    #amc=lcm_list(a)
    amc=math.gcd(a[0],a[1])
    print(int((m+amc)/(2*amc)))



### FIXED CODE ###

import fractions
from functools import reduce
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
nm=list(map(int, input().split()))
a=list(map(int, input().split()))
n=nm[0]
m=nm[1]
b=0
c=a[0]
dnum=0
while c%2==0:
    dnum+=1
    c=c//2
for i in range(len(a)):
    c=a[i]
    dnum1=0
    while c%2==0:
        dnum1+=1
        c=c//2
    #print(dnum)
    if dnum1!=dnum:
        b=1
        break

#print(a)
if b==1:
    print(0)
else:
    for i in range(len(a)):
        a[i]=a[i]//2
    #print(a)
    amc=lcm_list(a)
    #print(amc)
    # version3.5にてgcdがfractionsからmathに移動した
    print(int((m+amc)/(2*amc)))
n = int(input())
v = [int(x) for x in input().split()]
even = [0] * (10 ** 5)
odd = [0] * (10 ** 5)
for i in range(10 ** 5):
    even[i] = [0] * 2
    odd[i] = [0]*2
    even[i][1] = i
    odd[i][1] = i

for j in range(n):
    if j % 2 == 0:
        even[v[j]][0] += 1
    else:
        odd[v[j]][0] += 1

even = sorted(even, reverse=True)
odd = sorted(odd, reverse=True)
ans = 0
if even[0][1] == odd[0][1]:
    if even[0][0] > odd[0][0]:
        ans = n - even[0][0] - odd[1][0]
    else:
        ans = n - odd[0][0] - even[1][0]
else:
    ans = n-even[0][0]-odd[0][0]
print(ans)


### FIXED CODE ###

n = int(input())
v = [int(x) for x in input().split()]
big = 10**5+1
even = [0] * big
odd = [0] * big
for i in range(big):
    even[i] = [0] * 2
    odd[i] = [0]*2
    even[i][1] = i
    odd[i][1] = i

for j in range(n):
    if j % 2 == 0:
        even[v[j]][0] += 1
    else:
        odd[v[j]][0] += 1

even = sorted(even, reverse=True)
odd = sorted(odd, reverse=True)

ans = 0
if even[0][1] == odd[0][1]:
    ans = min(n - odd[0][0] - even[1][0], n - even[0][0] - odd[1][0])
else:
    ans = n - even[0][0] - odd[0][0]
print(ans)
a,b,n=map(int,input().split())
m=min(n,b)
tmp=(a*//b)-(((m-1)//b)*a)    
print(tmp)

### FIXED CODE ###

a,b,n=map(int,input().split())
m=min(n,b-1)
tmp=(a*m//b)-((m//b)*a)    
print(tmp)
import sys
n=int(input())
a=list(map(int,input().split()))
if len(a)==1:
  print("Yes")
  sys.exit()

for i in range(1,n)[::-1]:
  if a[i]>=a[i-1]:
    a[i-1]-=1
  elif a[i]a[i-1]:
    continue
  else:
    print("No")
    sys.exit()

print("Yes")

### FIXED CODE ###

import sys
n=int(input())
a=list(map(int,input().split()))
if len(a)==1:
  print("Yes")
  sys.exit()
if len(a)==2 and a[0]<=a[1]:
  print("Yes")
  sys.exit()
elif len(a)==2:
  print("No")
  sys.exit()
  
for i in range(1,n-1):
  if a[i+1]>=a[i]-1 and a[i]-1>=a[i-1]:
    a[i]=a[i]-1
    continue

  if a[i+1] >= a[i] and a[i] >=a [i-1]:
    continue
  else:
    print("No")
    sys.exit()
print("Yes")
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
for j in range(m):
  if a[0] >= a[1]:
    a[0] //= 2
  else:
    a[1] //= 2
    a.sort(reverse=True)
print(sum(a))

### FIXED CODE ###

n, m = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort(reverse=True)

if n > 1:
    a.append(0)
    biggest = a[0]
    now = 0
    while m > 0:
        a[now] = a[now]//2
        m -= 1
        biggest = a[0]
        for i in range(n-1):
            if a[i+1] >= biggest and m > 0:
                a[i+1] = a[i+1]//2
                m -= 1
            else:
                a.sort(reverse=True)
                break
    else:
        quit

else:
  for j in range(m):
    a[0] //= 2

print(sum(a))
n,a,b = map(int(input().split()))
s = 0
for i in range(n):
    x = sum(list(map(int,str(i).split())))
    if a <= x && x <= b:
        s += x
print(s)


### FIXED CODE ###

n,a,b = map(int,input().split())
s = 0
for i in range(n):
    x = sum(list(map(int,str(i+1))))
    if a <= x and x <= b:
        s += i+1
print(s)
N, M, K = map(int,input().split())
class UnionFind:
    def __init__(self, N):
        self.par = [-1 for i in range(N+1)]
        self.rank = [1]*(N+1)
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if self.rank[x] > self.rank[y]:
            self.par[x] += self.par[y]
            self.par[y] = x
        else:
            self.par[y] += self.par[x]
            self.par[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

UF = UnionFind(N)
friendlist = [[] for _ in range(N+1)]
for n in range(M):
    A, B = map(int,input().split())
    friendlist[A].append(B)
    friendlist[B].append(A)
    if not UF.same_check(A,B):
        UF.union(A, B)
blocklist = [[] for _ in range(N+1)]
for n in range(K):
    C, D = map(int, input().split())
    blocklist[C].append(D)
    blocklist[D].append(C)

for person in range(1,N+1):
    root = UF.find(person)
    ans = -UF.par[root]-1
    dellist = friendlist[person]+blocklist[person]
    for l in dellist:
        if UF.same_check(person,l):
            ans -= 1
    print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5+10)
N, M, K = map(int,input().split())
class UnionFind:
    def __init__(self, N):
        self.par = [-1 for i in range(N+1)]
        self.rank = [1]*(N+1)
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if self.rank[x] > self.rank[y]:
            self.par[x] += self.par[y]
            self.par[y] = x
        else:
            self.par[y] += self.par[x]
            self.par[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

UF = UnionFind(N)
friendlist = [[] for _ in range(N+1)]
for n in range(M):
    A, B = map(int,input().split())
    friendlist[A].append(B)
    friendlist[B].append(A)
    if not UF.same_check(A,B):
        UF.union(A, B)
blocklist = [[] for _ in range(N+1)]
for n in range(K):
    C, D = map(int, input().split())
    blocklist[C].append(D)
    blocklist[D].append(C)

for person in range(1,N+1):
    root = UF.find(person)
    ans = -UF.par[root]-1
    ans -= len(friendlist[person])
    for l in blocklist[person]:
        if UF.same_check(person,l):
            ans -= 1
    print(ans)
s = input()
b = 0
for i in range(n-1,-1,-1):
  if s[i] == 'B':
    b += 1
  else:
    if b > 0:
      b -= 1
    else:
      print(s[i], end='')
print()

### FIXED CODE ###

s = input()
ans_rev = ''
b = 0
for i in range(len(s)-1,-1,-1):
  if s[i] == 'B':
    b += 1
  else:
    if b > 0:
      b -= 1
    else:
      ans_rev += s[i]
for i in range(len(ans_rev)-1, -1,-1):
  print(ans_rev[i], end='')
print()
N, K = map(int,input().split()) # 複数の数字を変数に格納

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
  
 red = N - K
blue = K
division = 10 ** 9 + 7

for i in range(K):
    if i > red:
        print("{} 0".format(i+1))
    else:
        tmp_blue = cmb(blue-1,i)
        tmp_red = 1
        for j in range(i+1):
            tmp_red = tmp_red * (red+1-j) / (j+1) 
        result = int(tmp_blue * tmp_red % division)
        print("{} {}".format(i+1,result))


### FIXED CODE ###

N, K = map(int,input().split()) # 複数の数字を変数に格納

red = N - K
blue = K
division = 10 ** 9 + 7

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under % division
  
for i in range(K):
    if i > red:
        print("0")
    else:
        tmp_blue = cmb(blue-1,i) % division
        tmp_red = cmb(red+1,red-i)
        result = int(tmp_blue * tmp_red % division)
        print("{}".format(result))
# coding: utf-8
# Your code here!
import numpy as np

def main():
    N, W = map(int, input().split())
    V = 10**3 * 100
    
    dp = np.full(V, V+100)
    # print(len(dp))
    dp[0] = 0
    
    for _ in range(N):
        w, v = map(int, input().split())
        dp[v:] = np.minimum(dp[v:], dp[:-v]+w)

# print(dp)
print(np.max(np.where(dp<=W)))
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np
N, W = map(int, input().split())
 
items = [tuple(map(int, input().split())) for _ in range(N)]
 
dp = np.full(N*1000 +1, W+1) #横軸を価値の値に変換する
dp[0] = 0
 
for i, (w, v) in enumerate(items):
    dp[v:] = np.minimum(dp[v:], dp[:-v]+w)
 
print(np.max(np.where(dp <= W)))
n=input()
l=range(1,n)
m=0
while any(i&2==0 for i in l):
       l=[i/2 for i in l]
       m+=1
print(2**m)

### FIXED CODE ###

N=int(input())
c=0
n=range(1,N)
while any(i%2==0 for i in n):
          N=int(N/2)
          n=range(1,N+1)
          c+=1
print(2**c)
def trans(cur, prev_paths, score, goal_score, paths, N):
    # inf check
    if cur in prev_paths:
        return 'inf'
    if cur == N:
        goal_score = score
    if not cur in paths:
        return goal_score

    nodes = paths[cur]
    for n, s in nodes:
        new_score = score + s
        new_prev_paths = dict(prev_paths)
        new_prev_paths[cur] = 1
        tmp_goal_score = trans(n, new_prev_paths, new_score, goal_score, paths, N)
        if tmp_goal_score == 'inf':
            return 'inf'
        elif tmp_goal_score > goal_score:
            goal_score = tmp_goal_score

    return goal_score


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

paths = {}
prev_paths = {}
for i in range(M):
    a, b, c = map(int, input().split())
    if a in paths:
        paths[a].append((b, c))
    else:
        paths[a] = [(b, c)] 

cur_node = 1
prev_node = -1
score = trans(cur_node, prev_paths, 0, 0, paths, N)
print(score)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

def set_enable_goal(cur_node, back_paths, enable_goal):
    if cur_node in back_paths:
        for next_node in back_paths[cur_node]:
            if enable_goal[next_node - 1] == 0:
                enable_goal[next_node - 1] = 1
                set_enable_goal(next_node, back_paths, enable_goal)


N, M = map(int, input().split())
MIN = float('-inf')
INF_LIMIT = -MIN

back_paths = {}
all_paths = {}
for i in range(M):
    a, b, c = map(int, input().split())
    if a in all_paths:
        all_paths[a].append((b, c))
    else:
        all_paths[a] = [(b, c)]

    if b in back_paths:
        back_paths[b].append(a)
    else:
        back_paths[b] = [a]


# path cut
enable_goal= [0 for i in range(N)]
enable_goal[N - 1] = 1
set_enable_goal(N, back_paths, enable_goal)

for a, paths in all_paths.items():
    if not enable_goal[a - 1]:
        all_paths[a] = []
    else:
        valid_paths = []
        for b, c in paths:
            if enable_goal[b - 1]:
                valid_paths.append((b, c))
        all_paths[a] = valid_paths


scores = [MIN for i in range(N)]
scores[0] = 0

is_inf = False
for n in range(N):
    for a in all_paths.keys():
        for b, c in all_paths[a]:
            scores[b - 1] = max(scores[b - 1], scores[a - 1] + c)

# loop check
if not is_inf:
    prev_score = scores[N - 1]
    for a in all_paths.keys():
        for b, c in all_paths[a]:
            scores[b - 1] = max(scores[b - 1], scores[a - 1] + c)
    if prev_score != scores[N - 1]:
        is_inf = True


if is_inf:
    print('inf')
else:
    print(scores[N - 1])
N,K=map(int,input().split())
*p,= map(int, input().split())

s=[(p[n]+1)/2 for n in range(N)]
S=[0 for _ in range(N)]

S[0]=s[0]
for n in range(N-1):
    S[n+1]=s[n+1]+S[n]

def sjk(j):
    return S[j+K]-S[j]
delta = [sjk(i) for i in range(N-K)]

print(max(delta))

### FIXED CODE ###

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

s=[(p[n]+1)/2 for n in range(N)]
S=[0]*(N+1)

def make_S(n):
    S=[0]*(n+1)
    S[0]=0
    for i in range(n):
        S[i+1]=S[i]+s[i]
    return S
S=make_S(N)

def max_delta(n,k):
    max=-1000000
    for i in range(n-k+1):
        delta = S[i+k]-S[i]
        if delta>max:
            max=delta
    return max

print(max_delta(N,K))
n,d=map(int,input().split())

x=[list(map(int,input().split())) for i in range(n)]

lis=[False for i in range(5000)]
for i in range(65):
  lis[i*i]=True
  
ans=0
for i in range(n):
  for j in range(i):
    dis=sum([(x[i][k]-x[j][k])*(x[i][k]-x[j][k]) for k in range(d)])
    #print(dis)
    if lis[dis]:
      ans += 1
print(ans)

### FIXED CODE ###

n,d=map(int,input().split())

x=[list(map(int,input().split())) for i in range(n)]

lis=[False for i in range(16001)]
i=0
while(i*i<16000):
  lis[i*i]=True
  i+=1
  
ans=0
for i in range(n):
  for j in range(i):
    dis=sum([(x[i][k]-x[j][k])*(x[i][k]-x[j][k]) for k in range(d)])
 #   print(dis)
    if lis[dis]:
      ans += 1
print(ans)
N = int(input())
s, t = [], []
for i in range(N):
  s_i, t_i = [input().split(" ")]
  t_i = int(t_i)
  s.append(s_i)
  t.append(t_i)
X = input()

idx = 0
while idx < N:
  if s[idx] == X:
    idx += 1
    break
  idx += 1

ans = 0
for i in range(idx, N):
  ans += t[i]
print(ans)

### FIXED CODE ###

N = int(input())
s, t = [], []
for i in range(N):
  s_i, t_i = input().split(" ")
  t_i = int(t_i)
  s.append(s_i)
  t.append(t_i)
X = input()

idx = 0
while idx < N:
  if s[idx] == X:
    idx += 1
    break
  idx += 1

ans = 0
for i in range(idx, N):
  ans += t[i]
print(ans)
import math
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
a, b = map(int, input().split())
print(lcm(a,b))

### FIXED CODE ###

import math
def gcd(m, n):
    x = max(m,n)
    y = min(m,n)
    if x%y == 0:
        return y
    else:
        while x%y != 0:
            z = x%y
            x = y
            y = z
        else:
            return z
def lcm(m, n):
    return int(m*n/gcd(m,n))
a, b = map(int, input().split())
print(lcm(a,b))
def resolve():
    N, M = map(int, input().split())
    d = Counter(list(map(int, input().split())))

    for i in range(M):
        b, c = map(int, input().split())
        d[c] += b

    d = dict(sorted(d.items(), reverse=True))

    def main():
        cnt = 0
        ans = 0

        for k, v in d.items():
            if cnt + v < N:
                ans += v * k
                cnt += v
            else:
                ans += (N - cnt) * k
                return ans

    print(main())



resolve()

### FIXED CODE ###

A,B=map(int,input().split())
if A<=5:
    print(0)
elif 6<=A<=12:
    print(B//2)
else:
    print(B)
N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True,key=lambda x:abs(x))
a=[]
b=[]
c=0
mod=10**9+7
ans=1
for i in range(N):
  if A[i]<0:
    c+=1
    b.append(A[i])
  else:
    a.append(A[i])
if K==N:
  for i in range(N):
    ans*=A[i]
    ans%=mod
else:
  if c==N and K%2==1:
    for i in range(N-1,N-1-K,-1):
      ans*=A[i]
      ans%=mod
  else:
    d,e=0,0
    for i in range(K):
      ans*=A[i]
      if A[i]<0:
        d+=1
      else:
        e+=1
    if ans<0:
      bns=ans//b[d-1]*a[e]
      cns=ans//a[e-1]*b[d]
      ans=max(bns,cns)
      ans%=mod
print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
a,b,i=0,1,0
mod=10**9+7
ans=1
while i<K-1:
  if A[a]*A[a+1]>A[-b]*A[-b-1]:
    ans*=A[a]*A[a+1]
    ans%=mod
    a+=2
    i+=2
  else:
    ans*=A[-b]
    ans%=mod
    b+=1
    i+=1
if i==K-1:
  ans*=A[-b]
  ans%=mod
if A[-1]<0 and K%2==1:
  ans=1
  for i in A[N-K:]:
    ans*=i
    ans%=mod
print(ans%mod)
# ABC 120 D

from collections import deque

def resolve():
    N, M = map(int, input().split())
    bridges = []
    for i in range(M):
        a, b = map(int, input().split())
        bridges.append([a, b])

    par = [i for i in range(N+1)]

    nums = [1] * (N+1)  # i を根に持つ要素の数

    # x の根を求める
    def root(x):
        if par[x] == x:
            return x
        tmp = par[x]
        par[x] = root(par[x])  # 経路圧縮
        nums[tmp] -= 1
        nums[par[x]] += 1
        return par[x]

    # x と y の属する集合を併合
    # 便利になった数を返す
    def unite(x, y):
        x = root(x)
        y = root(y)
        if x == y:
            return
        par[x] = y
        conv = nums[x] * nums[y]
        nums[y] += nums[x]
        nums[x] = 0
        return conv

    # A[M-1] から順に橋をかけていく
    answers = [0] * M
    answers[M-1] = N*(N-1) // 2

    for i in range(M-1, 0, -1):
        a, b = bridges[i]
        if root(a) == root(b):  # 既に同じグループにいれば何もしない
            continue

        # 違うグループにいる場合はグループ同士を結合する
        conv = unite(a, b)
        answers[i-1] = answers[i] - conv

    for i in answers:
        print(i)


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

# ABC 120 D

from collections import deque

class UnionFind():
    # n : 要素数
    def __init__(self, n):
        self.n = n
        # root[x] < 0 ならそのノードが根かつその値が木の要素数
        # root[x] > 0 ならそのノードが根
        self.root = [-1] * (n+1)
        # 木の高さの管理
        self.rnk = [0] * (n+1)

    # x が所属するグループの根を返す
    def findRoot(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.findRoot(self.root[x])  # 経路圧縮
            return self.root[x]

    # x と y がそれぞれ所属するグループを結合する
    def unite(self, x, y):
        x = self.findRoot(x)
        y = self.findRoot(y)
        if x == y:
            # 既に同じグループに所属していれば何もしない
            return
        elif self.rnk[x] > self.rnk[y]:    # x の方が高さがある場合
            self.root[x] += self.root[y]   # x の要素数に y の要素数を足す
            self.root[y] = x               # y の親を x にする
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if self.rnk[x] == self.rnk[y]:
                self.rnk[y] += 1

    def isSameGroup(self, x, y):
        return self.findRoot(x) == self.findRoot(y)

    def count(self, x):
        return -self.root[self.findRoot(x)]

def resolve():
    N, M = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(M)]

    AB = AB[::-1]

    ret = []

    uf = UnionFind(N)

    for a, b in AB:
        if uf.isSameGroup(a-1, b-1):
            ret.append(0)
        else:
            ret.append(uf.count(a-1) * uf.count(b-1))
            uf.unite(a-1, b-1)

    ans = 0
    for i in range(M-1, -1, -1):
        ans += ret[i]
        print(ans)

if __name__ == "__main__":
    resolve()