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

#開始がL以上のものかつR以下のものをにぶたんで抽出
#抽出した配列を終了でソートしてR以下のものを抽出
import bisect
N,M,Q=map(int,input().split())
LR = []
for _ in range(M):
    LR.append(list(map(int,input().split())))
LR.sort()
L = [x for x,_ in LR]
R = [x for _,x in LR]

for _ in range(Q):
    l,r = map(int,input().split())
    idx_L = bisect.bisect_left(L,l)
    idx_R = bisect.bisect_right(L,r)
    tmp = R[idx_L:idx_R+1]
    tmp.sort()
    print(bisect.bisect_right(tmp,r))

### FIXED CODE ###

import bisect
N,M,Q=map(int,input().split())
LR = []
for _ in range(M):
    LR.append(list(map(int,input().split())))
LR.sort()
L = [x for x,_ in LR]
R = [x for _,x in LR]

#事前に配列化 ans[i][j] i以降にスタート、j以前に完了の個数
ans = [[0]*510 for _ in range(510)]
for i in range(1,501):
    idx_L = bisect.bisect_left(L,i)
    arr=R[idx_L:]
    for ar in arr:
        ans[i][ar]+=1
    for j in range(1,501):
        ans[i][j]=ans[i][j-1]+ans[i][j]
    
for _ in range(Q):
    l,r = map(int,input().split())
    print(ans[l][r])
### BUGGY CODE ###

import  collections

H, W, M = map(int, input().split())

H_count = collections.defaultdict(int)
W_count = collections.defaultdict(int)
points = set()
for m in range(M):
    h, w = map(int, input().split())
    H_count[h] += 1
    W_count[w] += 1
    points.add((h, w))

max_count = 0

for h, h_count in H_count.items():
    for w, w_count in W_count.items():
        count = h_count + w_count
        if (h, w) in points:
            count -= 1
        max_count = max(max_count, count)

print(max_count)

### FIXED CODE ###

H, W, M = map(int, input().split())

cnt_h = [0] * (H + 1)
cnt_w = [0] * (W + 1)
points = set()
for m in range(M):
    h, w = map(int, input().split())
    cnt_h[h] += 1
    cnt_w[w] += 1
    points.add((h, w))

H_max = max(cnt_h)
W_max = max(cnt_w)

H_max_num = [i for i, cnt in enumerate(cnt_h) if cnt == H_max]
W_max_num = [i for i, cnt in enumerate(cnt_w) if cnt == W_max]

flag = 0
for h_num in H_max_num:
    for w_num in W_max_num:
        if (h_num, w_num) not in points:
            print(H_max + W_max)
            exit()

print(H_max + W_max -1)
### BUGGY CODE ###

num = int(raw_input())
array = map(int, raw_input().split(" "))

all_ok = True
if num % 2 == 0:
    for i in range(num / 2):
        n = i * 2 + 1
        if n in array and ( array.count(n) == 2 ):
            continue
        else:
            all_ok = False
            break
else:
    for i in range(num / 2 + 1):
        n = i * 2
        if n == 0:
            if n in array and (array.count(n) == 1):
                continue
            else:
                all_ok = False
                break
        else:
            if n in array and ( array.count(n) == 2 ):
                continue
            else:
                all_ok = False
                break


div = pow(10, 9) + 7
if all_ok:
    print pow(2, (num/2) ) % div
else:
    print 0


### FIXED CODE ###

num = int(raw_input())
array = map(int, raw_input().split(" "))

a = sorted(array)

if num % 2 == 0:
    for i in xrange(0, num, 2):
        if a[i] != a[i + 1]:
            print 0
            break
    else:
        div = pow(10, 9) + 7
        print pow(2, num / 2) % div
else:
    for i in xrange(1, num, 2):
        if a[i] != a[i + 1]:
            print 0
            break
    else:
        div = pow(10, 9) + 7
        print pow(2, num / 2) % div
### BUGGY CODE ###

# n = int(input())
n, a, b = map(int, input().split())
# a = list(map(int, input().split()))
row = []
while len(row) < n:
    i = 0
    while i != a:
        row.append("b")
        # print(i)
        i += 1

    j = 0
    while j != b:
        row.append("r")
        # print(j)
        j += 1

cnt = 0
k = 1
for r in row:
    if k == n+1:
        break
    k += 1

    if r == "b":
        cnt += 1

print(cnt)

