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

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

b = str(bin(mod-2))[2:]
blis = []
for _ in range(len(b)):
  if b[-_-1] == '1':
    blis.append(_)

def modinv(a):
  if a == 1:
    return 1
  else:
    res = 1
    n = len(b)
    li = []
    for _ in range(n):
      li.append(a%mod)
      a = a*a
    for item in blis:
      res = res * li[item] %mod
    return res
      

if N == 1:
  print(M)
  exit()

m = [1]
s = 1
for _ in range(N-1):
  s = s*(M-1)%mod
  m.append(s)

ncombi = [1]
c = 1
for k in range(K):
  c = c*(N-1-k)*modinv(k+1)
  c %= mod
  ncombi.append(c)

ans = 0
for k in range(K+1):
  ans = ans + m[-k -1]*ncombi[k]
  ans %= mod

ans = ans*M%mod

print(ans)

### FIXED CODE ###

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

inv = [0,1]
for i in range(2, N):
  inv.append((-inv[mod%i]*(mod//i))%mod)

if N == 1:
  print(M)
  exit()

m = [1]
s = 1
for _ in range(N-1):
  s = s*(M-1)%mod
  m.append(s)

ncombi = [1]
c = 1
for k in range(K):
  c = c*(N-1-k)*inv[k+1]
  c %= mod
  ncombi.append(c)

ans = 0
for k in range(K+1):
  ans = ans + m[-k -1]*ncombi[k]
  ans %= mod

ans = ans*M%mod
print(ans)
### BUGGY CODE ###

import math
N = int(input())
ans = 2
tp, ap = 0, 0
for i in range(N):#ans以上での比からの最小値でans更新,
    #A+Tのn倍、ただしn>=ans/(t+a)
    t, a = map(int, input().split())
    k = 1
    while True:
        if t*k>=tp and a*k>=ap:
            t, a = t*k, a*k
            break
        k += 1
    c = math.ceil(ans/(t+a))
    while True:#ansが前回のans以上になるようにする
        if (t+a)*c >= ans:
            ans = (t+a)*c
            break
        c += 1
    tp, ap = t*c, a*c
print(ans)

### FIXED CODE ###

n = int(input())
t = []
a = []
for i in range(n):
    c = list(map(int,input().split()))
    t.append(c[0])
    a.append(c[1])
for i in range(n-1):
    d = max(1,-(-t[i]//t[i+1]),-(-a[i]//a[i+1]))
    t[i+1] =t[i+1]*d
    a[i+1] =a[i+1]*d
print(t[-1]+a[-1])
### BUGGY CODE ###

import numpy as np
N,M=map(int,input().split())
A=[int(x) for x in input().split()]
A.sort(reverse=True)

for i in range(0,M):
    A[np.argmax(A)]=int(A[np.argmax(A)]/2)

print(sum(A))

### FIXED CODE ###

import heapq
N,M=map(int,input().split())
A=list(map(lambda x:int(x)*(-1),input().split()))
heapq.heapify(A)
    
for i in range(0,M):
    tmp=heapq.heappop(A)
    heapq.heappush(A,-int(-tmp/2))
print(-sum(A))
### BUGGY CODE ###

Q = 1000000007
n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
dp = {
    0: 1,
    1: 0 if 1 in a else 1
}

for k in range(2, n + 1):
    dp[k] = (0 if k in a else dp[k - 1] + dp[k - 2]) % Q


print(dp[n])


### FIXED CODE ###

Q = 1000000007
n, m = map(int, input().split())
a = set([int(input()) for _ in range(m)])
dp = {
    0: 1,
    1: 0 if 1 in a else 1
}

for k in range(2, n + 1):
    dp[k] = (0 if k in a else dp[k - 1] + dp[k - 2]) % Q


print(dp[n])
### BUGGY CODE ###

ans=0
n=int(input())
cnt=0
def tri(x):
	p=""
	while x>0:
		p+=str(x%4)
		x//=4
	return p[::-1]
i=16
k=357
while k<=n:
	c0=0
	c1=0
	c2=0
	for j in range(len(tri(i))):
		if tri(i)[j]=="1":
			c0+=1
		elif tri(i)[j]=="2":
			c1+=1
		elif tri(i)[j]=="3":
			c2+=1
		else:
			c0=0
			break
	if c0!=0 and c1!=0 and c2!=0:
		ans+=1
	i+=1
	k=0
	for j in range(len(tri(i))):
		k+=(int(tri(i)[-j-1])*2+1)*(10**j)
print(ans)

### FIXED CODE ###

n=input()
p=""
for i in range(len(n)):
	if int(n[i])>7:
		p+="3"*(len(n)-i)
		break
	elif int(n[i])==7:
		p+="3"
	elif int(n[i])==6:
		p+="2"
		p+="3"*(len(n)-i-1)
		break
	elif int(n[i])==5:
		p+="2"
	elif int(n[i])==4:
		p+="1"
		p+="3"*(len(n)-i-1)
		break
	elif int(n[i])==3:
		p+="1"
	else:
		p+="0"
total=0
for i in range(len(n)):
	total+=int(p[-i-1])*(4**i)
def tet(x):
	q=""
	while x!=0:
		q+=str(x%4)
		x//=4
	if len(q)==0:
		q="0"
	return q[::-1]
ans=[]
cnt=0
for i in range(total):
	if tet(i+1).count("0")==0:
		ans.append(tet(i+1))
for i in range(len(ans)):
	if ans[i].count("1") and ans[i].count("2")\
	and ans[i].count("3"):
		cnt+=1
print(cnt)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
h,w=map(int,input().split())
red=[list(map(int,input().split()))+[0] for i in range(h)]+[[0 for i in range(w+1)]]
blue=[list(map(int,input().split()))+[0] for i in range(h)]+[[0 for i in range(w+1)]]
field=[[[0 for h in range(6500)] for i in range(w+1)] for j in range(h+1)]
field[0][0][abs(red[0][0]-blue[0][0])]=1
for i in range(h):
    for j in range(w):
        for f in range(6401):
            if field[i][j][f]==1:
                field[i][j+1][f+abs(red[i][j+1]-blue[i][j+1])]=1
                field[i][j+1][abs(f-abs(red[i][j+1]-blue[i][j+1]))]=1
                field[i+1][j][f+abs(red[i+1][j]-blue[i+1][j])]=1
                field[i+1][j][abs(f-abs(red[i+1][j]-blue[i+1][j]))]=1
for i in range(6500):
    if field[h-1][w-1][i]==1:print(i);exit()


### FIXED CODE ###

import sys
input=sys.stdin.readline
h,w=map(int,input().split())
red=[list(map(int,input().split()))+[0] for i in range(h)]+[[0 for i in range(w+1)]]
blue=[list(map(int,input().split()))+[0] for i in range(h)]+[[0 for i in range(w+1)]]
field=[[[0 for h in range(6500)] for i in range(w+1)] for j in range(h+1)]
field[0][0][abs(red[0][0]-blue[0][0])]=1
for i in range(h):
    for j in range(w):
        for f in range(6401):
            if field[i][j][f]==1:
                field[i][j+1][f+abs(red[i][j+1]-blue[i][j+1])]=1
                field[i][j+1][abs(f-abs(red[i][j+1]-blue[i][j+1]))]=1
                field[i+1][j][f+abs(red[i+1][j]-blue[i+1][j])]=1
                field[i+1][j][abs(f-abs(red[i+1][j]-blue[i+1][j]))]=1
for i in range(6500):
    if field[h-1][w-1][i]==1:print(i);exit()
### BUGGY CODE ###

import sys
from collections import Counter
import random

n=int(input())
x=list(map(int,input().split()))
xb=x.copy()
y=sorted(x)
c=n//2-1
for i in range(n):
    x=xb.copy()
    a=x.pop(i)
    z=y.copy()
    z.remove(a)
    print(z[c])

### FIXED CODE ###

import sys
from collections import Counter
import random
import numpy as np

n=int(input())
x=np.array(list(map(int,input().split())))
z=sorted(x)
cand=[z[n//2-1],z[n//2]]
#print(int(np.median(x)))
dic={}
for i in range(n):
    a=x[i]
    if(a<=cand[0]):print(cand[1])
    else:print(cand[0])
### BUGGY CODE ###

from itertools import product


def solve(string):
    h, w, d, *a = map(int, string.split())
    a, q, lr = a[:h * w], a[h * w], a[h * w + 1:]
    n = h * w
    index = [a.index(i + 1) for i in range(h * w)]
    costs = [
        [0 if j <= i or (j - i) % d != 0 else n * (j - i) // d for j in range(n)] for i in range(n)
    ]
    for s, g in product(range(n), repeat=2):
        if costs[s][g] == 0:
            continue
        before = 0 if g - d < 0 else costs[s][g - d]
        costs[s][g] = abs(index[g - d] // w - index[g] // w) + abs(index[g - d] % w -
                                                                   index[g] % w) + before
    return "\n".join([str(costs[l - 1][r - 1]) for l, r in zip(lr[::2], lr[1::2])])


if __name__ == '__main__':
    n, m, d = map(int, input().split())
    ins = '{} {} {}\n'.format(n, m, d) + '\n'.join([input() for _ in range(n)])
    n = int(input())
    print(solve(ins + '\n{}\n'.format(n) + '\n'.join([input() for _ in range(n)])))


### FIXED CODE ###

import numpy as np

h, w, d = map(int, input().strip().split(" "))
a = [[int(i) for i in input().strip().split(" ")] for _ in range(h)]
q = int(input().strip())
lr = [input().strip().split(" ") for _ in range(q)]
rs = [None for _ in range(h * w)]
cs = [None for _ in range(h * w)]
for _r, _a in enumerate(a):
    for _c, __a in enumerate(_a):
        rs[__a - 1] = _r
        cs[__a - 1] = _c
rs_d = [rs[i::d] for i in range(d)]
cs_d = [cs[i::d] for i in range(d)]
costs = [
    np.cumsum(
        np.abs(np.array(_rs[1:]) - np.array(_rs[:-1])) +
        np.abs(np.array(_cs[1:]) - np.array(_cs[:-1]))) for _rs, _cs in zip(rs_d, cs_d)
]
for l, r in lr:
    l = int(l) - 1
    r = int(r) - 1
    if l == r:
        print(0)
    elif l < d:
        print(costs[r % d][r // d - 1])
    else:
        print(costs[r % d][r // d - 1] - costs[l % d][l // d - 1])
### BUGGY CODE ###

import fileinput

for line in fileinput.input():
    n = int(line)
    sqn = n ** 0.5
    ps = set()
    for i in range(3, n + 1, 2):
        for p in ps:
            if p > sqn:
                continue
            if i % p == 0:
                break
        else:
            ps.add(i)
        i += 2
    ps.add(2)

    print(sum(i in ps and (n + 1 - i) in ps for i in range(2, n + 1)))

### FIXED CODE ###

import fileinput

ps = set()
for i in range(3, 10001, 2):
    for p in ps:
        if p > 100:
            continue
        if i % p == 0:
            break
    else:
        ps.add(i)
    i += 2
ps.add(2)

for line in fileinput.input():
    n = int(line)
    print(sum(i in ps and (n + 1 - i) in ps for i in range(2, n + 1)))
### BUGGY CODE ###

#D問題
mod = 1000000007
S = str(input())
N = len(S)

dp = [[0 for i in range(13)] for j in range(N+1)]
dp[0][0] = 1
for i in range(N):
    if S[i] == "?":
        for j in range(10):
            for k in range(13):
                dp[i+1][(10*k+j)%13] += dp[i][k] 
    else:
        s = int(S[i])
        for k in range(13):
            dp[i+1][(10*k+s)%13] += dp[i][k]
            
print(dp[N][5]%mod)

### FIXED CODE ###

#D問題
mod = 1000000007
S = str(input())
N = len(S)


dp = [[0 for i in range(13)] for j in range(N+1)]
dp[0][0] = 1
for i,s in enumerate(S):
    if s == "?":
        for j in range(10):
            for k in range(13):
                ind = (10*k+j)%13
                dp[i+1][ind] += dp[i][k]
    else:
        j = int(s)
        for k in range(13):
            ind = (10*k+j)%13
            dp[i+1][ind] += dp[i][k]

    for k in range(13):
        dp[i+1][k]%=mod
            
print(dp[N][5]%mod)
### BUGGY CODE ###

import heapq
from collections import defaultdict

n, m, s, t = list(map(int, input().split()))

graph_y = defaultdict(list)
graph_s = defaultdict(list)

for i in range(m):
	u, v, a, b = list(map(int, input().split()))
	graph_y[u - 1].append([v - 1, a])
	graph_y[v - 1].append([u - 1, a])
	graph_s[u - 1].append([v - 1, b])
	graph_s[v - 1].append([u - 1, b])

dist_node_ys = defaultdict(lambda: float("inf"))
dist_node_ys[s - 1] = 0

Q = []
heapq.heappush(Q, (dist_node_ys[s - 1], s - 1))

while Q: 
	dis, v= heapq.heappop(Q)
	if dist_node_ys[v] < dis:
		continue
	for u, w in graph_y[v]:
		alt = dis + w
		if dist_node_ys[u] > alt:
			dist_node_ys[u] = alt
			heapq.heappush(Q, (alt, u))

dist_node_st = defaultdict(lambda: float("inf"))
dist_node_st[t - 1] = 0

Q = []
heapq.heappush(Q, (dist_node_st[t - 1], t - 1))

while Q: 
	dis, v = heapq.heappop(Q)
	if dist_node_st[v] < dis:
		continue
	for u, w in graph_s[v]:
		alt = dis + w
		if dist_node_st[u] > alt:
			dist_node_st[u] = alt
			heapq.heappush(Q, (alt, u))

ansL = []
X = []
for i in range(n):
	heapq.heappush(X, dist_node_ys[n - 1 - i] + dist_node_st[n - 1 - i])
	ansL.append(X[0])

for i in range(1, n + 1):
	print(1000000000000000 - ansL[- i])


### FIXED CODE ###

import heapq
from collections import defaultdict

n, m, s, t = list(map(int, input().split()))

graph_y = defaultdict(dict)
graph_s = defaultdict(dict)

for i in range(m):
	u, v, a, b = list(map(int, input().split()))
	graph_y[u - 1][v - 1] = a
	graph_y[v - 1][u - 1] = a
	graph_s[u - 1][v - 1] = b
	graph_s[v - 1][u - 1] = b

dist_node_ys = defaultdict(lambda: float("inf"))
dist_node_ys[s - 1] = 0

Q = []
heapq.heappush(Q, (dist_node_ys[s - 1], s - 1))

while Q: 
	dis, v = heapq.heappop(Q)
	if dist_node_ys[v] < dis:
		continue
	for i in graph_y[v]:
		u = i
		w = graph_y[v][i]
		alt = dis + w
		if dist_node_ys[u] > alt:
			dist_node_ys[u] = alt
			heapq.heappush(Q, (alt, u))


dist_node_st = defaultdict(lambda: float("inf"))
dist_node_st[t - 1] = 0

Q = []
heapq.heappush(Q, (dist_node_st[t - 1], t - 1))

while Q: 
	dis, v = heapq.heappop(Q)
	if dist_node_st[v] < dis:
		continue
	for i in graph_s[v]:
		u = i
		w = graph_s[v][i]
		alt = dis + w
		if dist_node_st[u] > alt:
			dist_node_st[u] = alt
			heapq.heappush(Q, (alt, u))

ansL = []
X = []
for i in range(n):
	heapq.heappush(X, dist_node_ys[n - 1 - i] + dist_node_st[n - 1 - i])
	ansL.append(X[0])

for i in range(1, n + 1):
	print(1000000000000000 - ansL[- i])
### BUGGY CODE ###

#!/usr/bin/env python3
# Atcoder necoak answer
# https://atcoder.jp/contests/diverta2019/tasks/diverta2019_b
import itertools

intext = input()
[r, g, b, n] = map(int, intext.split())

r_list = [rn for rn in range(0, n+1, r)]
g_list = [gn for gn in range(0, n+1, g)]
b_list = [bn for bn in range(0, n+1, b)]

rgb_combis = itertools.product(r_list, g_list, b_list)

cnt = 0
for rn, gn, bn in rgb_combis:
    if (rn+gn+bn) == n:
        cnt +=1

print(cnt)

### FIXED CODE ###

#!/usr/bin/env python3
# Atcoder necoak answer
# https://atcoder.jp/contests/diverta2019/tasks/diverta2019_b
import itertools

intext = input()
[r, g, b, n] = map(int, intext.split())

rgb_list = [r, g, b]
rgb_list.sort(reverse=True)
[x, y, z] = rgb_list

cnt = 0
for x_val in range(0, n+1, x):
    # for y_val in range(0, n+1, y):
    for y_val in range(0, (y*((n-x_val)//z))+1, y):
        zan = n - x_val - y_val
        if zan >=0 and zan % z == 0:
            cnt += 1
print(cnt)
### BUGGY CODE ###

#C問題
import heapq
N = int(input())
A = list(map(int,input().split()))

a = []
for i in range(N):
    heapq.heappush(a,A[i])
B = []
for i in range(3*N):
    B.append(-A[3*N-1-i])
b = []
for i in range(N):
    heapq.heappush(b,B[i])

Red = [sum(a) for i in range(N+1)]
Blue = [sum(b) for i in range(N+1)]
inf = float("inf")
MAX = -inf
AR = []
BB = []
for i in range(N):
    AR.append(A[N+i])
    BB.append(B[N+i])
for i,ar in enumerate(AR):
    l = heapq.heappushpop(a,ar)
    Red[i+1] = Red[i]+(ar-l)
for i,bb in enumerate(BB):
    m = heapq.heappushpop(b,bb)
    Blue[i+1] = Blue[i]+(bb-m)
    
for i in range(N+1):
    #print(Red[i],Blue[N-i])
    MAX = max(MAX,Red[i]+Blue[N-i])

#print(A,B)
print(MAX)


### FIXED CODE ###

#C問題
import heapq
N = int(input())
A = list(map(int,input().split()))

a = []
for i in range(N):
    heapq.heappush(a,A[i])
B = []
for i in range(3*N):
    B.append(-A[3*N-1-i])
b = []
for i in range(N):
    heapq.heappush(b,B[i])

Red = [sum(a)]
Blue = [sum(b)]
inf = float("inf")
MAX = -inf
AR = []
BB = []
for i in range(N):
    AR.append(A[N+i])
    BB.append(B[N+i])
for i,(ar,r) in enumerate(zip(AR,Red)):
    l = heapq.heappushpop(a,ar)
    Red.append(r+(ar-l))
for i,(bb,bl) in enumerate(zip(BB,Blue)):
    m = heapq.heappushpop(b,bb)
    Blue.append(bl+(bb-m))
    
for i in range(N+1):
    #print(Red[i],Blue[N-i])
    MAX = max(MAX,Red[i]+Blue[N-i])

#print(A,B)
print(MAX)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
def i():
    return int(raw_input())
def s():
    return raw_input()
 
#memoize macro
def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper
 
Q=10**9+7
@memoize
def dp(n,i):
    if n<i:return 0
    elif n==1:return 1
    if i==0:return (dp(n-1,1)*2+dp(n-1,0))%Q
    else:return (dp(n-1,i-1)+dp(n-1,i+1)*2)%Q
n=i()
s=s()
print dp(n,len(s))

### FIXED CODE ###

mod=1000000007
n=int(raw_input())
l=len(raw_input())
dp=[[0 for i in range(n+2)] for j in range(n+1)]
for i in range(n+1):
    for j in range(i+1):
        if i==0:dp[i][j]=1
        elif j==0:dp[i][j]=(dp[i-1][1]*2+dp[i-1][0])%mod
        else:dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1]*2)%mod
print dp[n][l]
### BUGGY CODE ###

import sys
inputs = sys.stdin.readlines()

h, w = map(int, inputs[0].split())
S = [list(map(lambda x: 0 if x=='#' else 1, row)) for row in inputs[1:]]

w_costs = [[0]*w for _ in range(h)]
h_costs = [[0]*w for _ in range(h)]

def row_search(x, y):
    x_, cost = x, 0
    while x+1 < w and S[y][x+1]:
        x += 1
        cost += 1
    while x_ <= x:
        w_costs[y][x] = cost
        x -= 1
def col_search(x, y):
    y_, cost = y, 0
    while y+1 < h and S[y+1][x]:
        y += 1
        cost += 1
    while y_ <= y:
        h_costs[y][x] = cost
        y -= 1

for y in range(h):
    for x in range(w):
        if S[y][x]:
            if w_costs[y][x] == 0:
                row_search(x, y)
            if h_costs[y][x] == 0:
                col_search(x, y)

ans = 0
for y in range(h):
    for x in range(w):
        ans = max(ans, w_costs[y][x] + h_costs[y][x] + 1)
print(ans)

### FIXED CODE ###

import sys
inputs = sys.stdin.readlines()

h, w = map(int, inputs[0].split())
S = [list(map(lambda x: 0 if x=='#' else 1, row)) for row in inputs[1:]]

w_costs = [[0]*w for _ in range(h)]
h_costs = [[0]*w for _ in range(h)]

def row_search(x, y):
    x_, cost = x, 0
    while x+1 < w and S[y][x+1]:
        x += 1
        cost += 1
    while x_ <= x:
        w_costs[y][x] = cost
        x -= 1
def col_search(x, y):
    y_, cost = y, 0
    while y+1 < h and S[y+1][x]:
        y += 1
        cost += 1
    while y_ <= y:
        h_costs[y][x] = cost
        y -= 1

for y in range(h):
    for x in range(w):
        if S[y][x]:
            if w_costs[y][x] == 0:
                row_search(x, y)
            if h_costs[y][x] == 0:
                col_search(x, y)

ans = 0
for y in range(h):
    for x in range(w):
        ans = max(ans, w_costs[y][x] + h_costs[y][x] + 1)
print(ans)
### BUGGY CODE ###

N, A, B = map(int, input().split())
S = input()
T = []
Answer = []

for i in range(N):
  if S[i] == "a":
    if A + B > Answer.count("Yes"):
      Answer.append("Yes")
    else:
      Answer.append("No")
  elif S[i] == "b":
    if A + B > Answer.count("Yes") and B > T.count("Yes"):
      Answer.append("Yes")
      T.append("Yes")
    else:
      Answer.append("No")
  else:
    Answer.append("No")
  print(Answer[i])


### FIXED CODE ###

N, A, B = map(int, input().split())
S = input()
T = []
Answer = []
Acount = 0
Tcount = 0

for i in range(N):
  if S[i] == "a":
    if A + B > Acount:
      Answer.append("Yes")
      Acount += 1
    else:
      Answer.append("No")
  elif S[i] == "b":
    if A + B > Acount and B > Tcount:
      Answer.append("Yes")
      T.append("Yes")
      Acount +=1
      Tcount +=1
    else:
      Answer.append("No")
  else:
    Answer.append("No")
  print(Answer[i])
### BUGGY CODE ###

n, m, qqq = map(int, input().split())
LR = [[] for _ in range(n)]

for i in range(m):
    l, r = map(int, input().split())
    for j in range(l):
        LR[j].append(r)


for i in range(qqq):
    p, q = map(int, input().split())
    ans = 0
    for j in LR[p-1]:
        if j <= q:
            ans+=1
    print(ans)


### FIXED CODE ###

n, m, qqq = map(int, input().split())
DP = [[0 for _ in range(n)]for __ in range(n)]

for i in range(m):
    l, r = map(int, input().split())
    DP[l-1][r-1]+=1


#DP = [[0 for _ in range(n)]for __ in range(n)]
for i in range(n-1)[::-1]:
    for j in range(1,n):
        DP[i][j] += DP[i+1][j]+DP[i][j-1]-DP[i+1][j-1]

for i in range(qqq):
    p, q = map(int, input().split())
    print(DP[p-1][q-1])
# print(DP)
### BUGGY CODE ###

n,k=map(int,input().split())
while n-k>=0:
    n-=k
if n==0: print(0)
else: print(min(n,k-n))

### FIXED CODE ###

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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


n = int(readline())
csf = [tuple(map(int, readline().split())) for _ in range(n-1)]

for i in range(n):
    now = 0
    for c, s, f in csf[i::]:
        while now > s:
            s += f
        now += s - now
        now += c
    print(now)


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


n = int(readline())
csf = [tuple(map(int, readline().split())) for _ in range(n-1)]

for i in range(n):
    now = 0
    for c, s, f in csf[i::]:
        if now <= s:
            now = s
        else:
            if now % f == 0:
                pass
            else:
                now = (now // f + 1) * f
        now += c
    print(now)
### BUGGY CODE ###

a,b,n=map(int,input().split())
list=[]
for i in range(a,b+1):
    list.append(i)
    
ans=[]
if n>=b-a+1:
    for i in range(b-a+1):
        print(list[i])
else:
    for i in range(n):
        if list[i] not in ans:
            ans.append(list[i])

    for j in range(b-a+1-n,b-a+1):
        if list[j] not in ans:
            ans.append(list[j])
        
for k in range(len(ans)):
    print(ans[k])

### FIXED CODE ###

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

r=range(a,b+1)
for i in sorted(set(r[:k])|set(r[-k:])):print(i)
### BUGGY CODE ###

l,r=list(map(int,input().split()))
m=2018
for i in range(l,min(r+1,l+2019)):
  for j in range(i+1,r+1):
    m=min(m,i*j%2019)
print(m)

### FIXED CODE ###

l,r=list(map(int,input().split()))
m=2018
for i in range(l,min(r+1,l+2019)):
  for j in range(i+1,min(r+1,l+2019)):
    m=min(m,i*j%2019)
print(m)
### BUGGY CODE ###

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

s = s.replace("AC","aC")
t = [0]*(n+1)
i = 0
for i in range(1,n+1):
    t[i] = s[:i].count("a")

for i in range(q):
    a,b = map(int,input().split())
    print((t[b-1])-(t[a-1]))

### FIXED CODE ###

n, q = map(int,input().split())
s = list(input())
t = [0]*(n)
j = 0
for j in range(n-1):
    if s[j]=="A" and s[j+1]=="C":
        t[j+1]=t[j]+1
    else:
        t[j+1]=t[j]
i = 0
for i in range(q):
    a,b = map(int,input().split())
    print((t[b-1])-(t[a-1]))
### BUGGY CODE ###

n = int(input())
dat = list(map(int, input().split()))
res = 0
for i in range(n):
    for j in range(i+1, n):
        #print(i,j,abs(i-j))
        if abs(i - j) == dat[i] + dat[j]:
            res += 1
print(res)

### FIXED CODE ###

import collections
import bisect
n = int(input())
cnt = collections.defaultdict(list)
dat = list(map(int, input().split()))
buf = []
for i in range(n):
    cnt[i - dat[i]].append(i)
#print(buf)
res = 0
for i in range(n):
    x = i + dat[i]
    if x in cnt:
        res += len(cnt[x]) - bisect.bisect_left(cnt[x], x)
print(res)
### BUGGY CODE ###

N = int(input())
X = int(input(),2)

def popcount(n):
    return bin(n).count('1')


def f(n):
    count = 0
    while n!=0:
        n = n%popcount(n)
        count += 1
    return count


for i in range(N):
    X_i = X ^ (1<<(N-i-1))
    print(f(X_i))

### FIXED CODE ###

N = int(input())
X = int(input(),2)

def popcount(n):
    return bin(n).count('1')


def f(n):
    if n== 0:
        return 1
    count = 1
    while n!=0:
        n = n%popcount(n)
        count += 1
    return count


X_popcount = popcount(X)
X_mod_p = X%(X_popcount+1)
if X_popcount != 1:
    X_mod_m = X%(X_popcount-1)
for i in range(N):
    X_i = X ^ (1<<(N-i-1))
    if X_i == 0:
        ans = 0
    elif X>>(N-i-1)&1 == 1:
        if X_popcount == 1:
            ans = 1
        else:
            ans = f((X_mod_m-pow(2, N-i-1, X_popcount-1))%(X_popcount-1))
    else:
        ans = f((X_mod_p+pow(2, N-i-1, X_popcount+1))%(X_popcount+1))
    print(ans)
### BUGGY CODE ###

N,M=[int(x) for x in input().split()]
I=[[] for n in range(N)]
ans = int(N * (N-1) / 2)
E=[]
result=[]

def visit(i,V):
    if(V[i]==0):
        V[i]=1
        total=1;
        for n in I[i]:
            total+=visit(n,V)
        return total
    else:
        return 0

for m in range(M):
    A,B=[int(x) for x in input().split()]
    E.append((A-1,B-1))

for m in range(M):
    result.append(ans)
    if(ans>0):
        A,B=E.pop()
        V=[0 for n in range(N)]
        Wa=visit(A,V)
        Wb=visit(B,V)
        ans=ans-(Wa*Wb)
        I[A].append(B)
        I[B].append(A)

for r in reversed(result):
    print(r)


### FIXED CODE ###

N,M=[int(x) for x in input().split()]
G=[-1] * N
W=[0] * N
E=[]

result=[]
ans = int(N * (N-1) / 2)

def union(i,j):
    gi=find(i)
    gj=find(j)

    if(gi!=gj):
        if W[gi] > W[gj]:
            G[gi]+=G[gj]
            G[gj]=gi
        else:
            G[gj]+=G[gi]
            G[gi]=gj
            if W[gi]==W[gj]:
                W[gj]+=1

def find(i):
    if G[i]<0:
        return i;
    else:
        G[i]=find(G[i])
        return G[i]

for m in range(M):
    A,B=[int(x) for x in input().split()]
    E.append((A-1,B-1))

for m in range(M):
    result.append(ans)
    if(ans>0):
        A,B=E.pop()
        ga,gb=find(A),find(B)
        if (ga!=gb):
            ans=ans-(G[ga]*G[gb])
            union(A,B)

for r in reversed(result):
    print(r)