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

s=input()
n=len("s")
q=int(input())
l=[]
start=""
end=""
m=0
for i in range(q):
    l.append(input())
    if l[i]=="1":
        m += 1

    else:
        due,f,c=l[i].split()
        if (f=="1" and m % 2==0) or (f !="1" and m % 2==1) :
            start += c
        else:
            end += c
if m % 2 ==0:

    start=start[::-1]
    s = start + s + end

else:
    s = s + end
    s = s[::-1]
    s = s + start

print(s)

### FIXED CODE ###

s=input()
n=len("s")
q=int(input())
l=[]
start=""
end=""
m=0
for i in range(q):
    l.append(input())
    if l[i]=="1":
        m += 1

    else:
        due,f,c=l[i].split()
        if (f=="1" and m % 2==0) or (f !="1" and m % 2==1) :
            start += c
        else:
            end += c
if m % 2 ==0:

    start=start[::-1]
    s = start + s + end

else:
    s = s + end
    s = s[::-1]
    s = s + start

print(s)
### BUGGY CODE ###

import math
k = int(input())
ans = 0

for a in range(1,k+1):
  for b in range(1,k+1):
    for c in range(1,k+1):
      ans += math.gcd(a, math.gcd(b, c))

print(ans)

### FIXED CODE ###

import math
k = int(input())
ans = 0
ab = {}

for a in range(1,k+1):
  for b in range(1,k+1):
    tmp = math.gcd(a, b)
    if tmp not in ab:
      ab[tmp] = 1
    else:
      ab[tmp] += 1

for c in range(1,k+1):
  for d in ab.keys():
    ans += math.gcd(c, d) * ab[d]

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

N = int(input())
W = []
G = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    W.append((a,b))
    G[a].append(b)
    G[b].append(a)
K = 0
for i in range(1,N+1):
    n = len(G[i])
    K = max(K,n)
print(K)
d = {}
D = {}
D[1] = 1
k = 1
H = []
list = [1]
sumi = []
while list:
    x = list.pop(0)
    sumi.append(x)
    y = G[x]
    k = D[x] + 1
    if k > K:
        k -= K
    while y:
        z = y.pop(0)
        if z not in list:
            if z not in sumi:
                list.append(z)
                d[(x,z)] = k
                D[z] = k
                k += 1
                if k > K:
                    k -= K
                
for i in range(N-1):
    a,b = W[i]
    print(d[(a,b)])


### FIXED CODE ###

N = int(input())
W = []
G = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    W.append((a,b))
    G[a].append(b)
    G[b].append(a)
K = 0
for i in range(1,N+1):
    n = len(G[i])
    K = max(K,n)
print(K)
d = {}
D = {}
D[1] = 1
k = 1
H = []
list = [1]
sumi = []
while list:
    x = list.pop(0)
    sumi.append(x)
    Y = G[x]
    k = D[x] + 1
    while Y:
        y = Y.pop(0)
        if x in G[y]:
            G[y].remove(x)
        if k > K:
            k -= K
        list.append(y)
        d[(x,y)] = k
        D[y] = k 
        k += 1
        if k > K:
            k -= K
                
for i in range(N-1):
    a,b = W[i]
    print(d[(a,b)])
### BUGGY CODE ###

a,b = map(int,input().split())
f=True
for i in range(max(a,b)):
  if abs(a-i)==abs(b-i):
    print(i)
    f=False
    break
if f:
  print("IMPOSSIBLE")

### FIXED CODE ###