### FIXED CODE ###

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

x = n//(a+b)

print(a*x + min(a, n%(a+b)))
### BUGGY CODE ###

N = int(input())
V = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]

ans = -float('inf')
d = len(V)
for b in range(2 ** d):
    tmp = 0
    for j in range(d):
        if ((b >> j) & 1):
            tmp += V[j] - C[j]
    ans = max(ans, tmp)
print(ans)

### FIXED CODE ###

N = int(input())
V = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]

ans = -float('inf')
d = len(V)
for b in range(2 ** d):
    tmp = 0
    for j in range(d):
        if ((b >> j) & 1):
            tmp += V[j] - C[j]
    ans = max(ans, tmp)
print(ans)
### BUGGY CODE ###

n = int(input())
list1 = list(map(int, input().split()))
s = 0
for i in range(n):
  for j in range(i+1,n):
    p = list1[i] * list1[j]
    s += p
print(s % (10**9 + 7))

### FIXED CODE ###

n = int(input())
list1 = list(map(int, input().split()))
s = 0
ss = sum(list1)
for i in range(n):
  a = list1[i]
  ss = ss - a
  p = a * ss
  s += p
print(s % (10**9 + 7))
### BUGGY CODE ###

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

first_to = []
to_dest = []

for ab in AB:
    if ab[0] == 1:
        first_to.append(ab[1])
    elif ab[1] == N:
        to_dest.append(ab[0])

for f in first_to:
    if f in to_dest:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')


### FIXED CODE ###

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

first_to = []
to_dest = []

for ab in AB:
    if ab[0] == 1:
        first_to.append(ab[1])
    elif ab[1] == N:
        to_dest.append(ab[0])
first_to = set(first_to)
to_dest = set(to_dest)

for f in first_to:
    if f in to_dest:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

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

if n%k == 0:
    print(0)
    exit()
    
if abs(n-k) > n:
    print(n)
    exit()

tmp = n
for i in range(1,int(n**0.5)+1):
    if abs(n-i*k) > tmp:
      break
    tmp = min(abs(n-i*k), tmp)
print(tmp)

### FIXED CODE ###

n, k = map(int, input().split())
a = n%k
print(min(a, k-a))
### BUGGY CODE ###

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

e_max = 0

def get_e(p):
    return p*(p+1)/2/p

for i in range(N-K+1):
    e = sum(map(get_e, p[i:i+K]))
    if e > e_max:
        e_max = e

print(e_max)

### FIXED CODE ###

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

def get_e(p):
    return p*(p+1)/2/p

e_list = [get_e(p[i]) for i in range(N)]
c_e_list = [0 for i in range(N)]
c_e_list[0] = e_list[0]
for i in range(1, N):
    c_e_list[i] = c_e_list[i-1] + e_list[i]

max_e = c_e_list[K-1]
for i in range(1, N-K+1):
    e = c_e_list[i+K-1] - c_e_list[i-1]
    if e > max_e:
        max_e = e

print(max_e)
### BUGGY CODE ###

import sys

input = sys.stdin.readline
mod = 998244353
N, M, K = map(int, input().split())

def comb(n, r):
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = (fact[i-1] * i) % mod #n!を計算
    # print('fact:{}'.format(fact))
    revfact = [1] * (n + 1) #逆元を定義
    revfact[n] = pow(fact[n], mod - 2, mod) #n!のmod-2乗を計算
    # print('revfact:{}'.format(revfact))
    for i in reversed(range(1, n)): #N-1から1まで
        revfact[i] = ((i + 1) * revfact[i + 1]) % mod
    # print('revfact:{}'.format(revfact))

    return (fact[n] * revfact[n-r] * revfact[r]) % mod

ans = 0
for k in range(K + 1):
    ans += (M * pow(M - 1, N - 1 - k, mod) * comb(N - 1, k)) % mod
    ans %= mod
print(ans)

### FIXED CODE ###

import sys

input = sys.stdin.readline

def comb(n, r):
    return (fact[n] * revfact[n-r] * revfact[r]) % mod

mod = 998244353
N, M, K = map(int, input().split())

fact = [1] * (N + 1)
for i in range(1, N + 1):
    fact[i] = (fact[i-1] * i) % mod #n!を計算
