Harryxun/stf_run huggingface dataset:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq 
from itertools import *
import math
import re
import string

def max_minus_min(areas):
    # print("areas", areas)
    return max(areas) - min(areas)

def solve2(h, w):
    area1 = h * (w // 2)
    area2 = h * w - area1
    return area1, area2

def solve(h, w):
    w_div_3 = w // 3;
    ans = 1e9
    for w2 in range(w_div_3, w_div_3 + 2):
        area1 = w2 * h
        ans = min(ans, max_minus_min([area1, *solve2(h, w - w2)]))
        ans = min(ans, max_minus_min([area1, *solve2(w - w2, h)]))
    return ans

H, W = map(int, input().split())
print(min(solve(H,W), solve(W,H)))


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# import array
# from bisect import *
# from collections import *
# import fractions
# import heapq 
# from itertools import *
# import math
# import re
# import string

def max_minus_min(areas):
    # print("areas", areas)
    return max(areas) - min(areas)

def solve2(h, w):
    area1 = h * (w // 2)
    area2 = h * w - area1
    return [area1, area2]

def solve(h, w):
    w_div_3 = w // 3;
    ans = 1e9
    for w2 in range(w_div_3, w_div_3 + 2):
        area1 = w2 * h
        ans = min(ans, max_minus_min([area1] + solve2(h, w - w2)))
        ans = min(ans, max_minus_min([area1] + solve2(w - w2, h)))
    return ans

H, W = map(int, raw_input().split())
print(min(solve(H,W), solve(W,H)))
n,k=map(int,input().split())
s=list(input())*2
p=['A' if s[i]=='B' else 'B' for i in range(n)]*2
head,tail=0,n
for i in range(2*n):
	if s[0]=='A':
		s[0],p[0]='B','A'
	else:
		s,p=p,s
		head+=1
		s[tail],p[tail]='A','B'
		tail+=1
	if i==k-1:
		print(''.join(s[head:tail]))
		break
else:
	if n%2==1 and k%2==1:
		if s[0]=='A':
			s[0],p[0]='B','A'
		else:
			s,p=p,s
			head+=1
			s[tail],t[tail]='A','B'
			tail+=1
	print(''.join(s[head:tail]))

### FIXED CODE ###

n,k=map(int,input().split())
s=list(input())*3
p=['A' if s[i]=='B' else 'B' for i in range(n)]*3
head,tail=0,n
for i in range(2*n):
	if s[head]=='A':
		s[head],p[head]='B','A'
	else:
		s,p=p,s
		head+=1
		s[tail],p[tail]='A','B'		
		tail+=1
	if i==k-1:
		print(''.join(s[head:tail]))
		break
else:
	if n%2==1 and k%2==1:
		if s[head]=='A':
			s[head],p[head]='B','A'
		else:
			s,p=p,s
			head+=1
			s[tail],p[tail]='A','B'		
			tail+=1
	print(''.join(s[head:tail]))
S = raw_input()
t = ['dreamer','dream','eraser','erase']
while len(S) > 0:
    for i in t:
        if S[S.rfind(i):]==i:
            S = S[:S.rfind(t)]
            break
        elif i == t[-1]:
            print "NO"
            exit()
print "YES"


### FIXED CODE ###

S = raw_input().split()[0]
t = ['dreameraser','dreamerase','dreamer','dream','eraser','erase']
while len(S) > 0:
    for i in t:
        if S[-len(i):]==i:
            S = S[:-len(i)]
            break
        elif i == t[-1]:
            print "NO"
            exit()
print "YES"
N, M = map(int, input().split())

s = []
for i in range(M):
    _, *tmp_s = map(int, input().split())
    s.append(tmp_s)
    
p = list(map(int, input().split()))

import numpy as np

s_matrix = []

for i in range(M):
    s_matrix.append([1 if x+1 in s[i] else 0 for x in range(N)])
    
s_matrix = np.array(s_matrix)

ans = 0

for i in range(2**N):
    on_off_pattern = list(format(i, '0%db' %N))
    on_nums = s_matrix @ np.array(list(map(int, on_off_pattern)))
    on_nums_mod2 = on_nums % 2

    if not False in (on_nums_mod2 == p):
        ans += 1
        
print(ans)

### FIXED CODE ###

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

s = []
for i in range(M):
    _, *tmp_s = map(int, input().split())
    s.append(tmp_s)
    
p = list(map(int, input().split()))

import numpy as np

s_matrix = []

for i in range(M):
    s_matrix.append([1 if x+1 in s[i] else 0 for x in range(N)])
    
s_matrix = np.array(s_matrix)

ans = 0

for i in range(2**N):
    on_off_pattern = list(format(i, '0%db' %N))
    on_nums = np.dot(s_matrix, np.array(list(map(int, on_off_pattern))))
    on_nums_mod2 = on_nums % 2

    if not False in (on_nums_mod2 == p):
        ans += 1
        
print(ans)
from collections import defaultdict as de
s=de(int)
n=int(input())
a=sorted([list(map(int,input().split()))for i in range(n)])
for i in range(n):
    for j in range(i-1):
        s[(a[i][0]-a[j][0],a[i][1]-a[j][1])]+=1
print(n-max(s.values()))


### FIXED CODE ###

from collections import defaultdict as de
s=de(int)
n=int(input())
a=sorted([list(map(int,input().split()))for i in range(n)])
for i in range(n):
    for j in range(i):
        s[(a[i][0]-a[j][0],a[i][1]-a[j][1])]+=1
print(n-max(s.values(),default=0))
N, K = map(int, input().split())
List = list(map(int, input().split()))
List.sort()
List.reverse()
ans=0

if len(List) == K-1:
    print(0)
    quit()

def Check(List,ans):
    if sum(List) <= 0:
        print(ans)
        quit()

#print(List)

i=0
while i<K:
    del List[0]
    i+=1

Check(List,ans)

j=0
while 1==1:
    ans+=List[j]
    List[j]=0
    Check(List,ans)
    j+=1
    

### FIXED CODE ###

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

h.sort(reverse=True)
for i in range(0,min(k,len(h))):
    h[i] = 0
hp = 0
for j in range(k,n):
    hp += h[j]

print(hp)
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
import numpy as np
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
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()))
MOD = 10**9 + 7

