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

N,A,B = map(int, input().split())
red=0
blue=0
count=0

for i in range(N):

  if count == A+B:
      count=0

  if A!=0 and count < A :
      blue+=1
      count+=1
  elif count < A + B:
      red+=1
      count+=1

print(blue)

### FIXED CODE ###

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

if N%(A+B) <= A:
    print(int(int(N/(A+B))*A+N%(A+B)))
else:
    print(int(int(N/(A+B))*A+A))
### BUGGY CODE ###

N = int(input())
L = []
for i in range(N):
    S = input()
    if not(S in L):
        L.append(S)

#print(L)
print(len(L))

### FIXED CODE ###

N = int(input())
L = []
for i in range(N):
    S = input()
#    if not(S in L):
    L.append(S)

print(len(set(L)))
### BUGGY CODE ###

N = int(input())
count = 0

for i in range(357, N+1):

    i_str = str(i)
 
    thr = i_str.count("3")
    fiv = i_str.count("5")
    sev = i_str.count("7")


    if len(i_str) == thr + fiv + sev:
        if thr > 0:
             if fiv > 0:
                if sev > 0: 
                    count += 1

print(count)


### FIXED CODE ###

from itertools import product

N = int(input())
num_list = ["3", "5", "7"]
count = 0

for i in range(3, 10):
    for t in (product(num_list, repeat=i)):
        check = t.count("3")*t.count("5")*t.count("7")
        if int("".join(t)) <= N and check:
            count += 1


print(count)
### BUGGY CODE ###

a1,b1,a2,b2=map(int,input().split())

import sys
sys.setrecursionlimit(2000000000)