# print('fact:{}'.format(fact))
revfact = [1] * (N + 1) #逆元を定義
revfact[N] = pow(fact[N], mod - 2, mod) #n!のmod-2乗を計算
# print('revfact:{}'.format(revfact))
for i in reversed(range(1, N)): #N-1から1まで
    revfact[i] = ((i + 1) * revfact[i + 1]) % mod
# print('revfact:{}'.format(revfact))

ans = 0
for k in range(K + 1):
    ans += (M * pow(M - 1, N - 1 - k, mod) * comb(N - 1, k)) % mod
    ans %= mod
print(ans)
### BUGGY CODE ###

from collections import deque
S = list(input())
S = deque(S)

ans = 0
N = len(S)
going = True
while going:
    tmp = S.copy()
    for i in range(N - 1):
        if S[i] == "B" and S[i + 1] == "W":
            S[i] = "W"
            S[i + 1] = "B"
            ans += 1

    for i in range(N - 1, 0, -1):
        if S[i] == "W" and S[i - 1] == "B":
            S[i] = "B"
            S[i - 1] = "W"
            ans += 1
    if S == tmp:
        going = False

print(ans)
# print(S)


### FIXED CODE ###

S = list(input())
N = len(S)
ans = 0

WWW = S.count("W")

for i in range(N):
    if S[i] == "B":
        ans += WWW
    if S[i] == "W":
        WWW -= 1

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

n, k = map(int, input().split())
s = input()

nums = []
now = 1 # 今見ている値
cnt = 0 # 今見ている値の連続する個数
for i in range(n):
    if s[i] == str(now): # 今見ているもの同じ場合
        cnt += 1
    else:
        nums.append(cnt)
        now ^= 1
        cnt = 1
# if cnt != 0:
nums.append(cnt)
# print(nums) # 消し忘れ（でもTLEすることは分かった）
# 配列の大きさが奇数でないなら，0を追加
if len(nums) % 2 == 0:
    nums.append(0)

res = 0
for i in range(0, len(nums), 2): # 1のところを見ていく
    # if 2 * k + 1 + i > len(nums):
    #     break
    # tmp = sum(nums[i : 2 * k + 1 + i])
    left, right = i, min(i + 2 * k + 1, len(nums))
    tmp = sum(nums[left:right])
    res = max(res, tmp)
print(res)

### FIXED CODE ###

n, k = map(int, input().split())
s = input()

nums = []
now = 1 # 今見ている数
cnt = 0 # nowが並んでいる個数
for i in range(n):
    if s[i] == str(now):
        cnt += 1
    else:
        nums.append(cnt) # 切り替わりで追加
        now = 1 - now # 0と1を切り替える
        cnt = 1 # 新しいものをカウントし始める
# 最後
if cnt != 0:
    nums.append(cnt)

# 調整
if len(nums) % 2 == 0:
    nums.append(0)

add = 2 * k + 1

# 累積和を作る
acc = [0] * (len(nums) + 1)
for i in range(len(nums)):
    acc[i + 1] = acc[i] + nums[i]

res = 0
# 偶数番目だけ見る
for i in range(0, len(nums), 2):
    # [left, right)
    left = i
    right = min(i + add, len(nums))
    tmp = acc[right] - acc[left]
    res = max(res, tmp)

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

from collections import Counter
N = int(input())
A = list(enumerate(list(map(int, input().split()))))
b = Counter([x[0]+x[1]+1 for x in A])
c = Counter([x[0]-x[1]+1 for x in A])
count = 0
for x in b.items():
    for y in c.items():
        if x[0] == y[0]:
            count += x[1] * y[1]
print(count)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(enumerate(list(map(int, input().split()))))
b = Counter([x[0]+x[1]+1 for x in A])
c = Counter([x[0]-x[1]+1 for x in A])
count = 0
for x in b.items():
    count += x[1] * c[x[0]]
print(count)
### BUGGY CODE ###

N=int(input())
lst=list(map(int,input().split()))
s=0
for i in range(N):
    tf=True
    for j in range(i):
        if lst[j]<lst[i]:
            tf=False
            break
    if tf:
        s+=1
print(s)

### FIXED CODE ###

N=int(input())
lst=list(map(int,input().split()))
s=0
min=lst[0]
for i in lst:
    if i<=min:
        min=i
        s+=1
print(s)
### BUGGY CODE ###

