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

# pencil and paper !
# n = 3 (x, y, z = 山, a, b, c = ダム)
# x = a - b + c
# y = a + b - c
# z = -a + b + c
# 
# n = 5
# x = a - b + c - d + e
# 両隣は + , それ以降は -, +, -, +
n = int(input())
aaa = list(map(int, input().split(' ')))
ans = []
for i in range(n):
    r = 1
    temp = 0
    for j in range(n):
        temp += (aaa[(i+j) % n ] * r)
        r *= -1
    ans.append(str(temp))
print(' '.join(ans))

### FIXED CODE ###

# pencil and paper !
# n = 3 (x, y, z = 山, a, b, c = ダム)
# x = a - b + c
# y = a + b - c
# z = -a + b + c
# 
# n = 5
# x = a - b + c - d + e
# y = a + b - c + d - e
# 両隣は + , それ以降は -, +, -, +
# z =-a + b + c - d + e
#
# 1e5 * 1e5だけど
# 2つめ以降は前のを利用で 1e5 * 1 
# y + x = 2a
# y = 2a - x
#
# z + y  = 2b
# z = 2b - y
n = int(input())
aaa = list(map(int, input().split(' ')))
ans = []
for i in range(n):  # 1e5
    r = 1
    temp = 0
    if not ans:
        for j in range(n):  # 1e5
            temp += (aaa[(i+j) % n ] * r)
            r *= -1
    else:
        temp = 2 * aaa[(i-1) % n] - ans[-1] 
    ans.append(temp)
print(' '.join(map(str, ans)))
### BUGGY CODE ###

n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n-1)]
pq=[list(map(int,input().split())) for _ in range(m)]
ab=sorted(ab, key=lambda x:x[0])
pq=sorted(pq, key=lambda x:x[0])

res=[0 for _ in range(n)]
for p,q in pq:
	res[p-1]+=q
for a,b in ab:
	res[b-1]+=res[a-1]
ans=[str(t) for t in res]
print(" ".join(ans))


### FIXED CODE ###

n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n-1)]
pq=[list(map(int,input().split())) for _ in range(m)]
ab2=sorted(ab, key=lambda x:x[0])
pq2=sorted(pq, key=lambda x:x[0])

res=[0 for _ in range(n)]
for p,q in pq2:
	res[p-1]+=q
for a,b in ab2:
	res[b-1]+=res[a-1]
ans=str(res[0])
for i in range(1,n):
	ans+=" "+(str(res[i]))
print(ans)
### BUGGY CODE ###

s = input()
l = len(s)

if s[0] != '1' or s[-2] != '1' or s[-1] != '0':
  print('-1')
  exit()
if s[:-1] != s[:-1][::-1]:
  print('-1')
  exit()

# 1頂点に全部ついた状態から始める
e = [list(range(2, l+1))] + [[] for _ in range(l-1)]
now = 0
h = (l-1) // 2
for i in range(h, 0, -1):
  c = s[i]
  if c == '0':
    continue
  # now の木から子をi個取り出して繋げる
  nowl = len(e[now])
  e[l-i-1] = e[now][-i:]
  e[now] = e[now][:nowl-i]
  now = l-i-1

for i, arr in enumerate(e):
  for a in arr:
    print(i+1, a)

### FIXED CODE ###

s = input()
l = len(s)

if s[0] != '1' or s[-2] != '1' or s[-1] != '0':
  print('-1')
  exit()
if s[:-1] != s[:-1][::-1]:
  print('-1')
  exit()

# 1頂点に全部ついた状態から始める
e = [l] + [-1] * (l-1)
now = 0
h = (l-1) // 2
for i in range(h, 0, -1):
  c = s[i]
  if c == '0':
    continue
  # now の木から子をi個取り出して繋げる
  e[now] = l - i
  e[l-i-1] = l
  now = l-i-1

for i, a in enumerate(e):
  for j in range(i+2, a+1):
    print(i+1, j)
### BUGGY CODE ###

h,w=map(int,input().split())
grid=[[1 if s=='#' else 0 for s in list(input())] for i in range(h)]
#print(grid)
black=0
maxi=1000
from collections import deque
visited=[[1000]*w for _ in range(h)]
def bfs(s):
    q=deque()
    q.append(s)
    visited[s[0]][s[1]]=grid[s[0]][s[1]]
    D=[[1,0],[0,1]]
    while q:
        pre=q.pop()
        before=visited[pre[0]][pre[1]]
        for d in D:
            x=pre[0]+d[0]
            y=pre[1]+d[1]
            if 0<=x<h and 0<=y<w:
                q.append([x,y])
                visited[x][y]=min(visited[x][y],before+grid[x][y])