n, k = MAP()
a = LIST()

def update(a):
    b = np.zeros((n, n))
    for i in range(n):
        b[i, max(0, i-int(a[i])):min(n, i+int(a[i])+1)] = 1
    return np.sum(b, axis=0)
end = np.full(n, n)

for i in range(k):
    if np.all(a == end):
        break
    a = update(a)
for i in range(n):
    print(str(int(a[i]))+" ",end = "" )

### FIXED CODE ###

import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
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()))
MOD = 10**9 + 7

n, k = MAP()
a = LIST()


end = [n]*n

for i in range(min(k, 41)):
    b = [0]*(n+1)
    for j in range(n):
        b[max(j-a[j], 0)] +=1
        if j+a[j] <n:
            b[j+a[j]+1] -=1
    for j in range(1,n):
        b[j] += b[j-1]
    a = b[:n]

for i in range(n):
    print(str(int(a[i]))+" ",end = "" )
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]

for i in range(M - 1):
    if A[i] + 1 == A[i + 1]:
        print(0)
        exit()

memo = [0 for i in range(N + 10)]
memo[1] = 1
memo[2] = 2
for i in range(3, N + 10):
    memo[i] = memo[i - 1] + memo[i - 2]

ans = 1
for i in range(M):
    if i == 0:
        tmp = A[i] - 1
        if tmp == 0:
            tmp = 1
    else:
        tmp = A[i] - A[i - 1] - 2
    ans *= memo[tmp]
    ans %= int(1e9 + 7)

ans *= memo[(N - A[-1] - 1)]
ans %= int(1e9 + 7)
print(ans)



### FIXED CODE ###

N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]

for i in range(M - 1):
    if A[i] + 1 == A[i + 1]:
        print(0)
        exit()

MAX_N = int(1e5) + 10
memo = [0 for i in range(MAX_N + 10)]
memo[0] = 1
memo[1] = 1
memo[2] = 2
for i in range(3, MAX_N + 10):
    memo[i] = memo[i - 1] + memo[i - 2]

now = 0
ans = 1

for a in A:
    diff = a - now - 1
    ans *= memo[diff]
    ans %= int(1e9 + 7)
    now = a + 1