import numpy as np
def solve(n, k, r, s, p, t):
    dp = np.zeros((n, 3), dtype=int)
    win_hand_mapping = {
        "r": "p",
        "s": "r",
        "p": "s"
    }
    score_mapping = {
        "r": r,
        "s": s,
        "p": p
    }
    hand_index_mapping = {
        "r": 0,
        "s": 1,
        "p": 2
    }
    for i0 in range(k):
        for i in range(i0, n, k):
            win_hand = win_hand_mapping[t[i]]
            win_hand_index = hand_index_mapping[win_hand]
            win_hand_score = score_mapping[win_hand]
            for before in range(3):
                for current in range(3):
                    point = (current == win_hand_index) * win_hand_score
                    if i < k:
                        dp[i][current] = max(dp[i][current], point)
                    elif before != current:
                        dp[i][current] = max(dp[i][current], dp[i-k][before] + point)
    return np.max(dp, axis=1)[-k:].sum()

n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = input()
print(solve(n, k, r, s, p, t))

### FIXED CODE ###

import numpy as np
def solve(n, k, r, s, p, t):
    dp = np.zeros((n, 3), dtype=int)
    win_hand_mapping = {
        "r": "p",
        "s": "r",
        "p": "s"
    }
    score_mapping = {
        "r": r,
        "s": s,
        "p": p
    }
    hand_index_mapping = {
        "r": 0,
        "s": 1,
        "p": 2
    }
    legal_hands_mapping = {
        i: [j for j in range(3) if i!=j] for i in range(3)
    }
    for i0 in range(k):
        for i in range(i0, n, k):
            win_hand = win_hand_mapping[t[i]]
            win_hand_index = hand_index_mapping[win_hand]
            win_hand_score = score_mapping[win_hand]
            for current in range(3):
                point = (current == win_hand_index) * win_hand_score
                if i < k:
                    dp[i][current] = max(dp[i][current], point)
                else:
                    for before in legal_hands_mapping[current]:
                        dp[i][current] = max(dp[i][current], dp[i-k][before] + point)
    return np.max(dp, axis=1)[-k:].sum()

n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = input()
print(solve(n, k, r, s, p, t))
### BUGGY CODE ###

import sys
 
sys.setrecursionlimit(1000000)

def select_pivot(a, i, j):
    n = j - i + 1
    if n < 3:
        return i
    else:
        b = [a[i], a[(i+j)/2], a[j]]
        b.sort()
        t = b[1]
        if a[i] == t:
            return i
        elif a[j] == t:
            return j
        else:
            return (i+j) / 2
 
def quick_sort2(a, i, j):
    if j <= i:
        pass
    else:
        pivot = select_pivot(a, i, j); s = i
        x = a[pivot]
        a[pivot], a[j] = a[j], a[pivot]
        for k in range(i, j):
            if a[k] <= x:
                a[s], a[k] = a[k], a[s]
                s += 1
        a[j], a[s] = a[s], a[j]
        quick_sort2(a, i, s-1)
        quick_sort2(a, s+1, j)


n = int(raw_input())
A = map(int, raw_input().split())

quick_sort2(A, 0, n - 1)

print " ".join(map(str, A))

### FIXED CODE ###

n = int(raw_input())
x = map(int,raw_input().split())
x.sort()
for i in xrange(n):
	print x[i],
### BUGGY CODE ###

from collections import Counter

n, m = map(int, input().split())
A = []
for i in range(m):
    l, r = map(int, input().split())
    A.extend(list(range(l, r + 1)))
    
cnt = 0
for v in Counter(A).values():
    if v == m:
        cnt += 1
        
print(cnt)

### FIXED CODE ###

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

l = -1
r = N + 1
for i in range(M):
    L, R = map(int, input().split())
    l = max(l, L)
    r = min(r, R)
    
if l > r:
    print(0)
else:
    print(r - l + 1)
### BUGGY CODE ###

from itertools import permutations

N, M, R = [int(n) for n in input().split()]
r = [int(n)-1 for n in input().split()]
d = [[100000000]*N for n in range(N)]

for i in range(N):
  for j in range(N):
    d[i][j] = 0

for m in range(M):
  A, B, C = [int(n) for n in input().split()]
  A-=1
  B-=1
  d[A][B] = C
  d[B][A] = C

for k in range(N):
  for i in range(N):
    for j in range(N):
      d[i][j] = min(d[i][k]+d[k][j], d[i][j])

res = 10000000000
for perm in permutations(range(R)):
  s = 0
  for i in range(R-1):
    s += d[r[perm[i]]][r[perm[i+1]]]
  res = min(s, res)