bfs([0,0])
print(visited[-1][-1])

### FIXED CODE ###

h,w=map(int,input().split())
grid=[[1 if s=='#' else 0 for s in list(input())] for i in range(h)]
#print(grid)
maxi=10**5
from collections import deque
visited=[[maxi]*w for _ in range(h)]
def bfs(s):
    q=deque()
    q.append(s)
    visited[s[0]][s[1]]=grid[s[0]][s[1]]
    for r in range(h):
        for c in range(w):
            if r>=1:
                visited[r][c]=min(visited[r][c],visited[r-1][c]+grid[r][c])
                if grid[r-1][c]==1:
                    visited[r][c]=min(visited[r][c],visited[r-1][c])
            if c>=1:
                visited[r][c]=min(visited[r][c],visited[r][c-1]+grid[r][c])
                if grid[r][c-1]==1:
                    visited[r][c]=min(visited[r][c],visited[r][c-1])
            

bfs([0,0])
print(visited[-1][-1])
### BUGGY CODE ###

h,n = map(int,input().split())
dp = [[10**10]*(h+1) for i in range(n+1)]
dp[0][0] = 0

for i in range(1,n+1):
    a,b = map(int,input().split())
    for j in range(h+1):
        if j-a<0:
            dp[i][j] = min(b,dp[i-1][j])
        else:
            dp[i][j] = min(dp[i][j-a]+b,dp[i-1][j])

print(dp[n][h]) 

### FIXED CODE ###

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

ab = [list(map(int,input().split())) for i in range(n)]
ma = max(a for a,b in ab)


dp = [10**10]*(h+ma+1)
dp[0] = 0

for i in range(1,h+ma+1):
    dp[i] = min(dp[i-a]+b for a,b in ab)