diff = N - now
ans *= memo[diff]
ans %= int(1e9 + 7)
print(ans)
import collections
N = int(input())
A = list(set(list(map(int, input().split()))))


def prime_factorize(n):
    r = set()
    if n % 2 == 0:
        r.add(2)
    f = 3
    while f * f <= n:
        if n % f == 0:
            r.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        r.add(n)
    return collections.Counter(r)


a1 = collections.Counter([])
a2 = prime_factorize(A[0])
for a in A:
    tmp = prime_factorize(a)
    a1 += tmp
    a2 &= tmp
if a2:
    print('not coprime')
elif a1.most_common()[0][1] >= 2:
    print('setwise coprime')
else:
    print('pairwise coprime')

### FIXED CODE ###

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


def prime_factorize(n):
    r = set()
    while n % 2 == 0:
        r.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            r.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        r.add(n)
    return r


j = 0
a1 = set()
a2 = prime_factorize(A[0])
for a in A[1:]:
    tmp = prime_factorize(a)
    if a1 & tmp:
        j = 1
    a1 |= tmp
    a2 &= tmp
if a2:
    print('not coprime')
elif j:
    print('setwise coprime')
else:
    print('pairwise coprime')
while True:
  data = input().split()
  a = int(data[0])
  op = data[1]
  b=int(data[2])
  
  if op=='?':
    break
  
  if  op=='+':
    print("{:d}".format(a+b))
  elif op=='-':
    print("{:d}".format(a-b))
  elif op=='/':
    print("{:d}".format(a/b))
  elif op=="*":
    print("{:d}".format(a*b))


### FIXED CODE ###