print(res)

### FIXED CODE ###

from itertools import permutations

N, M, R = [int(n) for n in input().split()]
r = [int(n)-1 for n in input().split()]
d = [[100000000]*N for n in range(N)]

for i in range(N):
  d[i][i] = 0

for m in range(M):
  A, B, C = [int(n) for n in input().split()]
  A-=1
  B-=1
  d[A][B] = C
  d[B][A] = C

for k in range(N):
  for i in range(N):
    for j in range(N):
      d[i][j] = min(d[i][k]+d[k][j], d[i][j])

res = 1000000000
for perm in permutations(range(R)):
  s = 0
  for i in range(R-1):
    s += d[r[perm[i]]][r[perm[i+1]]]
  res = min(s, res)

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

def main():
    n, k = map(int, input().split())
    p = [int(x) for x in input().split()]
    maxv = 0
    for i in range(n-k+1):
        maxv = max(maxv, (sum(p[i:i+k])+k)/2)
    print(maxv)

if __name__ == '__main__':
    main()
    

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    P = [int(x) for x in input().split()]
    p_e = list()
    exp = 0
    for p in P:
        # 期待値
        # 累積和
        exp += (1+p)/2
        p_e.append(exp)  
    if n == k:
        print(p_e[-1])
    else:
        # 初期値
        maxv = p_e[k-1] - p_e[0]
        for i in range(1, n-k):
            # 隣接するk個の期待値の和
            p_sum = p_e[k+i] - p_e[i]
            maxv = max(maxv, p_sum)
        print(maxv)

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

def main():
    import math
    N,M=map(int,input().split())
    a=[]
    for i in range(M):
        tmp=list(map(int,input().split()))
        tmpc=list(map(int,input().split()))
        c=0
        for j in range(len(tmpc)):
            c+=2**(tmpc[j]-1)
        tmp[1]=c
        a+=[tmp]


    dp=[[10**10 for j in range(2**N)] for i in range(M)]
    dp[0][0]=0
    dp[0][a[0][1]]=a[0][0]


    for i in range(1,M):
        dp[i]=dp[i-1]
        for j in range(2**N):
            z,p=a[i][0],a[i][1]
            q=j|p
            dp[i][q]=min(dp[i-1][j]+z,dp[i][q])

    ans=dp[M-1][2**N-1]
    print(ans if ans<10**10 else -1)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N,M=map(int,input().split())
    L=2**N
    dp=[10**10 for i in range(L)]
    dp[0]=0


    for i in range(M):
        a, _ = map(int, input().split())
        key=sum([2**(int(i)-1) for i in input().split()])
        for j in range(L):
                q=j|key
                dp[q]=min(dp[j]+a,dp[q])


    ans=dp[L-1]
    print(ans if ans<10**10 else -1)

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

#!/usr/bin/env python3

# from numba import njit

# input = stdin.readline

# @njit
def solve(n,a,b):
  delta = [b[i] - a[i] for i in range(n)]
  need = list(sorted(x for x in delta if x > 0))
  amari = list(sorted((abs(x) for x in delta if x < 0),reverse=True))
  if sum(need) > sum(amari):
    return -1
  k = 0
  s = 0
  while s < sum(need):
    s += amari[k]
    k += 1
  return k + len(need)
  


def main():
  N = int(input())
  # N,M = map(int,input().split())
  a = list(map(int,input().split()))
  b = list(map(int,input().split()))
  print(solve(N,a,b))
  return

if __name__ == '__main__':
  main()


### FIXED CODE ###

#!/usr/bin/env python3

# from numba import njit

# input = stdin.readline

# @njit
def solve(n,a,b):
  delta = [b[i] - a[i] for i in range(n)]
  need = list(x for x in delta if x > 0)
  amari = list(sorted((abs(x) for x in delta if x < 0),reverse=True))
  needScore = sum(need)
  if needScore > sum(amari):
    return -1
  k = 0
  s = 0
  while s < needScore:
    s += amari[k]
    k += 1
  return k + len(need)
  


def main():
  N = int(input())
  # N,M = map(int,input().split())
  a = list(map(int,input().split()))
  b = list(map(int,input().split()))
  print(solve(N,a,b))
  return

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

from itertools import (
    accumulate,  # 累積和のイテレータ
    groupby,  # 値をkey,同じ値の集まりをgroup
    permutations,  # 順列
    combinations,  # 組み合わせ
    product,  # 重複あり順列（直積, 深いネストにも使える）
    combinations_with_replacement,  # 重複あり組み合わせ
)

