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

S = input()

dp = [[0 for _ in range(3 + 1)] for _ in range(len(S) + 1)]

dp[0][0] = 1
for i in range(1, len(S) + 1):
    if S[i - 1] == 'A':
        dp[i][0] += dp[i - 1][0]
        dp[i][1] += dp[i - 1][1]
        dp[i][2] += dp[i - 1][2]
        dp[i][3] += dp[i - 1][3]

        dp[i][1] += dp[i - 1][0]
    elif S[i - 1] == 'B':
        dp[i][0] += dp[i - 1][0]
        dp[i][1] += dp[i - 1][1]
        dp[i][2] += dp[i - 1][2]
        dp[i][3] += dp[i - 1][3]

        dp[i][2] += dp[i - 1][1]
    elif S[i - 1] == 'C':
        dp[i][0] += dp[i - 1][0]
        dp[i][1] += dp[i - 1][1]
        dp[i][2] += dp[i - 1][2]
        dp[i][3] += dp[i - 1][3]

        dp[i][3] += dp[i - 1][2]
    else:
        dp[i][0] += dp[i - 1][0] * 3
        dp[i][1] += dp[i - 1][1] * 3
        dp[i][2] += dp[i - 1][2] * 3
        dp[i][3] += dp[i - 1][3] * 3

        dp[i][1] += dp[i - 1][0]
        dp[i][2] += dp[i - 1][1]
        dp[i][3] += dp[i - 1][2]

B = 10 ** 9 + 7
print(dp[len(S)][3] % B)

### FIXED CODE ###


S = input()

dp = [[0 for _ in range(3+ 1)] for _ in range(len(S) + 1)]
dp[0][0] = 1

B = 10 ** 9 + 7
for i in range(1, len(S) + 1):
    if S[i - 1] == 'A':
        dp[i][0] += dp[i - 1][0]
        dp[i][1] += dp[i - 1][1]
        dp[i][2] += dp[i - 1][2]
        dp[i][3] += dp[i - 1][3]

        dp[i][1] += dp[i - 1][0]
    elif S[i - 1] == 'B':
        dp[i][0] += dp[i - 1][0]
        dp[i][1] += dp[i - 1][1]
        dp[i][2] += dp[i - 1][2]
        dp[i][3] += dp[i - 1][3]

        dp[i][2] += dp[i - 1][1]
    elif S[i - 1] == 'C':
        dp[i][0] += dp[i - 1][0]
        dp[i][1] += dp[i - 1][1]
        dp[i][2] += dp[i - 1][2]
        dp[i][3] += dp[i - 1][3]

        dp[i][3] += dp[i - 1][2]
    else:
        dp[i][0] += dp[i - 1][0] * 3
        dp[i][1] += dp[i - 1][1] * 3
        dp[i][2] += dp[i - 1][2] * 3
        dp[i][3] += dp[i - 1][3] * 3

        dp[i][1] += dp[i - 1][0]
        dp[i][2] += dp[i - 1][1]
        dp[i][3] += dp[i - 1][2]

    for k in range(4):
        dp[i][k] %= B


print(dp[len(S)][3])
### BUGGY CODE ###

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

c=0
i=0

for i in range(M):
    idx=A.index(max(A))
    A[idx]=A[idx]//2
    c+=1


print(sum(A))

### FIXED CODE ###

import heapq

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

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

heapq.heapify(A)

for i in range(M):
    temp=heapq.heappop(A)
    heapq.heappush(A,(temp+1)//2)

print(-1*sum(A))
### BUGGY CODE ###

# your code goes here
buf = input().split()
N = int(buf[0])
M = int(buf[1])
Q = int(buf[2])
import numpy as np
train = np.zeros((N+1, N+1))
for i in range(M):
	buf = input().split()
	L = int(buf[0])
	R = int(buf[1])
	train[L][R] += 1
#print(train)
for i in range(Q):
	buf = input().split()
	p = int(buf[0])
	q = int(buf[1])
	buf_train = train[p:q+1, p:q+1]
	print(int(np.sum(buf_train)))

### FIXED CODE ###

import numpy as np
N, M, Q = map(int, input().split())

train = np.zeros((N, N))
for i in range(M):
	L, R = map(int, input().split())
	train[N-L][R-1] += 1
train = np.cumsum(np.cumsum(train, axis=0), axis=1)

for _ in range(Q):
	p, q = map(int, input().split())
	print(int(train[N-p][q-1]))
### BUGGY CODE ###

l=list(input())
n=len(l)
p=10**9+7
ans=0
d=0
for i in range(n):
    if l[i]=="1":
        x=n-i-1
        k=x//p
        m=x%p
        K=d//p
        M=d%p
        ans+=(((3**(k+m))%p)*((2**(K+M))%p))%p
        d+=1
    else:
        continue
K=d//p
M=d%p
ans+=2**(K+M)
print(ans%p)



### FIXED CODE ###

l=list(input())
n=len(l)
p=10**9+7
dp1=[0]*n
dp2=[0]*n
dp1[0]=1
dp2[0]=2
for i in range(1,n):
    if l[i]=="1":
        dp1[i]=(3*dp1[i-1]+dp2[i-1])%p
        dp2[i]=(dp2[i-1]*2)%p
    else:
        dp1[i]=(3*dp1[i-1])%p
        dp2[i]=dp2[i-1]
print((dp1[n-1]+dp2[n-1])%p)
### BUGGY CODE ###

from bisect import bisect_right as br
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(N)]