while True:
  a,op,b = input().split()
  a=int(a)
  op=str(op)
  b=int(b)
  
  if op=='?':
    break
  elif  op=='+':
    print("{:d}".format(a+b))
  elif op=='-':
    print("{:d}".format(a-b))
  elif op=='/':
    print("{:d}".format(a//b))
  elif op=="*":
    print("{:d}".format(a*b))
hen = map(int(input().split())

print(hen[0]*hen[1]  hen[0]*2+hen[1]*2)

### FIXED CODE ###

a,b=map(int, input().split())
print(a*b,2*a+2*b)
import time
start = time.time()
a, b, c = map(int, input().split())

cnt = 0
a_list = [0]*(1001001)
b_list = [0]*(1001001)
c_list = [0]*(1001001)
a_list[0] = a
b_list[0] = b
c_list[0] = c

for i in range(1, 10**9):
    a_list[i] = (b_list[i-1] + c_list[i-1]) // 2
    b_list[i] = (c_list[i-1] + a_list[i-1]) // 2
    c_list[i] = (a_list[i-1] + b_list[i-1]) // 2
    cnt += 1
    if a_list[i] % 2 != 0 or b_list[i] % 2 != 0 or c_list[i] % 2 != 0:
        break
    if time.time() - start >= 1:
        cnt = -1
        break

print(cnt)


### FIXED CODE ###

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

if any(i % 2 != 0 for i in [a, b, c]):
    print(0)
    exit()

if a == b and b == c:
    print(-1)
    exit()

cnt = 0
a_list = [0]*(1001001)
b_list = [0]*(1001001)
c_list = [0]*(1001001)
a_list[0] = a
b_list[0] = b
c_list[0] = c

for i in range(1, 1001001):
    a_list[i] = (b_list[i-1] + c_list[i-1]) // 2
    b_list[i] = (c_list[i-1] + a_list[i-1]) // 2
    c_list[i] = (a_list[i-1] + b_list[i-1]) // 2
    cnt += 1
    if a_list[i] % 2 != 0 or b_list[i] % 2 != 0 or c_list[i] % 2 != 0:
        break

print(cnt)
s=list(str(input()))

ans=[]
for i in s:
  if i=='1':
    ans.append('1')
  elif i=='0':
    ans.append(0,'0')
  else:
    if ans:
      ans.pop(-1)
    else:
      continue

print(''.join(ans))

### FIXED CODE ###

s=list(str(input()))

ans=[]
for i in s:
  if i=='1':
    ans.append('1')
  elif i=='0':
    ans.append('0')
  else:
    if ans:
      ans.pop(-1)
    else:
      continue

print(''.join(ans))
from sys import stdin


def main():
    n = int(stdin.readline())
    a = map(int, stdin.readline().split())
    r = [0]*9
    for ai in a:
        r[int(ai / 400)] += 1
    min = 0
    for i in range(8):
        if r[i] > 0:
            min += 1
    max = min + r[8]
    print(min, max)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from sys import stdin


def main():
    n = int(stdin.readline())
    a = map(int, stdin.readline().split())
    r = [0] * 13
    for ai in a:
        r[int(ai / 400)] += 1
    min = 0
    for i in range(8):
        if r[i] > 0:
            min += 1
    max = min
    for i in range(8, 13):
        max += r[i]
    if min == 0:
        min = 1
    print(min, max)


if __name__ == "__main__":
    main()
N = int(input())
seq = [i for in range(1,N) 
count = 0
for t in range(len(seq)):
  if seq[t]%3 != 0 or seq[t]%5 != 0:
       count += seq[t]
print(count)

### FIXED CODE ###

N = int(input())
seq = [i for i in range(1,N+1)]
count = 0
for t in range(0,N):
	if seq[t]%3 != 0 and seq[t]%5 != 0:
		count += seq[t]
print(count)
A,B = list(map(int,input(.split)))
if A-2*B < 0:
  print('0')
else:
  print(A-2*B)

### FIXED CODE ###

A,B = list(map(int,input().split()))
if A-2*B < 0:
  print('0')
else:
  print(A-2*B)
# encoding:utf-8
import copy
import numpy as np
import random

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

count_ac = np.zeros([len(s)])
for i in range(len(s)):
    if s[i]=="A" and i<len(s):
        if s[i+1]=="C":
            count_ac[i+1:] += 1

# print(count_ac)
for i in range(q):
    ans = count_ac[L[i][1]-1]-count_ac[L[i][0]-1]
    print(int(ans))


### FIXED CODE ###

# encoding:utf-8
import copy
import numpy as np
import random

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

# count_ac = np.zeros([n])
count_ac = []
count = 0
i = 0
while i < n-1:
    if s[i] == "A" and s[i+1] == "C":
        count_ac.append(count)
        count += 1
        count_ac.append(count)
        i += 2
    else:
        count_ac.append(count)
        i += 1

count_ac.append(count)


# print(count_ac)
for i in range(q):
    ans = count_ac[L[i][1]-1]-count_ac[L[i][0]-1]
    print(int(ans))
a = []
while True:
    inp = input()
    if inp[0] == "i":
        a.append(int(inp[7:]))
    elif inp[0] == "e":
        a.sort()
        print(a.pop())
    else:
        break

### FIXED CODE ###

import heapq

a = []
while True:
    inp = input().split()
    if inp[0] == "insert":
        heapq.heappush(a, -int(inp[1]))
    elif inp[0] == "extract":
        print(-heapq.heappop(a))
    else:
        break
import math
print(math.factorial(int(input)))

### FIXED CODE ###

import math
print(math.factorial(int(input()))%(10**9+7))
a,b,c=map(int, input().split())

if a+b=c or b+c=a or c+a=b:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

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

if a+b==c or b+c==a or c+a==b:
  print("Yes")
else:
  print("No")
#左右それぞれで一番近い神社
#その神社それぞれの左右それぞれで一番近い寺
#はい２ぶたん
from bisect import bisect_right

A,B,Q = map(int,input().split())
s = [int(input())for i in range(A)]
t = [int(input())for i in range(B)]

ans = []
for i in range(0,Q,1):
    q = int(input())
    sr = min(bisect_right(s,q),A-1)
    sl = max(0,sr-1)

    tr = min(bisect_right(t,q),B-1)
    tl = max(0,sl-1)


    ans.append(min(
    abs(q-s[sr])+ abs(t[min(bisect_right(t,s[sr]),B-1)]-s[sr]),
    abs(q-s[sl])+ abs(t[min(bisect_right(t,s[sl]),B-1)]-s[sl]),
    abs(q-t[tr])+ abs(s[min(bisect_right(s,t[tr]),A-1)]-t[tr]),
    abs(q-t[tl])+ abs(s[min(bisect_right(s,t[tl]),A-1)]-t[tl]),
    abs(q-s[sr])+ abs(t[max(bisect_right(t,s[sr])-1,0)]-s[sr]),
    abs(q-s[sl])+ abs(t[max(bisect_right(t,s[sl])-1,0)]-s[sl]),
    abs(q-t[tr])+ abs(s[max(bisect_right(s,t[tr])-1,0)]-t[tr]),
    abs(q-t[tl])+ abs(s[max(bisect_right(s,t[tl])-1,0)]-t[tl]))
    )

for i in range(0,Q,1):
    print(ans[i])

### FIXED CODE ###

import bisect
 
A, B, Q = map(int, input().split())
INF = float('inf')
s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]
 
for i in range(Q):
    x = int(input())
    b = bisect.bisect_right(s, x)
    d = bisect.bisect_right(t, x)
    ans = INF
    for S in [s[b-1], s[b]]:
        for T in [t[d-1], t[d]]:
            ans1 = abs(S-x) + abs(S-T)
            ans2 = abs(T-x) + abs(T-S)
            ans = min(ans, ans1, ans2)
    print(ans)
n,k=map(int,input().split())
p=list(map(int,input().split()))
pro=[]
for ch in p:
  pro.append((ch*(ch+1))/2)
ans=[]
for i in range(n-k):
  ans.append(sum(pro[i:k+i]))
print(max(ans))


### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
ans=[sum(p[0:k])]
for i in range(1,n-k+1):
  ans.append(ans[i-1]+p[i+k-1]-p[i-1])
max_value=max(ans)
max_index=ans.index(max_value)
total=0
for i in p[max_index:max_index+k]:
  total+=(i+1)/2
print(total)
i=1
while True:
    n=int(input())
    i++
    print(f'Case {i}: {x}')



### FIXED CODE ###

i=1
while True:
    x=int(input())
    if(x==0):
        break
    print(f"Case {i}: {x}")
    i+=1
N, M = map(int, input().split())
S = list(input())

n = 0
next_n = 0
move = []
while n != N:
    for i in range(M, 0, -1):
        if n + i > N:
            continue

        if S[n + i] != '1':
            n = n + i
            move.append(i)
            break
    else:
        print(-1)
        exit()


print(1 / 0)
# i = len(move) - 1
# move.sort(reverse=True)
# n = 0
# ans = []
# while move:
#     if S[n + move[i]] != '1':
#         ans.append(move[i])
#         n += move[i]
#         del move[i]
#         i = len(move) - 1
#     else:
#         i -= 1
# 
# print(*ans)


### FIXED CODE ###

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


# 後ろから貪欲
ans = []
position = N
while position > 0:
    for move in range(M, 0, -1):
        if position - move < 0:
            continue

        if S[position - move] == '1':
            continue

        ans.append(move)
        position -= move
        break
    else:
        print(-1)
        exit()

print(*ans[::-1])
n = int(input())
a = list(map(int, input().split()))
b = [[0] * 21 for _ in range(n)]
for i in range(n):
    j = 0
    k = 1
    while True:
        if a[i] == 0:
            break
        if (a[i] // k) % 2 == 1:
            b[i][j] = 1
            a[i] -= k
        k *= 2
        j += 1
ans = 0
for i in range(n):
    s = b[i]
    j = 1
    ans += 1
    while True:
        if i + j >= n or j >= 21:
            break
        for k in range(n):
            s[k] += b[i + j][k]
        if max(s) >= 2:
            break
        else:
            ans += 1
        j += 1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
m, x, c = 0, 0, 0
j = 0
ans = 0
for i in range(n):
    m += a[i]
    x ^= a[i]
    c += 1
    if not m == x:
        while True:
            if m == x:
                break
            x ^= a[j]
            m -= a[j]
            j += 1
            c -= 1
    ans += c
print(ans)
import collections
import itertools

s = list(map(str, input()))
g = list(map(lambda x: int(x),input().split()))

seq = ('R', 'L')

ans = False

count_dict = collections.Counter(s)

g_sum = abs(g[0])+abs(g[1])
if g_sum > count_dict['F']:
    print('No')
else:
    patterns = list(itertools.product(seq, repeat=count_dict['T']))

    for _p in patterns:
        i = 0
        m = [0, 0]
        n = 3
        for _s in s:
            if _s == 'F':
                if n == 3:
                    m[0] = m[0] + 1
                elif n == 1:
                    m[0] = m[0] - 1
                elif n == 0:
                    m[1] = m[1] + 1
                elif n == 2:
                    m[1] = m[1] - 1
            else:
                i = i + 1
                if _p[i-1] == 'R':
                    if n == 0:
                        n = 3
                    else:
                        n = n - 1
                elif _p[i-1] == 'L':
                    if n == 3:
                        n = 0
                    else:
                        n = n + 1

        if m[0] == g[0] and m[1] == g[1]:
            ans = True
            break

    if ans:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

import math

a = list(map(lambda x: int(x),input().split()))
s = sum(a)
ave = math.ceil(sum(a)/len(a))

print(ave)
l = map(int, input().split())
m = max(l)
n = l.pop(m)
wa = 0
for i in n:
    wa += i
if wa == m:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

l = list(map(int, input().split()))
p = max(l)
s = min(l)
wa =sum(l)
m = wa - p - s
if m + s == p:
    print("Yes")
else:
    print("No")
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, n):
        self.parents = [i for i in range(n)]
        self.sizes = [1] * n
    def find(self, i):
        parent = self.parents[i]
        if parent == i:
            return i
        else:
            return self.find(parent)
    def unite(self, i, j):
        pi = self.find(i)
        pj = self.find(j)
        if pi == pj:
            pass
        else:
            self.sizes[pj] += self.sizes[pi]
            self.parents[pi] = pj 
 
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.sizes[px] * uf.sizes[py]
            uf.unite(px, py)
        ans.append(p)
 
    for a in reversed(ans[:-1]):
        print(a)
 
 
main()


### 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()
n,l = map(int, input().split())
a = [input() for i in range(n)]
a.sorted()
k = ""
for j in range(n):
  k = k+a[j]
print(k)
  

### FIXED CODE ###

n,l = map(int, input().split())
a = [input() for i in range(n)]
b = sorted(a)
k = ""
for j in range(n):
  k = k+b[j]
print(k)
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    b = 0
    bud = 0
    for ai in a:
        if a[i] != ai:
            bud += abs(ai - b)
            b = ai
    bud += abs(b)
    print(bud)


### FIXED CODE ###

a, b, c, d = map(int, [input() for i in range(4)])
print(min([a, b]) + min([c, d]))
x,y = map(int,input().split())
print(np.count_nonzero([list(x)[i]==list(y)[i]  for i in range(len(list(x)))]))

### FIXED CODE ###

import numpy as np
hoge = []
for i in range(2):
    a = input()
    hoge.append(a)
a=np.count_nonzero([list(hoge[0])[i]==list(hoge[1])[i]  for i in range(3)])
print(a)
N,Y = map(int,input().split())

ans = "-1 -1 -1"

for i in range(N+1):
  for j in range(N+1-j):
    if 0 <= Y - 10000*i - 5000*j <= 500*(N - i - j):
      print(i+" "+j+" "+N-i-j)
      exit()
print(ans)

### FIXED CODE ###

N,Y = map(int,input().split())
ans = "-1 -1 -1"
 
for i in range(N+1):
  for j in range(N+1-i):
    if Y == 10000*i + 5000*j + 1000*(N - i - j):
      print(str(i)+" "+str(j)+" "+str(N-i-j))
      exit()
print(ans)
import numpy as np
N = int(input())
S = list(input())
Q = int(input())
Q_list = [input().split() for _ in range(Q)]
t_list = []
for q in Q_list:
  type = int(q[0])
  if(type==1):
    S[int(q[1])-1] = q[2]
  else:
    s, e = int(q[1]), int(q[2])
    t = 0
    str_list = []
    t = len(np.unique(S[s-1:e]))
    t_list.append(t)
[print(t) for t in t_list]

### FIXED CODE ###

print((int(input())+1)//2)
ABC = list(map(int, input().split()))

ABC_1 = sorted(ABC)

ABC_1[-1] = ABC_1[-1]*2**K

print(sum(ABC_1))

### FIXED CODE ###

ABC = list(map(int, input().split()))
K = int(input())

ABC_1 = sorted(ABC)

ABC_1[-1] = ABC_1[-1]*2**K

print(sum(ABC_1))