import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)


N = int(input())
ans = 0
for i, j, k in combinations_with_replacement(range(1, N+1), 3):
    if i==j==k:
        ans += i
    elif i==j:
        ans += gcd(i, k)*3
    elif j==k:
        ans += gcd(j, i)*3
    elif i==k:
        ans += gcd(i, j)*3
    else:
        ans += gcd_list([i, j, k])*6
print(ans)

### FIXED CODE ###

from itertools import (
    accumulate,  # 累積和のイテレータ
    groupby,  # 値をkey,同じ値の集まりをgroup
    permutations,  # 順列
    combinations,  # 組み合わせ
    product,  # 重複あり順列（直積, 深いネストにも使える）
    combinations_with_replacement,  # 重複あり組み合わせ
)

import fractions, math
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd, numbers)


N = int(input())
ans = 0
for i, j, k in combinations_with_replacement(range(1, N+1), 3):
    if i==j==k:
        ans += i
    elif i==j:
        ans += math.gcd(i, k)*3
    elif j==k:
        ans += math.gcd(j, i)*3
    elif i==k:
        ans += math.gcd(i, j)*3
    else:
        ans += gcd_list([i, j, k])*6
print(ans)
### BUGGY CODE ###

N, M = list(map(int, input().split()))
A=[0] * M
B=[0] * M

import math

for i in range(M):
  A[i], B[i] = list(map(int, input().split()))

  
island_dict = [i for i in range(N+1)] #{i+1:i+1 for i in range(N)} #島が属するグループ
group_dict = [[i] for i in range(N+1)] #{i+1:[i+1] for i in range(N)} #グループに属する島
group_len_dict= [1 for i in range(N+1)] #{i+1:1 for i in range(N)}

answer = [0] * M
answer[-1] = math.factorial(N) // (math.factorial(N-2)*2)
  
for i in range(M)[:0:-1]:
  if island_dict[A[i]] == island_dict[B[i]]:
    answer[i-1] = answer[i]
  else:
    groupA = island_dict[A[i]]
    groupB = island_dict[B[i]] #グループ合併, groupB消滅
    NA = group_len_dict[groupA]
    NB = group_len_dict[groupB]
    
    if NA>=NB:
      for j in group_dict[groupB]:
        island_dict[j] = groupA
      group_dict[groupA] = group_dict[groupA] + group_dict[groupB]
      #group_dict[groupB] = []
      group_len_dict[groupA] = group_len_dict[groupA] + group_len_dict[groupB]
      #group_len_dict[groupB] = 0
      
    else:
      for j in group_dict[groupA]:
        island_dict[j] = groupB
      group_dict[groupB] = group_dict[groupA] + group_dict[groupB]
      #group_dict[groupA] = []
      group_len_dict[groupB] = group_len_dict[groupA] + group_len_dict[groupB]
      #group_len_dict[groupA] = 0
      
    answer[i-1] = answer[i] - NA*NB

#print(answer)

for i in range(M):
  print(answer[i])
    
    

### FIXED CODE ###

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

roots = [(i,1) for i in range(N+1)] # root, num_islands_in_group

inconveniences = [0]*(M+1)
inconveniences[-1] = N*(N-1)//2 #すべての橋が崩落するとNC2

def find_root(a, roots=roots):
  if roots[a][0] == a:
    return roots[a]
  else:
    roots[a] = find_root(roots[a][0])
  return roots[a]

def reduce_inconvenience_with_unite(a, b, roots=roots):
  root_a, n_a = find_root(a)
  root_b, n_b = find_root(b)
  if root_a == root_b:
    return 0
  else:
    if n_a > n_b:
      roots[root_a] = (root_a, n_a + n_b) # 二項目は何でも良い
      roots[root_b] = (root_a, n_a + n_b)
    else:
      roots[root_a] = (root_b, n_a + n_b) # 二項目は何でも良い
      roots[root_b] = (root_b, n_a + n_b)
    return n_a * n_b

for i, ab in enumerate(AB[:0:-1]): #実は1個めの橋は全く関係ない
  a, b = ab
  inconveniences[M-1-i] = inconveniences[M-i] - reduce_inconvenience_with_unite(a,b)

for inc in inconveniences[1:]:
  print(inc)