AB.sort()
A=[a for a,b in AB]
B=[b for a,b in AB]
works=[]
ans=0
for i in range(1,M+1):
  day=M-i
  latest=i
  #worksにlatest日以内に報酬を貰える仕事を追加する
  for _ in range(br(A,latest)):
    A.pop(0)
    works.insert(br(works,B[0]),B[0])
    B.pop(0)
  if not works:
    continue
  ans+=works.pop(-1)

print(ans)









### FIXED CODE ###

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

AB.sort(reverse=True)
works=[]
heapq.heapify(works)
ans=0
for i in range(1,M+1):
  day=M-i
  latest=i
  while AB and AB[-1][0]<=latest:
    a,b=AB.pop()
    heapq.heappush(works,-b)
  if not works:
    continue
  ans-=heapq.heappop(works)

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

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

ans = []
for i in range(n):
    cur = 0
    count = 0

    while cur < n:
        if s[cur] == "o" and cur != i:
            count += 1
            cur += c

        cur += 1

    if count < k:
        ans.append(i+1)

for i in ans:
    print(i)

### FIXED CODE ###

from sys import stdin
def main():
    input = stdin.readline
    n, k, c = map(int, input().split())
    s = input()

    l, r = [], []
    cur = 0
    count = 0

    while cur <= n:
        if s[cur] == "o":
            count += 1
            l.append((count, cur+1))
            cur += c

        cur += 1

    cur = n
    count = k

    while cur >= 0:
        if s[cur] == "o":
            r.append((count, cur+1))
            count -= 1
            cur -= c

        cur -= 1

    ans = (i[1] for i in set(l) & set(r))
    for i in sorted(ans):
        print(i)


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

H, W = map(int, input().split())
A = []
for i in range(H):
  tmp = input()
  A.append(tmp)

B = []

for i in range(H):
  for j in range(W):
    tmp = []
    for h in range(H):
      for w in range(W):
        if A[h][w] == "#":
          tmp.append(abs(h-i)+abs(w-j))
    B.append(min(tmp))
print(max(B))

### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
A = [input() for i in range(H)]
X = [1,0,-1,0]
Y = [0,-1,0,1]

INF = 99999
dp = [[-1]*W for i in range(H)]
q = deque()
for y, row in enumerate(A):
  for x,c in enumerate(row):
    if c == "#":
      dp[y][x] = 0
      q.append((y,x))
while q:
  y,x = q.popleft()
  d = dp[y][x]
  for i in range(4):
    nx = x + X[i]
    ny = y + Y[i]
    if (0 <= nx < W) and (0 <= ny < H) and (dp[ny][nx] == -1):
      dp[ny][nx] = d + 1
      q.append((ny,nx))
print(max(max(row) for row in dp))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys, os

def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n, m = inp[0],inp[1]

    wi, vi = inp[2], inp[3]


    dp = [0] * (m + 1)
    for j in range(wi, m + 1):
        dp[j] = vi

    for i in range(n - 1):
        wi = inp[2*i + 4]
        vi = inp[2*i + 5]
        for j in range(m, wi-1, -1):
            if dp[j] < vi + dp[j - wi]:
                dp[j] = vi + dp[j - wi]

    print(dp[-1])
main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys, os
range = xrange