print(min(dp[h:]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

h,w,d=map(int,input().split())
A=[]
for i in range(h):
    l=list(map(int,input().split()))
    for j in range(w):
        A.append([l[j],i,j])
ans=[]
for i in sorted(A):
    ans.append(i[1:])
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=map(int,input().split())
for i in range(h*w-1,d-1,-1):
    ans[i]=abs(ans[i][0]-ans[i-d][0])+abs(ans[i][1]-ans[i-d][1])
for i in range(d):
    ans[i]=0
for i in range(q):
    print(sum(ans[i] for i in range(l[i]+d-1,r[i],d)))

### FIXED CODE ###

import sys
input = sys.stdin.readline

h,w,d=map(int,input().split())
A=[0]*(h*w)
for i in range(h):
    l=list(map(int,input().split()))
    for j in range(w):
        A[l[j]-1]=[i,j]
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=map(int,input().split())
ans=[0]*(h*w)
for i in range(d,h*w):
    ans[i]=ans[i-d]+abs(A[i][0]-A[i-d][0])+abs(A[i][1]-A[i-d][1])
for i in range(q):
    print(ans[r[i]-1]-ans[l[i]-1])
### BUGGY CODE ###

N,K=map(int, input().split())
R,S,P=map(int, input().split())
T=input()

# N,K=7 ,1
# R,S,P=100 ,10, 1
# T="ssssppr"

# N,K=5, 2
# R,S,P=8, 7, 6
# T="rsrpr"

# N,K=30, 5
# R,S,P=325, 234, 123
# T="rspsspspsrpspsppprpsprpssprpsr"


max_ans=T.count("s")*R+T.count("p")*S+T.count("r")*P
for i in range(K):
    tmp_ans=T[i::K]
    for i in range(len((tmp_ans))-1):
        if tmp_ans[i]==tmp_ans[i+1]:
            if tmp_ans[i]=="s":
                max_ans-=R
            if tmp_ans[i]=="p":
                max_ans-=S
            if tmp_ans[i]=="r":
                max_ans-=P
            tmp_ans = tmp_ans[:i+1] + 'X' +tmp_ans[i+2:]

print(max_ans)
    
    


### FIXED CODE ###

N,K=map(int,input().split())
R,S,P=map(int,input().split())
T=input()
A=[]
for x in T:
    if x == 's':
        A.append('r')
    if x == 'p':
        A.append('s')
    if x == 'r':
        A.append('p')
 
for i in range(K,N):
    if A[i-K] == A[i]:
        A[i] = 'x'
 
ans = 0
for x in A:
    if x == 's':
        ans += S
    if x == 'p':
        ans += P
    if x == 'r':
        ans += R
print(ans)
### BUGGY CODE ###

from collections import deque
from sys import exit

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

a_book = [0]
for index, i in enumerate(input().split(), 1):
    if a_book[index-1] + int(i) <= K:
        a_book.append(a_book[index-1] + int(i))
    else:
        N = index - 1
        break

b_book = [0]
for index, i in enumerate(input().split(), 1):
    if b_book[index-1] + int(i) <= K:
        b_book.append(b_book[index-1] + int(i))
    else:
        M = index - 1
        break

search = deque()
check = {}


def search_count(v):
    search.appendleft(v)
    while search:
        v = search.popleft()

        if not v in check:
            check[v] = v[0] + v[1]

            if not (v[0] + 1, v[1]) in check:
                if v[0] + 1 <= N:
                    if a_book[v[0] + 1] + b_book[v[1]] <= K:
                        search.appendleft((v[0] + 1, v[1]))

            if not (v[0], v[1] + 1) in check:
                if v[1] + 1 <= M:
                    if a_book[v[0]] + b_book[v[1] + 1] <= K:
                        search.appendleft((v[0], v[1] + 1))


search_count((0, 0))

print(max(check.values()))


### FIXED CODE ###

from bisect import bisect_right
from time import time

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

a_book = [0]
for index, i in enumerate(input().split(), 1):
    if a_book[index-1] + int(i) <= K:
        a_book.append(a_book[index-1] + int(i))
    else:
        N = index - 1
        break

b_book = [0]
for index, i in enumerate(input().split(), 1):
    if b_book[index-1] + int(i) <= K:
        b_book.append(b_book[index-1] + int(i))
    else:
        M = index - 1
        break

check = {}

max_books = 0

for i, a in enumerate(a_book):
    b_pos = bisect_right(b_book, K - a)

    if max_books < b_pos - 1 + i:
        max_books = b_pos - 1 + i

print(max_books)
### BUGGY CODE ###

# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


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

    INF = 10 ** 18

    res = 1

    for i in range(N):
        res *= A[i]

    if res > INF:
        res = -1

    print(res)



main()


### FIXED CODE ###

# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
# from numba import njit


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

    Aset = set(A)

    if 0 in Aset:
        print(0)
        sys.exit()

    A.sort(reverse=True)

    res = 1
    INF = 10 ** 18

    for i in range(N):
        res *= A[i]
        if res > INF:
            res = -1
            break

    print(res)



main()
### BUGGY CODE ###

N=int(input())
p=[0]
count=0
for i in range (N):
  a=int(input())
  flag=0
  for j in range (i+1):
    if a==p[j]:
      p[j]=0
      count-=1
      flag=1
      p.append(0)
  if flag==0:
    p.append(a)
    count+=1
print(count)

### FIXED CODE ###

N=int(input())
p=[]
count=0
for i in range (N):
  a=int(input())
  p.append(a)
list.sort(p)
flag=1
for j in range (N-1):
  if p[j]==p[j+1]:
    flag*=-1
  else:
    if flag>0:
      count+=1
    flag=1
if flag>0:
  count+=1
print(count)
### BUGGY CODE ###

k = int(input())
g = [[] for _ in range(k)]
from collections import deque
dic = {1:1}
queue = deque([[1,1]])
while queue:
    v,cost = queue.popleft()
    if not v+1 in dic.keys() or cost+1<dic[v+1]:
        dic[v+1] = cost+1
        queue.append([v+1,cost+1])
    if not v*10%k in dic.keys() or cost<dic[v*10%k]:
        dic[v*10%k] = cost
        queue.append([v*10%k,cost])

print(dic[0])

### FIXED CODE ###

k = int(input())
from collections import deque
dic = {1:1}
queue = deque([[1,1]])
while queue:
    v,cost = queue.popleft()
    if not (v+1)%k in dic or cost+1<dic[(v+1)%k]:
        dic[(v+1)%k] = cost+1
        queue.appendleft([(v+1)%k,cost+1])
    if not v*10%k in dic or cost<dic[v*10%k]:
        dic[v*10%k] = cost
        queue.append([v*10%k,cost])

print(dic[0])
### BUGGY CODE ###

import math

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

if N == 1:
    print(P)
else:
    now_max = 1
    
    for i in range(int(math.pow(P, 1 / N)) + 1, 0, -1):
        if P % (i ** N) == 0:
            now_max = i
            break
    
    print(now_max)

### FIXED CODE ###

n, p = map(int, input().split())
if n == 1:
    print(p)
else:
    for i in range(1, round(p**(1/n))+1):
        if p % i**n ==0:
            res = i
    print(res)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
class segtree:
    ## define what you want to do ,(min, max)
    

    def __init__(self,n):
        self.n = n
        self.tree = [[]]*(2*n)
        
    def build(self, list):
        for i,x in enumerate(list,self.n):
            d = set()
            d.add(x)
            self.tree[i] = d
            
        for i in range(self.n-1,0,-1):
            self.tree[i] = self.tree[i<<1]|self.tree[i<<1 | 1]

    ## take the value of [l,r) 
    def get(self,l,r):
        l += self.n
        r += self.n
        res = set()

        while l < r:
            if l & 1:
                res |= self.tree[l]
                l += 1
            if r & 1:
                res |= self.tree[r-1]
            l >>= 1
            r >>= 1
        return len(res)

n,q = map(int,input().split())
c = list(map(int,input().split()))

seg = segtree(n)
seg.build(c)

for i in range(q):
    l,r = map(int,input().split())
    print(seg.get(l-1,r))

### FIXED CODE ###

import sys
input = sys.stdin.readline

class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
 
    def sum(self, i):
        # [0, i) の要素の総和を返す
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s
    # 0 index を 1 index に変更  転倒数を求めるなら1を足していく
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


n,q = map(int,input().split())
c = list(map(int,input().split()))
Q = []
for i in range(q):
    l,r = map(int,input().split())
    Q.append([l,r,i])

Q.sort(key=lambda x: x[1])

bit = BIT(n)
ind = [-1]*(n+1)

ans = [0]*q
now = 0
for l,r,num in Q:
    while now < r:
        x = c[now]
        if ind[x] == -1:
            ind[x] = now
            bit.add(now,1)
        else:
            bit.add(ind[x],-1)
            ind[x] = now
            bit.add(now,1)
        now += 1
    ans[num] = bit.sum(r)-bit.sum(l-1)
for i in ans:
    print(i)
### BUGGY CODE ###

import collections

N = int(input())

S_list = []

for i in range(N):
    tmp = str(input())
    S_list.append(tmp)

c = collections.Counter(S_list)

appear = max(list(c.values()))

keys = [k for k, v in c.items() if v == appear]

for i in range(len(keys)):
    print(sorted(keys)[i])


### FIXED CODE ###

import collections

N = int(input())

S_list = []

for i in range(N):
    tmp = str(input())
    S_list.append(tmp)

c = collections.Counter(S_list)

appear = max(list(c.values()))

keys = [k for k, v in c.items() if v == appear]

keys_sorted = sorted(keys)

for i in range(len(keys)):
    print(keys_sorted[i])
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
for _ in range(q):
    l,r=map(int,input().split())
    st=s[l-1:r]
    print((len(st)-len([i for i in st.split("AC") if i!=""]))//2)

### FIXED CODE ###

from collections import deque
n,q=map(int,input().split())
s=input()
AC=deque()
count=0
for i in range(n):
    if i!=0:
        if s[i-1:i+1]=="AC":
            count+=1
    AC.append(count)
for _ in range(q):
    l,r=map(int,input().split())
    print(AC[r-1]-AC[l-1])
### BUGGY CODE ###

def solve(s,e):
	res=0
	for i in range(s,e+1):
		for j in range(s,e+1):
			res+=train[i][j]
	return res

city,dnum,qnum=map(int,input().split())

train=[[0 for i in range(city+1)] for i in range(city+1)]

for i in range(dnum):
	l,r=map(int,input().split())
	train[l][r]+=1
	
querry=[list(map(int,input().split())) for i in range(qnum)]

for q in querry:
	print(solve(*q))

### FIXED CODE ###

def main():
    n, m, Q = map(int, input().split())
    Train= [[0 for _ in range(n)] for _ in range(n)]
    
    for i in range(m):
        l, r = map(int, input().split())
        l, r = l - 1, r - 1
        Train[l][r] += 1
    
    P_Train = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        tmp = 0
        for j in range(n):
            tmp += Train[i][j]
            P_Train[i][j] = tmp

    for i in range(Q):
        p, q = map(int, input().split())
        p, q = p - 1, q - 1
        ans = solve(P_Train, n, p, q)
        print(ans)

def solve(P_Train, n, p, q):
    ans = 0
    for i in range(p, q + 1):
        if  p - 1 < 0:
            ans += P_Train[i][q]
        else:
            ans += P_Train[i][q] - P_Train[i][p - 1]
    return ans


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

n,k=map(int,input().split())
A=list(map(int,input().split()))
B=[]
C=[]
D=[]
for i in range(n):
  C.append((1+A[i])/2)
  B.append(sum(C))
  if i>=k:
    D.append(B[i]-B[i-k])
  elif i==k-1:
    D.append(B[i])
print(max(D))

### FIXED CODE ###

n,k=map(int,input().split())
p = [(int(s)+1)/2 for s in input().split()]
l = [sum(p[:k])]
for i in range(n-k):
  l.append(l[i]-p[i]+p[i+k])
print(max(l))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10000000)
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue

# import fractions

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

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

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

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


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

    S = iss()
    s,e = 0,0

    for i in range(len(S)):
        if S[i] == 'A':
            s = i
            break
    for i in range(len(S)):
        if S[::-1][i] == 'Z':
            e = i
            break

    print(len(S) - s - e)




if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os

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

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

MOD = 10 ** 9 + 7


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

    S = iss()
    a = S.find('A')
    z = S.rfind('Z')
    print(z - a + 1)


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

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

for k in range(K):
  imos = [0] * (N+1)
  for i, a in enumerate(A):
    l = max(0, i-a)
    r = min(N, i+1+a)
    imos[l] += 1
    imos[r] -= 1
  imos[0] = min(N, imos[0])
  for i in range(N):
    imos[i+1] = min(N, imos[i] + imos[i+1])
  A = imos[:-1]
  if all(a==N for a in A):
    break

print(*A)
  


### FIXED CODE ###

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

for k in range(K):
  imos = [0] * (N+1)
  for i, a in enumerate(A):
    l = max(0, i-a)
    r = min(N, i+1+a)
    imos[l] += 1
    imos[r] -= 1
  imos[0] = min(N, imos[0])
  for i in range(N):
    imos[i+1] = min(N, imos[i] + imos[i+1])
  A = imos[:-1]
  if all(a==N for a in A):
    break

print(*A)
### BUGGY CODE ###

n =int(input())
a = list(map(int,input().split()))
x=0
for i in range(n):
  if a.count(a[i]) != 1:
    print("NO")
    x=1
    break
    
if x == 0:
  print("YES")

### FIXED CODE ###

n = int(input())
a = list(int(x) for x in input().split())
x = 0
 
a.sort()
for i in range(n-1):
    if a[-1] - a[-2] == 0:
        print("NO")
        x = 1
        break
    a.pop()
 
if x == 0:
    print("YES")
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
# ----------------------------------------------------------------
# Use Solve Function

def solve(lines):
    N,M = map(int, lines.pop(0).split(' '))
    NLIST = []
    for i in range(M):
        A,B = map(int, lines.pop(0).split(' '))
        NLIST.append((A,B))

    res = N * (N-1) // 2
    R = [res]
    sets = []

    for i in range(M-1, 0, -1):
        x = NLIST[i]
        n1 = {x[0]}
        n2 = {x[1]}

        delete_idx = []

        for j,y in enumerate(sets):
            if x[0] in y:
                n1 = y
                delete_idx.append(j)
            if x[1] in y:
                n2 = y
                if not j in delete_idx:
                    delete_idx.append(j)

        delete_idx.sort(reverse=True)
        for k in delete_idx:
            sets.pop(k)

        if n1 != n2:
            res -= (len(n1) * len(n2))
            n1 = n1.union(n2)

        sets.append(n1)
        R.append(res)
    for i in range(M-1, -1, -1):
        print(R[i])


lines = [x.strip() for x in sys.stdin.readlines()]
#
##
## solve !!
##
solve(lines)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
# ----------------------------------------------------------------
# Use Solve Function

class UnionFind:
    def __init__(self, n):
        # ノードとリストのインデックスを一致させるために長さN+1のリストを作成
        self.par = [i for i in range(n+1)]
        self.size = [1 for i in range(n+1)]
        self.rank = [0] * (n+1)

    def __str__(self):
        return ' '.join(map(str,self.par))

    def tree_size(self, x):
        x = self.find(x)
        return self.size[x]

    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 same_check(self, x, y):
        return self.find(x) == self.find(y)

    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.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
# A,B = map(int, input().split(' '))
N,M = map(int, input().split(' '))
NLIST = []
for i in range(M):
    A,B = map(int, input().split(' '))
    NLIST.append((A,B))

res = N * (N-1) // 2
R = [res]
uf = UnionFind(N)

NLIST.reverse()
for i in range(M-1):
    x = NLIST[i]
    n1 = x[0]
    n2 = x[1]

    if not uf.same_check(n1,n2):
        res -= uf.tree_size(n1) * uf.tree_size(n2)
        uf.unite(n1,n2)
    R.append(res)

R.reverse()
for i in range(M):
    print(R[i])
# for i in range(M-1, -1, -1):
#     print(R[i])