a,b = map(int,input().split())
f=True
if a%2 == b%2:
  print((a+b)//2)
else:
  print("IMPOSSIBLE")
### BUGGY CODE ###

import itertools
from functools import lru_cache

@lru_cache(maxsize=10000)
def f(x):
    return (max(x) - min(x))

def resolve():
    MOD = 10**9 + 7
    N, K = map(int, input().split())
    A = map(int, input().split())

    c_list = itertools.combinations(A, K)

    fx = map(f, c_list)
    total = sum(fx)
    total = total % MOD
    print(total)

if __name__ == "__main__":
    resolve()

### FIXED CODE ###

import math
from functools import lru_cache
from operator import mul
from functools import reduce


def resolve():
    import sys
    input = sys.stdin.readline
    MOD = 10**9 + 7
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    A.sort()
    B = A[::-1]

    @lru_cache(maxsize=None)
    def combinations_count__(n, r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

    @lru_cache(maxsize=None)
    def combinations_count____(n, r):
        r = min(r, n - r)
        numer = reduce(mul, range(n, n - r, -1), 1)
        denom = reduce(mul, range(1, r + 1), 1)
        return numer // denom

    def combinations_count_(n, r):
        if n - r < r: r = n - r
        if r == 0: return 1
        if r == 1: return n

        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]

        for p in range(2,r+1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p-1,r,p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot

        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])

        return result

    def modinv(a, mod=10**9+7):
        return pow(a, mod-2, mod)

    def combinations_count(n, r, mod=10**9+7):
        if (r < 0) or (n < r):
            return 0
        r = min(r, n-r)
        return fact[n] * factinv[r] * factinv[n-r] % mod
    
    fact = [1, 1]
    factinv = [1, 1]
    inv = [0, 1]
    for i in range(2, N + 1):
        fact.append((fact[-1] * i) % MOD)
        inv.append((-inv[MOD % i] * (MOD // i)) % MOD)
        factinv.append((factinv[-1] * inv[-1]) % MOD)

    sum = 0
    for i in range(K-1, N):
        sum += combinations_count(i, K-1) * A[i] % MOD - combinations_count(i, K-1) * B[i] % MOD

    print(sum % MOD)


if __name__ == "__main__":
    resolve()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, m = map(int, input().split())
edges = [[]for _ in range(n)]
for _ in range(m):
    x, y = map(lambda x: int(x)-1, input().split())
    edges[x].append(y)


def dfs(v, parent):
    visited[v] = 1
    for v2 in edges[v]:
        if v2 == parent:
            continue
        dfs(v2, v)
        dist[v] = max(dist[v], dist[v2]+1)


dist = [0]*n
visited = [0]*n

for i in range(n):
    if visited[i]:
        continue
    dfs(i, -1)

print(max(dist))


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n, m = map(int, input().split())
edges = [[] for _ in range(n)]
for _ in range(m):
    x, y = list(map(lambda x: int(x)-1, input().split()))
    edges[x].append(y)


def memoize(f):
    memo = dict()

    def memoized(*args):
        if args in memo.keys():
            return memo[args]
        else:
            memo[args] = f(*args)
            return memo[args]
    return memoized

@memoize
def longest_path(v):
    retval = 0
    for v2 in edges[v]:
        retval = max(retval, longest_path(v2)+1)
    return retval


ans = 0
for i in range(n):
    ans = max(ans, longest_path(i))
print(ans)
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()
a = [0] * M
b = [0] * M
d = [0] * M

for i in range(M):
	a[i], b[i] = MAP()
	c = LIST()
	for x in c:
		d[i] += 1<<(x-1)

dp = [INF]*(1<<N)
dp[0] = 0
for i in range(1, M+1):
	for j in range(1<<N):
		dp[j|d[i-1]] = min(dp[j|d[i-1]], dp[j]+a[i-1])

if dp[-1] == INF:
	print(-1)
else:
	print(dp[-1])


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()
dp = [INF]*(1<<N)
dp[0] = 0

for _ in range(M):
	a, b = MAP()
	c = LIST()
	d = 0
	for x in c:
		d += 1<<(x-1)

	for j in range(1<<N):
		tmp = j|d
		dp[tmp] = min(dp[tmp], dp[j]+a)

if dp[-1] == INF:
	print(-1)
else:
	print(dp[-1])
### BUGGY CODE ###

N,H = map(int,input().split())
Ma = 1
B = []
for i in range(N):
    a,b = map(int,input().split())
    B.append(b)
    if a > Ma:
        Ma = a
B.sort()
B.reverse()
C = 0
while H > 0:
    if B == []:
        C += int(-(-H//Ma))
        H = 0
    else:
        if Ma >= B[0]:
            C += int(-(-H//Ma))
            H = 0
        else:
            C += 1
            H -= B[0]
            B = B[1:]
print(C)

### FIXED CODE ###

N,H = map(int,input().split())
Ma = 1
B = []
for i in range(N):
    a,b = map(int,input().split())
    B.append(b)
    if a > Ma:
        Ma = a
B.sort()
B.reverse()
i = 0
Mb = B[0]
while Mb > Ma and H > 0:
  i += 1
  H -= Mb
  if i == N:
    Mb = 0
  else:
    Mb = B[i]
if H <= 0:
  print(i)
else:
  print(i+int(-(-H//Ma)))
### BUGGY CODE ###

H, W, M, *HW = map(int, open(0).read().split())

R = HW[::2]
C = HW[1::2]

A = [0] * (H + 1)
B = [0] * (W + 1)
for h, w in zip(*[iter(HW)] * 2):
    A[h] += 1
    B[w] += 1

S = set(zip(*[iter(HW)] * 2))

ans = 0
for r in R:
    for c in C:
        ans = max(ans, A[r] + B[c] - ((r, c) in S))

print(ans)

### FIXED CODE ###

H, W, M, *HW = map(int, open(0).read().split())
HW = list(zip(*[iter(HW)] * 2))

A = [0] * (H + 1)
B = [0] * (W + 1)
for h, w in HW:
    A[h] += 1
    B[w] += 1

a = max(A)
b = max(B)

cnt = A.count(a) * B.count(b) - len([0 for h, w in HW if A[h] == a and B[w] == b])

print(a + b - (cnt == 0))
### BUGGY CODE ###

A,B,N = map(int,input().split())
for i in range(N):
  if A>0:
    A-=1
  else:
    if B>0:
      B-=1
print(A,B)

### FIXED CODE ###

A,B,N = map(int,input().split())
if A>=0:
  if N<=A:
    print(A-N,B)
  else:
    N = N-A
    if N<=B:
      print(0,B-N)
    else:
      print(0,0)
### BUGGY CODE ###

def resolve():
    N,K,Q = list(map(int,input().split()))
    A =[]
    for i in range(Q):
        A.append(input())
    P = []
    for i in range(N):
        P.append(K)
    def calc(n):
        return n-1

    for i in range(Q):
        P = list(map(calc,P))
        P[int(A[i])-1] += 1

    for i in range(N):
        if P[i] <= 0:
            print("No")
        else:
            print("Yes")
resolve()

### FIXED CODE ###

def resolve():
    N,K,Q = list(map(int,input().split()))
    A = [input() for i in range(Q)]
    P = [K] * N

    def calc(n):
        return n-Q

    for i in range(Q):
        P[int(A[i])-1] += 1

    P = list(map(calc, P))

    for i in range(N):
        if P[i] <= 0:
            print("No")
        else:
            print("Yes")
resolve()
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline 

n,k,*a = list(map(int,read().split()))
for i in range(n): a[i] -= 1

def pow2(a,n):
    if n==0: return list(range(n))
    if n==1: return a
    if n%2:
        return mul(a,pow2(a,n-1))
    else:
        x = pow2(a,n//2)
        return mul(x,x)

def mul(a,b):
    return [a[bi] for bi in b]

x = pow2(a,k)
print(x[0]+1)

### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline 


n,k,*a = list(map(int,read().split()))
for i in range(n): a[i] -= 1


now = 0
cnt = 0
used = [-1]*n

while used[now] == -1:
    used[now] = cnt
    cnt += 1
    now = a[now]
    if cnt == k:
        print(now+1)
        exit()

c = cnt - used[now]
#print(used,cnt,c,now)

k -= used[now]
k %= c
print(used.index(k+used[now])+1)
### BUGGY CODE ###

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

for i in range(n):
  temp = a.pop(i)
  tempList = sorted(a)
  print(tempList[n-2])
  a.insert(i,temp)

### FIXED CODE ###

import numpy as np
n = int(input())
a = [int(input()) for _ in range(n)]

# 最大値のインデックス
i1 = np.argmax(a)
temp = a[i1]
a[i1] = 0
# ２番目の最大値のインデックス
i2 = np.argmax(a)
a[i1] = temp


for i in range(n):
  if i == i1:
    print(a[i2])
  else:
    print(a[i1])
### BUGGY CODE ###

import collections

dq = collections.deque()
N, Q = map(int, input().split())
for i in range(N):
    name, time = input().split()
    dq.append((name, int(time)))
total_time = 0
while dq:
    name, time = dq.popleft()
    total_time += min(Q, time)
    if time <= Q:
        print(name, total_time)
    else:
        dq.append((name, time))

### FIXED CODE ###

import collections

dq = collections.deque()
N, Q = map(int, input().split())
for i in range(N):
    name, time = input().split()
    dq.append((name, int(time)))
total_time = 0
while dq:
    name, time = dq.popleft()
    total_time += min(Q, time)
    if time <= Q:
        print(name, total_time)
    else:
        dq.append((name, time-Q))
### BUGGY CODE ###

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

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9+ 7

ans = 0
for i in range(61):
  n = sum([int(bin(a>>i)[-1]) for a in A])
  ans += (n * (N - n) * (2 ** i) % MOD)
print(ans%MOD)

### FIXED CODE ###

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

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9+ 7

ans = 0
two = 1
for i in range(61):
  n = len([ a for a in A if (a >> i) & 1 ])
  ans += (n * (N - n) * two % MOD)
  two *= 2 
print(ans%MOD)
### BUGGY CODE ###

K = int(input())

num = 7

if(7 % K == 0):
    print(1)
    exit()

for i in range(1,K):
    num = num*10 + 7
    if(num % K == 0):
        print(i + 1)
        exit()

print(-1)
    


### FIXED CODE ###

K = int(input())

num = 0

for i in range(0,K):
    num = num*10 + 7
    if num % K == 0:
        print(i + 1)
        exit()

    num %= K

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

import bisect

n = int(input())
a = []
for i in range(n):
    a.append(int(input()))

color = [float("inf")]
min_color = color[0]
for i in a:
    if i <= min_color:
        color = [i] + color
        min_color = i
    else:
        insert = bisect.bisect_left(color, i)
        color[insert - 1] = i
        if insert == 1:
            min_color = color[0]
print(len(color) - 1)

### FIXED CODE ###

import bisect, collections

n = int(input())
num = collections.deque([])
for i in range(n):
    a = int(input())
    temp = bisect.bisect_left(num, a)
    if temp == 0:
        num.appendleft(a)
    else:
        num[temp - 1] = a
print(len(num))
### BUGGY CODE ###

s = list(input())
N = len(s)

s_tmp = list(s)
ans = 0
for i in range(N - 2):
    if s_tmp[i] == 'A' and s_tmp[i + 1] == 'B' and s_tmp[i + 2] == 'C':
        for i_back in range(i):
            if s_tmp[i - 1 - i_back] == 'A':
                continue
            else:
                break
        else:
            i_back = i
        #
        for j in range(i - i_back, i + 3):
            if j == i - i_back:
                s_tmp[j] = 'B'
            elif j == i - i_back + 1:
                s_tmp[j] = 'C'
            else:
                s_tmp[j] = 'A'
        #
        ans += (i_back + 1)

print(ans)


### FIXED CODE ###

s = input()

s = s.replace('BC', 'X')
# print("#", s)

seqs = []
seq = ''
for si in s:
    if si in ('A', 'X'):
        seq += si
    else:
        seqs.append(seq)
        seq = ''
else:
    if len(seq) > 0:
        seqs.append(seq)
        seq = ''
        
ans = 0
for seq in seqs:
    Ni = len(seq)
    cnttab = [None] * Ni
    cnt = seq.count('X')
    for i, ci in enumerate(seq):
        if ci == 'X':
            cnt -= 1
        cnttab[i] = cnt
    # print("##", seq, cnttab)
    #
    for i, ci in enumerate(seq):
        if ci == 'A':
            ans += cnttab[i]

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

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

### FIXED CODE ###

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

if b-a>200:
    for i in range(k):
        print(a+i)
    for i in range(k):
        print(b-k+1+i)
    
else:
    arr=[]
    for i in range(a,b+1):
        if i<a+k or i>b-k:
            arr.append(i)
    for i in range(len(arr)):
        print(arr[i])
### BUGGY CODE ###

x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))

d=[]
for i in a:
  for j in b:
    d.append(i+j)
d.sort(reverse=1)
ans=[]
if x+y>k:
  for i in d[:k]:
    for j in c:
      ans.append(i+j)
else:
  for i in d:
    for j in c:
      ans.append(i+j)
ans.sort(reverse=1)
if x+y+z>k:
  for i in ans[:k]:
    print(i)
else:
  for i in ans:
    print(i)

### FIXED CODE ###

x,y,z,K=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort(reverse=1)
b.sort(reverse=1)
c.sort(reverse=1)
m=[]
for i in range(x):
  for j in range(y):
    for k in range(z):
      if (i+1)*(j+1)*(k+1)>K:
        break
      m.append(a[i]+b[j]+c[k])
m.sort(reverse=1)
for i in m[:K]:
  print(i)
### BUGGY CODE ###

n = int(input())
li_a = list()
d_a = dict()

for _ in range(n):
    wk = int(input())
    li_a.append(wk)

    get = d_a.get(wk, 0)
    d_a[wk] = get + 1

for i in range(n):
    d_a_copy = d_a.copy()
    if d_a_copy.get(li_a[i], 0) == 1:
        d_a_copy.pop(li_a[i])
    print(max(d_a_copy.keys()))




### FIXED CODE ###

n = int(input())
li_a = list()
d_a = dict()

for _ in range(n):
    wk = int(input())
    li_a.append(wk)

    get = d_a.get(wk, 0)
    d_a[wk] = get + 1

li_top2 = sorted(d_a.keys(), reverse=True)[:2]

for i in range(n):
    val = li_a[i]

    if val not in li_top2:
        print(li_top2[0])
    else:
        if val == li_top2[0] and d_a.get(val, 0) == 1:
            print(li_top2[1])
        else:
            print(li_top2[0])
### BUGGY CODE ###

from scipy.special import comb

n = int(input())
a = list(map(int, input().split()))
l = [0] * (max(a))

for i in a:
    l[i-1] += 1
    #logging.debug(a)

ans = 0
for i in a:
    l[i-1] -= 1
    for j in l:
        ans += comb(j,2, exact=True)
    print(ans)
    ans = 0
    l[i-1] += 1

### FIXED CODE ###

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

import collections
C = collections.Counter(a)

#logging.debug(C)

sum=0
for v in list(C.values()):
	sum+=v*(v-1)//2
 
for k in range(n):
	x = C[a[k]]
	print(sum-(x*(x-1)//2)+((x-1)*(x-2)//2))
### BUGGY CODE ###

n = int(input())
A = [int(x) for x in input().split()]

A.sort(reverse=True)

line = [A[0]]
comfort = 0
for a in A[1:]:
    diff_comfort = [min(line[(i + 1) % len(line)], line[i])
                    for i in range(len(line))]
    pos = min(range(len(line)), key=lambda i: diff_comfort[i])
    comfort += diff_comfort[pos]
    line.insert(pos + 1 if pos < len(line) - 1 else 0, a)
print(comfort)


### FIXED CODE ###

n = int(input())
A = [int(x) for x in input().split()]
A.sort(reverse=True)
print(A[0] + sum(A[1:(n - 2) // 2 + 1]) * 2 +
      (0 if n % 2 == 0 else A[(n - 1) // 2]))
### BUGGY CODE ###

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

for i in range(0, n):
    result = result * a[i]
    # print(i)

# print(result)
# print(101*9901*999999000001)
# print(pow(10, 18))

if result > pow(10, 18):
    result = -1

print(result)


### FIXED CODE ###

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

for i in a:
    result = result * i

    # result = np.prod(a)

    if (result > pow(10, 18)):
        result = -1
        break

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

N=int(input())
a=[]
b=[]
c=[0]*N
cnt=0
for i in range(N):
  a.append(list(map(int, input().split())))
  a[i].append(i+1)
#print(a)

for i in range(N):
  b.append(a[i][0])
#print('b='+str(b))
for j in range(N*(N-1)//2):
  for i in range(N):
    if b[i]==i+1:
      cnt+=0
    elif i==b[b[i]-1]-1:
      c[i]+=1
  #print('c='+str(c))
  for i in range(N):
    b[i]=a[i][c[i]]
  #print('b='+str(b))
  cnt+=1
  if c==[N-1]*N:
    print(cnt)
    exit()

print('-1')

### FIXED CODE ###

import sys
from collections import deque

n = int(input())
matches = [[a - 1 for a in map(int, line.split())] for line in sys.stdin]
#print(matches)
q = deque(range(n))
#print(q)
depth = [0] * n
waiting = [-1] * n

while q:
    a = q.popleft()
    b = matches[a].pop()
    #print(a, b)
    if waiting[b] == a:
        depth[a] = depth[b] = max(depth[a], depth[b]) + 1
        if matches[a]:
            q.append(a)
        if matches[b]:
            q.append(b)
    else:
        waiting[a] = b

if any(matches):
    print(-1)
else:
    print(max(depth))
### BUGGY CODE ###

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

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

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y:
      return False

    if self.parents[x] > self.parents[y]:
      x, y = y, x

    self.parents[x] += self.parents[y]
    self.parents[y] = x
    return True

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

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

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]
    
  def all_group_numbers(self):
    return sum([-x*(-x-1)//2 for x in self.parents if x < -1])

  def group_count(self):
    return len(self.roots())

  def all_group_members(self):
    return {r: self.members(r) for r in self.roots()}

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
uf=UnionFind(N)
ans=[]
ANS=N*(N-1)//2
flg=True
for i in range(M-1,-1,-1):
  if flg:
    ans.append(ANS-uf.all_group_numbers())
    if ans[-1]==0:
      ans.extend([0]*i)
      break
  else:
    ans.append(ans[-1])
  
  flg=uf.union(AB[i][0]-1,AB[i][1]-1)
for i in range(len(ans)-1,-1,-1):
  print(ans[i])

### FIXED CODE ###

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

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

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y:
      return False,0,0

    if self.parents[x] > self.parents[y]:
      x, y = y, x
    nx=self.size(x)
    ny=self.size(y)
    self.parents[x] += self.parents[y]
    self.parents[y] = x
    
    return True,nx,ny

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

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

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]
    
  def all_group_numbers(self):
    return [-x for x in self.parents if x < -1]

  def group_count(self):
    return len(self.roots())

  def all_group_members(self):
    return {r: self.members(r) for r in self.roots()}

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
uf=UnionFind(N)
ans=[0]*(M+1)
ans[M]=N*(N-1)//2
i=M-1
for a,b in AB[::-1]:
  flg,na,nb=uf.union(a-1,b-1)
  if flg:
    ans[i]=ans[i+1]-na*nb
  else:
    ans[i]=ans[i+1]
  i-=1
for a in ans[1:]:
  print(a)