def main():
    inp = [int(x) for x in os.read(0, os.fstat(0).st_size).split()]
    n, m = inp[0],inp[1]

    w, v = inp[2::2], inp[3::2]

    dp = [0] * (m + 1)
    for j in range(w[0], m + 1):
        dp[j] = v[0]

    for i in range(n - 1):
        vi = v[i + 1]
        wi = w[i + 1]
        for j in reversed(range(wi, m + 1)):
            dp[j] = max(vi + dp[j - wi], dp[j])

    print(dp[-1])
main()
### BUGGY CODE ###

from collections import defaultdict
N = int(input())
A = [int(i) for i in input().split()]
P = []
H = defaultdict(list)
for i, v in enumerate(A):
    H[i+v].append(i)
    P.append((i, i-v))
ans = 0

for i, v in P:
    for j in H[v]:
        if i > j:
            ans += 1
print(ans)

### FIXED CODE ###

from collections import defaultdict
N = int(input())
A = [int(i) for i in input().split()]
H = defaultdict(int)
ans = 0
for i, v in enumerate(A):
    ans += H[i-v]
    H[i+v] += 1
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
n,m,k=map(int,input().split())
friend=[[] for _ in range(n)]
block=[[False]*n for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    friend[a].append(b)
    friend[b].append(a)
for _ in range(k):
    c,d=map(int,input().split())
    c-=1
    d-=1
    block[c][d]=True
    block[d][c]=True

def dfs(graph,v,s):
    seen[v]=True
    if not block[s][v]:
        count[s]+=1
    for nv in graph[v]:
        if seen[nv]:
            continue
        dfs(graph,nv,s)
count=[0]*n
for v in range(n):
    seen=[False]*n
    temp=0
    if seen[v]:
        continue
    dfs(friend,v,v)
    count[v]-=1
    count[v]-=len(friend[v])

for i in range(n):
    print(count[i],end=' ')

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
n,m,k=map(int,input().split())
friend=[[] for _ in range(n)]
block=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    friend[a].append(b)
    friend[b].append(a)
for _ in range(k):
    c,d=map(int,input().split())
    c-=1
    d-=1
    block[c].append(d)
    block[d].append(c)
seen=[-1]*n
def dfs(graph,v,top):
    seen[v]=top
    top_count[top]+=1
    for nv in graph[v]:
        if seen[nv]!=-1:
            continue
        dfs(graph,nv,top)
top=0
top_count=[0]
for v in range(n):
    count=0
    if seen[v]!=-1:
        continue
    dfs(friend,v,top)
    top_count.append(0)
    top+=1


for i in range(n):
    ans=top_count[seen[i]]-len(friend[i])-1
    cnt=0
    for v in block[i]:
        if seen[v]==seen[i]:
            cnt+=1
    ans-=cnt
    print(ans,end=' ')
### BUGGY CODE ###

# -*- coding utf-8 -*-
MOD = 10 ** 9 + 7

S = input()
# S = '?' * 10000
mods = [0] * 13
mods[0] = 1

digit = 1
for s in S[::-1]:
    next_mods = [0] * 13
    if s == '?':
        for i in range(10):
            for m in range(13):
                next_mods[(m + i * digit) % 13] += mods[m]
    else:
        for m in range(13):
            next_mods[(m + int(s) * digit) % 13] += mods[m]

    for m in range(13):
        next_mods[m] %= MOD
    mods = next_mods
    digit *= 10
    digit %= 13

ans = mods[5]

print(ans)


### FIXED CODE ###

# -*- coding utf-8 -*-
MOD = 10 ** 9 + 7

S = input()
# S = '?' * 100000
mods = [0] * 13
mods[0] = 1

digit = 1
for s in S[::-1]:
    next_mods = [0] * 13
    if s == '?':
        for i in range(10):
            for m in range(13):
                next_mods[(m + i * digit) % 13] += mods[m]
    else:
        for m in range(13):
            next_mods[(m + int(s) * digit) % 13] += mods[m]

    for m in range(13):
        next_mods[m] %= MOD
    mods = next_mods
    digit *= 10
    digit %= 13    # this line dramatically reduces calculation time

ans = mods[5]

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

n = int(input())
s = input()
words = [[0]*3for _ in range(n)] #i以降のR,G,Bの数(i含まず)
for i in range(n-2,-1,-1):
    if s[i+1] == 'R':
        words[i][0]+=1
    elif s[i+1] == 'G':
        words[i][1] +=1
    else:words[i][2] +=1
    words[i][0] +=words[i+1][0]
    words[i][1] +=words[i+1][1]
    words[i][2] +=words[i+1][2]
ans = 0
for i in range(n):
    for j in range(i+1,n):
        
        if s[i] == 'R':
            if s[j] == 'G':
                ans += words[j][2]
                if j+j-i >n-1:continue
                if s[j+(j-i)] == 'B':ans-=1
            if s[j] == 'B':
                ans += words[j][1]
                if j+j-i >n-1:continue
                if s[j+(j-i)] == 'G':ans-=1
        if s[i] == 'G':
            if s[j] == 'R':
                ans += words[j][2]
                if j+j-i >n-1:continue
                if s[j+(j-i)] == 'B':ans-=1
            if s[j] == 'B':
                ans += words[j][0]
                if j+j-i >n-1:continue
                if s[j+(j-i)] == 'R':ans-=1
        if s[i] == 'B':
            if s[j] == 'G':
                ans += words[j][0]
                if j+j-i >n-1:continue
                if s[j+(j-i)] == 'R':ans-=1
            if s[j] == 'R':
                ans += words[j][1]
                if j+j-i >n-1:continue
                if s[j+(j-i)] == 'G':ans-=1
print(ans)
 


        

        

        
        
    

### FIXED CODE ###

n = int(input())
s = input()
words = [[0]*3for _ in range(n)] #i以降のR,G,Bの数(i含まず)
for i in range(n-2,-1,-1):
    if s[i+1] == 'R':
        words[i][0]+=1
    elif s[i+1] == 'G':
        words[i][1] +=1
    else:words[i][2] +=1
    words[i][0] +=words[i+1][0]
    words[i][1] +=words[i+1][1]
    words[i][2] +=words[i+1][2]
ans = 0
for i in range(n):
    for j in range(i+1,n):
        
        if s[i] == 'R':
            if s[j] == 'G':
                ans += words[j][2]
                if j+j-i >n-1:continue
                if s[j+(j-i)] == 'B':ans-=1
            if s[j] == 'B':
                ans += words[j][1]
                if j+j-i >n-1:continue
                if s[j+(j-i)] == 'G':ans-=1
        if s[i] == 'G':
            if s[j] == 'R':
                ans += words[j][2]
                if j+j-i >n-1:continue
                if s[j+(j-i)] == 'B':ans-=1
            if s[j] == 'B':
                ans += words[j][0]
                if j+j-i >n-1:continue
                if s[j+(j-i)] == 'R':ans-=1
        if s[i] == 'B':
            if s[j] == 'G':
                ans += words[j][0]
                if j+j-i >n-1:continue
                if s[j+(j-i)] == 'R':ans-=1
            if s[j] == 'R':
                ans += words[j][1]
                if j+j-i >n-1:continue
                if s[j+(j-i)] == 'G':ans-=1
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
track = []
for i in range(N):
  if A[i] in track:
    print('NO')
    exit()
  else:
    track.append(A[i])
print('YES')

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = set(A)
if sorted(A) == sorted(B):
  print('YES')
else:
  print('NO')
### BUGGY CODE ###

N,K=map(int,input().split())
A=set(map(int,input().split()))
import numpy as np
a=np.array([1 if i in A else 0 for i in range(1,K+1)])
d=np.zeros(K+1)
for i in range(K):
    if d[i]==0:
        d[i+1:]+=a[:K-i]
print(['Second','First'][d[K]>0])

### FIXED CODE ###

N,K=map(int,input().split())
A=sorted(map(int,input().split()))
d=[0]*(K+1)
for i in range(K):
    x=d[i]^1
    if x:
        for a in A:
            if i+a<K+1:
                d[i+a]=x
print(['Second','First'][d[-1]])
### BUGGY CODE ###

mod=998244353
n,s=map(int,input().split())
arr=list(map(int,input().split()))
dp=[[0]*(s+1) for _ in range(n+1)]
dp[0][0]=1
for i in range(1,n+1):
  val=arr[i-1]
  for j in range(s,-1,-1):
    dp[i][j]=2*dp[i-1][j]
    dp[i][j]%=mod
    if j-val>=0 and dp[i-1][j-val]!=0:
      dp[i][j]+=dp[i-1][j-val]
      dp[i][j]%=mod
print(dp[n][s])

### FIXED CODE ###

mod = 998244353
n, s = map(int, input().split())
arr = list(map(int, input().split()))
dp = [[0] * (s + 1) for _ in range(n + 1)]
dp[0][0] = 1

for i in range(1, n + 1):
    var = arr[i - 1]
    for j in range(0, s + 1):
        dp[i][j] = 2 * dp[i - 1][j]
        dp[i][j] %= mod
        if j - var >= 0 and dp[i - 1][j - var] != 0:
            dp[i][j] += dp[i - 1][j - var]
            dp[i][j] %= mod
print(int(dp[n][s]))
### BUGGY CODE ###

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

point = 1
points = []
for i in range(n):
    point *= a[i]
    if i >= k - 1:
        points.append(point)
        if i >= k:
            if points[-1] > points[-2]:
                print("Yes")
            else:
                print("No")
        point //= a[i - k + 1]

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
"""
point = 1
points = []

for i in range(n):
    point *= a[i]
    if i >= k - 1:
        points.append(point)
        if i >= k:
            if points[-1] > points[-2]:
                print("Yes")
            else:
                print("No")
        point //= a[i - k + 1]
"""
for i in range(n):
    if i >= k:
        if a[i] > a[i - k]:
            print("Yes")
        else:
            print("No")
### BUGGY CODE ###

n, m = list(map(int, input().split()))
results = []
if m:
    results = [input().split() for _ in range(m)]
ac = {}
wa = {}
cnt_ac = 0
cnt_wa = 0
for res in results:
    if res[1] == "AC":
        if not res[0] in ac.keys():
            cnt_ac += 1
            ac[res[0]] = "AC"
            if res[0] in wa.keys():
                cnt_wa += wa[res[0]]
    elif not res[0] in ac.keys():
        if res[0] in wa.keys():
            wa[res[0]] += 1
        else:
            wa[res[0]] = 1
print(cnt_ac, cnt_wa)

### FIXED CODE ###

N,M=map(int,input().split())
AC=[0]*N
WA=[0]*N
wa=0
for i in range(M):
  p,s=input().split()
  p=int(p)-1
  if AC[p]==0 and s=="AC":
  	AC[p]=1
  	wa+=WA[p]
  WA[p]+=1
print(sum(AC),wa)
### BUGGY CODE ###

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

P=[]
Y=[]
for i in range(M):
	P_tmp,Y_tmp = map(int, raw_input().split())
	P.append(P_tmp)
	Y.append(Y_tmp)

S={}

for i in Y:
	key = str(P[Y.index(i)]) + "_"
	#print "key: "+key
	try:
		S[key]
	except:
		S[key]=[]
	S[key].append(i)

for i in S.keys():
	S[i]=sorted(S[i])

#print S

for i in Y:
	key = str(P[Y.index(i)]) + "_"
	print "{0:06d}".format(P[Y.index(i)]) + "{0:06d}".format(S[key].index(i)+1)



### FIXED CODE ###

from collections import defaultdict as dd
 
d=dd(int)
n,m=map(int,input().split())
l=[[i]+list(map(int,input().split()))+[0] for i in range(m)]
 
o=sorted(l,key=lambda x:x[2])
for i,j in enumerate(o):
  d[j[1]]+=1
  o[i][3]=d[j[1]]
 
for i in sorted(o):
  print('{0:06d}'.format(i[1])+'{0:06d}'.format(i[3]))
### BUGGY CODE ###

n = int(input())
s = []
ans = []

for i in range(n):
    s.append(input())

for i in range(n):
    temp = []
    for j in range(len(s[i])):
        temp.append(s[i][j])

    ans.append(''.join(sorted(temp)))

#ans.sort()
temp = ans[0]

# if ans.count(temp) == 1:
#     count = 0
# else:
#     count = ans.count(temp)
count = 0
setV = set()

for i in range(n):
    if ans.count(ans[i]) > 1:
        if ans[i] in setV:
            continue
        else:
            num = ans.count(ans[i])
            count += (num * (num-1))/2
            setV.add(ans[i])

print(int(count))


### FIXED CODE ###

import itertools

n = int(input())
s = []
textSet = set()
ans = 0

for i in range(n):
    s.append(''.join(sorted(input())))

s.sort()

# print(s)
cnt = 0

for i in range(1, n):
    if s[i] == s[i-1]:
        cnt += 1
    elif cnt > 0:
        # ans += cntC2
        # ans += len(list(itertools.combinations(range(cnt+1), 2)))
        ans += (cnt + 1) * cnt // 2
        cnt = 0

if cnt > 0:
    # ans += len(list(itertools.combinations(range(cnt + 1), 2)))
    ans += (cnt + 1) * cnt // 2

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

import bisect
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort()
b.sort()
c.sort()
ans=0
for i in range(n):
  j=bisect.bisect_left(b,a[i]+1)
  if j>=n:
    break
  for k in range(j,n):
    l=bisect.bisect_left(c,b[k]+1)
    if l>=n:
      break
    ans+=n-l
print(ans)

### FIXED CODE ###

import bisect
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort()
b.sort()
c.sort()
ans=0
for i in range(n):
  j=bisect.bisect_left(a,b[i])
  k=n-bisect.bisect_right(c,b[i])
  ans+=j*k
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
for i in range(n,m):
    if m%i:continue
    print(m//i);exit()
print(1)

### FIXED CODE ###

n,m=map(int,input().split())
ans=1
ps=[]
for i in range(1,int(m**(1/2))+1):
    if m%i:continue
    if n*(i)<=m:ans=max(i,ans)
    if n*(m//i)<=m:ans=max(ans,m//i)
print(ans)
### BUGGY CODE ###

import collections

N, M = map(int, input().split())
bridges = reversed([[int(i) for i in input().split()] for i in range(M)])

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    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 union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            _y = self.par[y]
            for i in range(N):
              if self.par[i] == _y: self.par[i] = x

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

def solve():
  uf = UnionFind(N)
  ans = [str(N * (N - 1) // 2)]
  for bridge in bridges:
    uf.union(bridge[0] - 1, bridge[1] - 1)
    C = collections.Counter(uf.par)
    n = N
    a = 0
    for c in C.values():
      n -= c
      a += n * c
    ans.append(str(a))
  ans.pop(-1)
  return '\n'.join(reversed(ans))

print(solve())


### FIXED CODE ###

class UnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数

    def root(self, x): #root(x): xの根ノードを返す．
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x]) #xをxの根に直接つなぐ
            return self.parent[x]

    def merge(self, x, y): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]: #xの要素数がyの要素数より「小さい」とき入れ替える
            x,y=y,x
        self.parent[x] += self.parent[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True

    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue
        return self.root(x) == self.root(y)

    def size(self,x): #size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]

def solve():
    N, M = map(int, input().split())
    bridges = [[int(i) - 1 for i in input().split()] for i in range(M)]
    ans = [N * (N - 1) // 2]

    uf = UnionFind(N)
    for bridge in reversed(bridges):
        A, B = bridge
        if uf.issame(A, B):
            ans.append(ans[-1])
        else:
            ans.append(ans[-1] - uf.size(A) * uf.size(B))
            uf.merge(A, B)
    ans.pop(-1)
    return '\n'.join(map(str, reversed(ans)))

print(solve())
### BUGGY CODE ###

S = input()

from collections import deque

q = deque()
q.append(S)
#ここに、次にチェックする文字列を入れていく
#今回はque(fi-fo)として使うので、popleftを使う

flag = False
while(q):
  nows = q.popleft()
  if len(nows) <= 4: continue
    #残りが4文字以下だと絶対違う
    #またほっとくと添字バグが起きる
  if nows[0:5] == 'dream':
    if nows[5:] == '':
      flag = True
      break
    else: q.append(nows[5:])
    if nows[0:7] == 'dreamer':
      if nows[7:] == '':
        flag = True
        break
      else: q.append(nows[7:])
  elif nows[0:5] == 'erase':
    if nows[5:] == '':
        flag = True
        break
    else: q.append(nows[5:])
    if nows[0:6] == 'eraser':
      if nows[6:] == '':
        flag = True
        break
      else: 
        q.append(nows[6:])

print('YES' if flag else 'NO')

### FIXED CODE ###

S = input()

from collections import deque

q = deque()
if len(S) > 5: #4文字以下ならそもそもバツ→入れない
  q.append((len(S), S))
#ここに、次にチェックする文字列を入れていく
#今回はque(fi-fo)として使うので、popleftを使う

flag = False
while(q):
  nowlen, nows = q.popleft()
  nows5 = nows[0:5]
  nowsfrom5 = nows[5:]
  if nows5 == 'dream':
    if nowlen == 5:
      flag = True
      break
    else:
      if nowlen>=10: q.append((nowlen-5, nowsfrom5))
    if nows[0:7] == 'dreamer':
      if nowlen == 7:
        flag = True
        break
      else:
        if nowlen>=12: q.append((nowlen-7, nows[7:]))
  elif nows5 == 'erase':
    if nowlen == 5:
        flag = True
        break
    else:
      if nowlen>=10: q.append((nowlen-5, nowsfrom5))
    if nows[0:6] == 'eraser':
      if nowlen == 6:
        flag = True
        break
      else: 
        if nowlen>=11: q.append((nowlen-6, nows[6:]))

print('YES' if flag else 'NO')