p = 10 ** 9 + 7
N = a2+b2+2  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
  fact.append((fact[-1] * i) % p)
  inv.append((-inv[p % i] * (p // i)) % p)
  factinv.append((factinv[-1] * inv[-1]) % p)

def comb(n, r, p):
  if (r < 0) or (n < r):
    return 0
  r = min(r, n - r)
  return fact[n] * factinv[r] * factinv[n-r] % p



score=comb(a2+b2+2,a2+1,p)-comb(a2+b1+1,a2+1,p)-comb(a1+b2+1,a1,p)+comb(a1+b1,a1,p)
print(score%(10**9+7))

### FIXED CODE ###

a1,b1,a2,b2=map(int,input().split())

import sys
sys.setrecursionlimit(2000000000)

p = 10 ** 9 + 7
N = a2+b2+2  # N は必要分だけ用意する
R = max(a2+1,b2+1)
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
  fact.append((fact[-1] * i) % p)
  
for i in range(2, R + 1):
  inv.append((-inv[p % i] * (p // i)) % p)
  factinv.append((factinv[-1] * inv[-1]) % p)

def comb(n, r, p):
  if (r < 0) or (n < r):
    return 0
  r = min(r, n - r)
  return fact[n] * factinv[r] * factinv[n-r] % p

score=comb(a2+b2+2,a2+1,p)-comb(a2+b1+1,a2+1,p)-comb(a1+b2+1,a1,p)+comb(a1+b1,a1,p)
print(score%(10**9+7))
### BUGGY CODE ###

x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
p.sort(reverse = True)
q.sort(reverse = True)
del p[x:]
del q[y:]
for k in range(c):
    if r[k] > p[x - 1] or r[k] > q[y - 1]:
        if p[x - 1] >= q[y - 1]:
            q[y - 1] = r[k]
        elif p[x - 1] < q[y - 1]:
            p[x - 1] = r[k]
    p.sort(reverse = True)
    q.sort(reverse = True)
print(sum(p) + sum(q))                      


### FIXED CODE ###

x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))
p.sort(reverse = True)
q.sort(reverse = True)
del p[x:]
del q[y:]
t = p + q + r
t.sort(reverse = True)
del t[(x + y):]
print(sum(t))
### BUGGY CODE ###

n = int(input())
s = input()

c = s.count('R') * s.count('G') * s.count('B')

for i in range(n):
    for j in range(i+1,n):
        k = 2 * j - i
        if(k <= j or k >= n):continue
        if(s[i] != s[j] and s[j] != s[k] and s[i] != s[k]):c -= 1

print(c)

### FIXED CODE ###

n = int(input())
s = input()
d = [0,0,0]
for i in s:
    if(i == 'R'):d[0] += 1
    elif(i == 'G'):d[1] += 1
    elif(i == 'B'):d[2] += 1
c = d[0] * d[1] * d[2]

for i in range(n):
    for j in range(i+1,n):
        k = 2 * j - i
        if(k >= n):continue
        if(s[i] == s[j]):continue
        if(s[j] == s[k]):continue
        if(s[i] == s[k]):continue
        c -= 1

print(c)
### BUGGY CODE ###

H, N = map(int, input().split())
A = {}
B = {}
for i in range(N):
    a, b = map(int, input().split())
    A.update({i : a})
    B.update({i : b})
dp = dict(zip(range(10001), [10000000000] * 10001))
dp.update({0 : 0})
for i in range(N):
    for j in range(10001):
        next = min(j + A[i], H)
        dp.update({next : (min(dp[next], dp[j] + B[i]))})
print(dp[H])


### FIXED CODE ###

H, N = map(int, input().split())
A = []
B = []
for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
dp = [10000000000] * 10001
dp[0] = 0
for i in range(N):
    for j in range(10001):
        next = min(j + A[i], H)
        dp[next] = min(dp[next], dp[j] + B[i])
print(dp[H])
### BUGGY CODE ###

r,g,b,n = map(int,input().split())
cnt = 0
for i in range(0,n//r + 1):
    for j in  range(0,n//g + 1):
        if (n - i*r - j*g)%b == 0 and (n - i*r - j*g)/b >= 0:
            cnt += 1
print(cnt)

### FIXED CODE ###

r,g,b,n = map(int,input().split())
cnt = 0
for i in range(0,n+1,r):
    for j in range(0,n+1-i,g):
        if (n - i - j)%b == 0 and (n - i - j)%b >= 0:
            cnt += 1
print(cnt)
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

h,w,m = inpl()
yd = []
for i in range(h):
    yd.append([i,0])
xd = []
for i in range(w):
    xd.append([i,0])
s = [[False]*w for _ in range(h)]

for _ in range(m):
    a,b = inpl()
    yd[a-1][1] += 1
    xd[b-1][1] += 1
    s[a-1][b-1] = True
yd.sort(key = lambda x:x[1], reverse = True)
xd.sort(key = lambda x:x[1], reverse = True)
ymax = yd[0][1]
yl = []
for i,x in yd:
    if x != ymax: break
    yl.append(i)
xmax = xd[0][1]
xl = []
for i,x in xd:
    if x != xmax: break
    xl.append(i)
res = ymax + xmax - 1
for i in yl:
    fl = False
    for j in xl:
        if not s[i][j]:
            res += 1
            fl = True
            break
    if fl: break
print(res)

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

h,w,m = inpl()
yd = []
for i in range(h):
    yd.append([i,0])
xd = []
for i in range(w):
    xd.append([i,0])
se = set()
def ind(i,j):
    return i*w + j
for _ in range(m):
    a,b = inpl()
    yd[a-1][1] += 1
    xd[b-1][1] += 1
    se.add((a-1,b-1))
yd.sort(key = lambda x:x[1], reverse = True)
xd.sort(key = lambda x:x[1], reverse = True)
ymax = yd[0][1]
yl = []
for i,x in yd:
    if x != ymax: break
    yl.append(i)
xmax = xd[0][1]
xl = []
for i,x in xd:
    if x != xmax: break
    xl.append(i)
res = ymax + xmax - 1
# print(yl,xl,res)
for i in yl:
    for j in xl:
        if not (i,j) in se:
            res += 1
            print(res)
            quit()
print(res)
### BUGGY CODE ###

LARGE = 998244353


def solve(n):
    r = 0
    mck = 1
    for k in range(n // 2):
        r += mck * pow(2, k, LARGE)
        r %= LARGE
        mck *= n - k
        mck *= pow(k + 1, LARGE - 2, LARGE)
        mck %= LARGE
    res = (pow(3, n, LARGE) - (2 * r)) % LARGE
    return res


def main():
    n = int(input())
    res = solve(n)
    print(res)


def test():
    assert solve(2) == 7
    assert solve(10) == 50007
    # assert solve(1000000) == 210055358


if __name__ == "__main__":
    test()
    main()


### FIXED CODE ###

LARGE = 998244353


def solve(n):
    r = 0
    mck = 1
    factorial_n = 1
    factorial_inv = [0] * (n + 1)
    factorial_inv[0] = 1
    for i in range(1, n + 1):
        factorial_n *= i
        factorial_n %= LARGE
    factorial_inv[-1] = pow(factorial_n, LARGE - 2, LARGE)
    for i in range(n):
        factorial_inv[n - i - 1] = (factorial_inv[n - i] * (n - i)) % LARGE
    pow_2 = 1
    for k in range(n // 2):
        r += factorial_n * factorial_inv[n - k] * factorial_inv[k] * pow_2
        r %= LARGE
        pow_2 *= 2
        pow_2 %= LARGE
    res = (pow(3, n, LARGE) - (2 * r)) % LARGE
    return res


def main():
    n = int(input())
    res = solve(n)
    print(res)


def test():
    assert solve(2) == 7
    assert solve(10) == 50007
    # assert solve(1000000) == 210055358


if __name__ == "__main__":
    test()
    main()
### BUGGY CODE ###

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

left = 0
right = n - 1
ans = 0

for i in range(n):
    left = 0
    right = n - 1
    while left <= right:
        if i == left == right:
            left, right = left + 1, right - 1
            continue

        elif i == left:
            if a[i] % a[right] == 0:
                break

        elif i == right:
            if a[i] % a[left] == 0:
                break

        else:
            if a[i] % a[left] == 0 or a[i] % a[right] == 0:
                break

        left, right = left + 1, right - 1

    if left > right:
        ans += 1

print(ans)


### FIXED CODE ###

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

ans = 0
dp = [0] * (a[-1] + 1)

for i in range(n):
    tmp = a[i]
    while tmp <= a[-1]:
        dp[tmp] += 1
        tmp += a[i]

for i in a:
    if dp[i] == 1:
        ans += 1

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

from functools import reduce

n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
ans = 0

def gcd(a, b):
    # 大きい方を被除数、小さい方を除数とする
    dividend = max(a, b)
    divider = min(a, b)

    if divider == 0:
        return dividend

    # 最大公約数を見つけるまで繰り返す
    while dividend % divider != 0:
        # 除算を行い、その除数を次回の被除数、剰余を次回の除数として処理を繰り返す
        r = dividend % divider
        dividend = divider
        divider = r

    # 一方がもう一方を割り切れた時点で、その除数を最大公約数とみなせる
    return divider


def lcm(a, b):
    return (a * b) // gcd(a, b)

a.sort(reverse=True)
v1, v2 = None, None
L = None

# if len(a) > 1:
#     v1 = a[0]
#     v2 = a[1]
#     L = lcm(v1, v2)
#     # print(L)
# else:
#     L = reduce(lcm, a)

L = reduce(lcm, a)

# print(L)

for i in range(n):
    ans += (L // a[i])
    # ans %= mod

print(ans % mod)

### FIXED CODE ###

from functools import reduce

n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
ans = 0

def gcd(a, b):
    # 大きい方を被除数、小さい方を除数とする
    dividend = max(a, b)
    divider = min(a, b)

    if divider == 0:
        return dividend

    # 最大公約数を見つけるまで繰り返す
    while dividend % divider != 0:
        # 除算を行い、その除数を次回の被除数、剰余を次回の除数として処理を繰り返す
        r = dividend % divider
        dividend = divider
        divider = r

    # 一方がもう一方を割り切れた時点で、その除数を最大公約数とみなせる
    return divider


def lcm(a, b):
    return (a * b) // gcd(a, b)

def modinv(x):
    return pow(x, mod-2, mod)

b = list(set(a))
# for i in range(n):

# L = reduce(lcm, a)
L = reduce(lcm, b)

# print(L)

for i in range(n):
    # ans += (L // a[i])
    ans += L * modinv(a[i])

print(ans % mod)
### BUGGY CODE ###

n=int(input())
s=[]
p=[]
for i in range(n):
    a=input()
    if not a in s:
        s.append(a)
        p.append(1)
    else:
        p[s.index(a)]=(p[s.index(a)]+1)%2
print(sum(p))

### FIXED CODE ###

from collections import Counter
n=int(input())
s=[int(input())for i in range(n)]
d=Counter(s)
c=0
for a,b in d.items():
    if b%2==1:
        c+=1
print(c)
### BUGGY CODE ###

n = int(input())
s = str(input())

s_r = []
s_g = []
s_b = []

for i in range(n):
  if s[i] == "R":
    s_r.append(i)
  elif s[i] == "G":
    s_g.append(i)
  else:
    s_b.append(i)

def conditions(a, b):
  if (a+b) % 2 == 0:
    x = (a+b) / 2
    y = 2*b - a
    z = 2*a - b
  else:
    x = -1
    y = 2*b - a
    z = 2*a - b
  return (x, y, z)
  
count = 0
for item in s_r:
  for item2 in s_g:
    for i in conditions(item, item2):
      if i in s_b:
        count += 1
    
ans = len(s_r) * len(s_g) * len(s_b) - count
print(ans)

### FIXED CODE ###

import collections

n = int(input())
s = str(input())

aaa = collections.Counter(s)
s_r = aaa["R"]
s_g = aaa["G"]
s_b = aaa["B"]

def noteq(a, b, c):
  if a != b and b != c and c != a:
    return True
  else:
    return False

ans = s_r * s_g * s_b

for i in range(n):
  for d in range(n):
    j = i + d
    k = j + d
    if k >= n:
      break;
    else:
      a = s[i]
      b = s[j]
      c = s[k]
      if noteq(a, b, c):
        ans -= 1
    
print(ans)
### BUGGY CODE ###

# 初期入力
N = int(input())

N_list =[i for i in range(1,N+1)]
ans =sum(N_list) -N
print(ans)

### FIXED CODE ###

# 初期入力
N = int(input())

#N_list =[i for i in range(1,N+1)]
N_list_sum =N*(N+1)//2
ans =N_list_sum -N
print(ans)
### BUGGY CODE ###

import sys
s = input()
t = input()
table = [[len(s) for i in range(len(s))] for j in range(26)]

for i in range(len(s)):
  table[ord(s[i])-97][i] = 0
for i in range(26):
  for j in range(len(s)):
    table[i][len(s)-j-2] = min(table[i][len(s)-j-1] +1, table[i][len(s)-j-2])
  for j in range(len(s)):
    table[i][len(s)-j-2] = min(table[i][len(s)-j-1] +1, table[i][len(s)-j-2])

for letter in t:
  if s.find(letter) == -1:
    print(-1)
    sys.exit()
    
place = 0
ans = 0
for i in range(len(t)):
  letter = t[i]
  move = table[ord(t[i])-97][place]
  ans += move + 1
  place = (place + move+1)%len(s)
print(ans)

### FIXED CODE ###

import sys
s = input()
t = input()
table = [[len(s) for i in range(len(s))] for j in range(26)]
sset = set(s)
tset = set(t)
for i in range(len(s)):
  table[ord(s[i])-97][i] = 0
for letter in sset:
  i = ord(letter) - 97
  for j in range(len(s)):
    table[i][len(s)-j-2] = min(table[i][len(s)-j-1] +1, table[i][len(s)-j-2])
  for j in range(len(s)):
    if table[i][len(s)-j-2] < len(s): break
    table[i][len(s)-j-2] = min(table[i][len(s)-j-1] +1, table[i][len(s)-j-2])

if tset - sset:
  print(-1)
  sys.exit()
    
place = 0
ans = 0
for i in range(len(t)):
  letter = t[i]
  move = table[ord(t[i])-97][place]
  ans += move + 1
  place = (place + move+1)%len(s)
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
light=list(map(int,input().split()))
for k in range(K):
  imo=[0]*(N+1)
  x=0
  for i in range(N):
    kido=light[i]
    imo[max(0,i-kido)]+=1
    imo[min(N-1,i+kido)+1]-=1
  for j in range(N):
    x+=imo[j]
    light[j]=x
  if N==min(light):
    break
print(*light)

### FIXED CODE ###

N,K=map(int,input().split())
light=list(map(int,input().split()))
for k in range(K):
  imo=[0]*(N+1)
  for i in range(N):
    l=max(0,i-light[i])
    r=min(N-1,i+light[i])+1
    imo[l]+=1
    imo[r]-=1
  for i in range(1,N):
    imo[i]+=imo[i-1]
  if light==imo:
    break
  else:
    light=imo[:]
print(*light[:-1])
### BUGGY CODE ###

import collections as c
N,K,*A= map(int,open(0).read().split())
ans=0
C=c.Counter(A)
C=sorted(C.values())

colors = len(C)

for i in range(colors):
  if len(C)<=K:
    break
  _c = C.pop(0)
  ans+=_c
print(ans)


### FIXED CODE ###

import collections as c
N,K,*A= map(int,open(0).read().split())
ans=0
C=c.Counter(A)
C=sorted(C.values())
#Aprint(C)
for i in range(len(C)-K):
  ans+=C[i]

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

L, R = list(map(int, input().split(' ')))
t = [i for i in range(L, R+1)]
s = t[0] % 2019
x = []
x.append(s)
for i in range(1, len(t)):
    m = t[i] % 2019
    if s == m:
        break
    x.append(m)
min_v = 2018
for i in range(0, len(x)):
    for j in range(i+1, len(x)):
        ij = (x[i]*x[j]) % 2019
        if ij < min_v:
            min_v = ij
print(min_v)

### FIXED CODE ###

import numpy as np
L, R = list(map(int, input().split(' ')))
x = []
x.append(L % 2019)
for i in range(L+1, R+1):
    m = i % 2019
    if x[0] == m:
        break
    x.append(m)
    
min_v = 2018
for i in range(0, len(x)-1):
    tmp = np.amin(np.mod([x[i]*x[j] for j in range(i+1, len(x))], 2019))
    if tmp < min_v:
        min_v = tmp

print(min_v)
### BUGGY CODE ###

import copy

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

for i in range(N):
    tmp = copy.deepcopy(X)
    del tmp[i]
    tmp = sorted(tmp)
    print(tmp[int((len(tmp)+1)/2)-1])

### FIXED CODE ###

import copy

N = int(input())
X = [int(i) for i in input().split()]
tmp = copy.deepcopy(X)

X = sorted(X)
for i in range(N):
    ans1 = X[int(len(X)/2)]
    ans2 = X[int(len(X)/2)-1]
    if tmp[i] < ans1:
        print(ans1)
    else:
        print(ans2)
### BUGGY CODE ###

n,m = map(int,input().split())
a = []
b = []
l = []
ans = 0
count = 0

for i in range(n):
	a_dash,b_dash = map(int,input().split())
	a.append(a_dash)
	b.append(b_dash)

c = zip(a,b)
c = sorted(c)
a,b = zip(*c)
a = list(a)
b = list(b)

for i in reversed(range(m)):
	for j in range(count,len(a)):
		if a[j] + i == m:
			l.append(b[j])
			count += 1
		else:
			break
	if len(l) != 0:
		ans += max(l)
		l.pop(l.index(max(l)))

print(ans)


### FIXED CODE ###

import sys
import heapq

s = sys.stdin.readlines()
n,m = map(int,s[0].split())
a = []
b = []
l = []
ans = 0
count = 0

for i in range(1,n+1):
	a_dash,b_dash = map(int,s[i].split())
	a.append(-a_dash)
	b.append(-b_dash)

c = zip(a,b)
c = sorted(c,reverse=True)
a,b = zip(*c)
a_length = len(a)

for i in reversed(range(m)):
	for j in range(count,a_length):
		if -a[j] + i == m:
			heapq.heappush(l,b[j])
			count += 1
		else:
			break
	if len(l) != 0:
		maximum = heapq.heappop(l)
		ans += maximum

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

N, Q = map(int, input().split())
S = input()
a = []
an = [0] * (N + 1)
for i in range(Q):
    a.append(list(map(int, input().split())))

for i in range(len(S) - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        an[i] = 1
# print(an)
for i in range(Q):
    print(an[a[i][0] - 1:a[i][1] - 1].count(1))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
a = []
an = [0] * (N + 1)
for i in range(Q):
    a.append(list(map(int, input().split())))

for i in range(len(S) - 1):
    an[i + 1] = an[i]
    if S[i:i + 2] == "AC":
        an[i + 1] += 1
for i in range(Q):
    print(an[a[i][1] - 1] - an[a[i][0] - 1])
### BUGGY CODE ###

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

ans = 0
for l in range(N-1):
    for r in range(l+1,N):
        ans += sorted(P[l:r+1])[-2]

print(ans)

### FIXED CODE ###

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

ind = [0]*(N+1)
for i in range(N):
    ind[P[i]] = i+1

ans = 0
l = [0] + [f for f in range(N+1)]
r = [f + 1 for f in range((N+1))] + [N+1]

for j in range(1,N+1):
    f = ind[j]

    l1 = l[f]
    l2 = l[l1]
    r1 = r[f]
    r2 = r[r1]
    ans += ((l1-l2)*(r1-f) + (f-l1)*(r2-r1))*j

    l[r1] = l1
    r[l1] = r1

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

# coding: utf-8

import math

cnt = 0
m = 0
G = []
def insertionSort(A, n, g):
    global cnt
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j = j - g
            cnt += 1
            A[j+g] = v
    return A
            
def shellSort(A, n):
    global m, G
    m = 1 if int(math.log(n, 2)) == 0 else int(math.log(n, 2)) 
    G = [2**x for x in range(m - 1, -1, -1)]
    for i in range(m):
        A = insertionSort(A, n, G[i])
    return A
    
n = int(input())
A = []
for i in range(n):
    A.append(int(input()))
    
A = shellSort(A, n)


print(m)
print(" ".join(map(str, G)))
print(cnt)
for i in range(n):
    print(A[i])

### FIXED CODE ###

# coding: utf-8

import math
import sys

def insertionSort(a, n, g):
    ct = 0
    for i in range(g, n):
        v = a[i]
        j = i - g
        while j >= 0 and a[j] > v:
            a[j+g] = a[j]
            j = j - g
            ct += 1
            a[j+g] = v
    return ct

n = int(input())
a = list(map(int, sys.stdin.readlines()))
cnt = 0
m = 0
h = 0
g = []

while True:
    h = 3*h + 1
    if h > n:
        break
    g.insert(0, math.ceil(h))

for i in g:
    cnt += insertionSort(a, n, i)

print(len(g))
print(*g, sep=" ")
print(cnt)
print(*a, sep="\n")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, m = [int(x) for x in input().split()]
g = [[] for _ in range(n)]

for _ in range(m):
    l, r, d = [int(x) for x in input().split()]
    l -= 1
    r -= 1
    g[l].append((r, d))
    g[r].append((l, -d))

d = [0] * n

for i in range(n):
    if d[i] != 0:
        continue
    stack = [i]
    while stack:
        u = stack.pop()
        for v, d_ in g[u]:
            if d[v] == 0 and v != i:
                d[v] = d[u] + d_
                stack.append(v)
            else:
                if d[v] != d[u] + d_:
                    print("No")
                    sys.exit()
    d[i] = 1
print("Yes")


### FIXED CODE ###

n, m = map(int, input().split())
ed = [[] for _ in range(n)]  # グラフ
v = [None] * n
for _ in range(m):
  l, r, d = map(int, input().split())
  ed[l-1].append((r-1, d))  # l -> r
  ed[r-1].append((l-1, -d))  # r -> l

visited = [False] * n  # 訪問フラグ（非連結の可能性の為）

def dfs(start):
  s = [start]
  v[start] = 0
  while s:
    label = s.pop()
    if visited[label] == False:
      visited[label] = True
      for to, dist in ed[label]:
        if v[to] is None:
          v[to] = v[label] + dist
          s.append(to)
        else:
          if v[to] != v[label] + dist:
            return False
  return True

is_exist = True
for i in range(n):
  if v[i] is None:
    if not dfs(i):
      print('No')
      is_exist = False
      break
if is_exist:
  print("Yes")
### BUGGY CODE ###

def find_index_by_value(a, val):
    for i, items in enumerate(a):
        if val in items:
            return i
    return -1


def num_reachable(n):
    return n * (n - 1) // 2


n, m = map(int, input().split())
edges = []

for _ in range(m):
    a, b = map(int, input().split())
    edges.append((a, b))

size = [1 for _ in range(n + 1)]
group = [i for i in range(n + 1)]


def find_group(x):
    p = x
    while True:
        pp = group[p]
        if pp == p:
            break
    return pp

ans = []
not_reachable = n * (n - 1) // 2
reachable_node = []
ans.append(not_reachable)

count = not_reachable
reachable = 0
for _ in range(m - 1):
    a, b = edges.pop()
    if count > 0:
        ra = find_group(a)
        rb = find_group(b)
        if rb != ra:
            s_ra = size[ra]
            s_rb = size[rb]
            new_size = s_ra + s_rb
            reachable += num_reachable(new_size) - num_reachable(s_ra) - num_reachable(s_rb)
            size[ra] = new_size
            group[rb] = ra
        count = not_reachable - reachable
    ans.append(count)

for _ in range(len(ans)):
    print(ans.pop())

### FIXED CODE ###

def find_index_by_value(a, val):
    for i, items in enumerate(a):
        if val in items:
            return i
    return -1


def num_reachable(n):
    return n * (n - 1) // 2


n, m = map(int, input().split())
edges = []

for _ in range(m):
    a, b = map(int, input().split())
    edges.append((a, b))

size = [1 for _ in range(n + 1)]
group = [i for i in range(n + 1)]


def find_group(x):
    c = []
    p = x
    while True:
        pp = group[p]
        if pp == p:
            break
        else:
            c.append(p)
            p = pp
    for i in c:
        group[i] = pp
    return pp

# find_group = lambda x: x if x == group[x] else find_group(group[x])

ans = []
not_reachable = n * (n - 1) // 2
reachable_node = []
ans.append(not_reachable)

count = not_reachable
reachable = 0
for _ in range(m - 1):
    a, b = edges.pop()
    if count > 0:
        ra = find_group(a)
        rb = find_group(b)
        if rb != ra:
            s_ra = size[ra]
            s_rb = size[rb]
            new_size = s_ra + s_rb
            reachable += num_reachable(new_size) - num_reachable(s_ra) - num_reachable(s_rb)
            size[ra] = new_size
            group[rb] = ra
        count = not_reachable - reachable
    ans.append(count)

for _ in range(len(ans)):
    print(ans.pop())