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

def main():
    n,s=map(int,input().split())
    N=[i+1 for i in range(n)]
    list1=[]
    pattern=[]
    A=list(map(int,input().split()))

    ft=0  
    dict={}
    for i in range(n+1):
        dict[i]=[]
    for i in range(1,2**n):
        list2=[]
        for j in range(n):
            if (i >> j) &1 == 1:
                list2.append(N[j])
        pattern=[]
        for x in range(1,2**len(list2)):
            pt=[]
            for y in range(len(list2)):
                if (x>>y)&1==1:
                    pt.append(list2[y])
            pattern.append(pt)
    # print(pattern)

        for p in pattern:
            sum=0
            if p in dict[len(p)]:
                ft+=1
            else:
                for x in p:
                    sum+=A[x-1]
                if sum==s:
                    dict[len(p)].append(p)
                    ft+=1
                    ft=ft%998244353
    print(ft%998244353)

if __name__=="__main__":
    main()


### FIXED CODE ###

import numpy as np
def main():
    n,s=map(int,input().split())
    A=list(map(int,input().split()))
    dp=np.array([0 for i in range(min(3001,s+1))])
    dp[0]=1
    for ai in A:
        tmp=dp[:-ai].copy()
        #print(tmp)
        dp*=2
        dp[ai:]+=tmp
        dp%=998244353
    print(dp[s])
    

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

n = int(input())
l = list(map(int, input().split()))
ans = 0
maximum = max(l)+1
minimum = min(l)-1

for i in range(minimum, maximum+1):
  count = 0
  for j in l:
    if j == i or j == i+1 or j == i-1:
      count += 1
  if count > ans:
    ans = count

print(ans)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
ans = 0
count = {}
for i in range(0, 10**5+1):
  count[i] = 0

for i in l:
  count[i] = count[i] + 1

for i in range(0, 10**5+1):
  if i == 0:
    temp = count[i] + count[i+1]
  elif i == 10**5:
    temp = count[i] + count[i-1]
  else:
    temp = count[i] + count[i+1] + count[i-1]

  if temp > ans:
    ans = temp

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

# -*- coding: utf-8 -*-

from operator import mul
from functools import reduce

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


def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def calc_routes(dan):
    tmp = 1
    for i in range(int(dan/2)):
        i += 1
        n = dan - i
        # tmp += factorial(n) / factorial(i) / factorial(n - i)
        tmp += cmb(n, i)

    return tmp

routes = 1
prev = 0
for x in a:
    if x == prev:
        routes = 0
        break
    else:
        dan = (x-1) - prev
        routes = (routes * calc_routes(dan)) % 1000000007
        prev = x+1

routes = (routes * calc_routes(N-prev)) % 1000000007
print(int(routes))

### FIXED CODE ###

# -*- coding: utf-8 -*-
from math import factorial

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

def fibo(dan):
    tmp = [1, 1]
    for i in range(2, dan+1):
        tmp.append(tmp[i-1] + tmp[i-2])
    return tmp[dan]

routes = 1
prev = 0
for x in a:
    if x == prev:
        routes = 0
        break
    else:
        dan = (x-1) - prev
        routes = (routes * fibo(dan))
        prev = x+1

routes = (routes * fibo(N-prev)) % 1000000007
print(int(routes))
### BUGGY CODE ###

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

total = 1
for a in li:
    total *= a
    if a == 0:
        total = 0
        break

if 10 ** 18 < total:
    total = -1
  
print(total)

### FIXED CODE ###

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

total = 1
li.sort()
for a in li:
    if a == 0:
        total = 0
        break
    total *= a
    if 10 ** 18 < total:
        total = -1
        break
print(total)
### BUGGY CODE ###

import math
def main():
    i = int(input())
    j = list(map(int, input().split()))
    res = 1
    for jj in j:
        res *= jj

    if math.pow(10, 18) < res:
        print(-1)
    else:
        print(res)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import math
def main():
    i = int(input())
    j = list(map(int, input().split()))
    res = 1

    if 0 in j:
        print(0)
        return

    for jj in j:
        res *= jj
        if math.pow(10, 18) < res:
            print(-1)
            return

    print(res)


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

# -*- coding: utf-8 -*-
from itertools import product
from operator import xor
from functools import reduce
 
rS = input()
S = int(rS, 2)
 
L = len(rS)
k = len(rS)
 
dp = set([0])
while True:
    A = [sum([2**i for i in range(I, I+k)]) for I in range(L-k+1)]
    B = set([reduce(xor, A_) for i in range(0, L-k+1) for A_ in product(A, repeat=i+1)])
    dp.update([d^b for d, b in product(dp, B)])
    if S in dp:
        break
    else:
        #print(dp)
        k -= 1
print(k)

### FIXED CODE ###

# -*- coding: utf-8 -*-
S = input()
n = len(S)
L = list(map(int, list(S)))
D = []
res = 0
for k in range(n-1):
    if L[k] != L[k+1]:
        D.append(max(k+1, n-k-1))

if len(D):
    print(min(D))
else:
    print(n)
### BUGGY CODE ###

n = int(input())
a = [0] * n
b = [0] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())

count = 0
for i in reversed(range(n)):
    c = b[i] * (-(-a[i] // b[i])) - a[i]
    for j in range(i):
        a[j] += c
    count += c
print(count)


### FIXED CODE ###

n = int(input())
a = [0] * n
b = [0] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())

count = 0
for i in reversed(range(n)):
    c = b[i] * (-(-a[i] // b[i])) - a[i]
    #for j in range(i):
    #    a[j] += c
    count += c
    if i >= 1:
        a[i-1] += count
print(count)
### BUGGY CODE ###

n,k = map(int, input().split())
a = list(map(int, input().split()))
hyoutei = []
for i in range(n-k+1):
    tmp = 0
    for j in range(i,k+i):
        tmp += a[j]
    hyoutei.append(tmp)

for i in range(n-k):
    if hyoutei[i] < hyoutei[i+1]:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

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


for i in range(n-k):
    if (a[i] < a[i+k]):
        print("Yes")
    else: print("No")
### BUGGY CODE ###

n, m = map(int, input().split())
friend = [[] for i in range(n)]
for i in range(m):
    s, t = map(int, input().split())
    friend[s].append(t)
    friend[t].append(s)

def are_connected(s, t):
    q = [s]
    checked = [False] * n
    checked[s] = True

    while q:
        user = q.pop(0)
        for f in friend[user]:
            if f == t:
                return True
            elif not checked[f]:
                q.append(f)
                checked[f] = True
    return False

q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    if are_connected(s, t):
        print('yes')
    else:
        print('no')

### FIXED CODE ###

n, m = map(int, input().split())
friend = [[] for i in range(n)]
for i in range(m):
    s, t = map(int, input().split())
    friend[s].append(t)
    friend[t].append(s)

group = [-1 for i in range(n)]
for u in range(n):
    if group[u] == -1:
        group[u] = u
        q = [u]
        while q:
            u1 = q.pop()
            for u2 in friend[u1]:
                if group[u2] == -1:
                    group[u2] = u
                    q.append(u2)

q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    if group[s] == group[t]:
        print('yes')
    else:
        print('no')
### BUGGY CODE ###

from functools import reduce
mod=10**9+7

def f(A,B):
 if B==0:
  den=1
  num=1
 else:
  den=reduce(lambda x,y:x*y%mod,range(A,A-B,-1))
  num=reduce(lambda x,y:x*y%mod,range(1,B+1))
 return den*pow(num,mod-2,mod)%mod

n,k=map(int,input().split())
ans=0
for i in range(min(n-1,k)+1):
 ans+=f(n,i)*f(n-1,i)%mod
print(ans%mod)

### FIXED CODE ###

mod=10**9+7
n,k=map(int,input().split())
ans=0
comb1=1 #初期値はNC0=1
comb2=1 #初期値は(N-1)C0=1
for i in range(min(k+1,n)): #0人の部屋は高々N-1個しか
 # 存在しないので操作回数は高々min(K,N-1)回となる
 ans+=comb1*comb2 #0人の部屋がi個のときの場合の数は
 # NCi*(N-1)Ci
 ans%=mod
 comb1*=(n-i)*pow(i+1,mod-2,mod) #NC(i+1)はNC
 # i*(N-i)/(i+1)で求められる
 comb1%=mod
 comb2*=(n-1-i)*pow(i+1,mod-2,mod) #(N-1)C(i+1
 # )は(N-1)Ci*((N-1)-i)/(i+1)で求められる
 comb2%=mod
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
exp=list(map(int,input().split()))
A=[]
for i in range(N-K+1):
  A.append(sum(exp[i:i+K]))
print((max(A)+K)/2)

### FIXED CODE ###

N,K=map(int,input().split())
p=list(map(int,input().split()))
S=sum(p[:K])
T=S
for i in range(N-K):
  S=S-p[i]+p[i+K]
  T=max(T,S)
print((T+K)/2)
### BUGGY CODE ###

import collections
import sys
sys.setrecursionlimit(10**6)

def calc(one,two,three):
  if dp[one][two][three]!=-1:
    return dp[one][two][three]
  zero=n-one-two-three
  if zero==n:
    return 0
  ret=n
  if one!=0:
    ret+=calc(one-1,two,three)*one
  if two!=0:
    ret+=calc(one+1,two-1,three)*two
  if three!=0:
    ret+=calc(one,two+1,three-1)*three
  ret/=n-zero
  dp[one][two][three]=ret
  return ret

n=int(input())
arr=list(map(int,input().split()))
dp=[[[-1]*301 for _ in range(301)] for _ in range(301)]
cnt=collections.Counter(arr)
print(calc(cnt[1],cnt[2],cnt[3]))

### FIXED CODE ###

import collections

n=int(input())
arr=list(map(int,input().split()))
dp=[[[0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]
cnt=collections.Counter(arr)
for total in range(1,n+1):
  for three in range(total+1):
    for two in range(total-three+1):
      one=total-two-three
      dp[one][two][three]+=n/total
      if one!=0:
        dp[one][two][three]+=dp[one-1][two][three]*one/total
      if two!=0:
        dp[one][two][three]+=dp[one+1][two-1][three]*two/total
      if three!=0:
        dp[one][two][three]+=dp[one][two+1][three-1]*three/total
print(dp[cnt[1]][cnt[2]][cnt[3]])
### BUGGY CODE ###

import fractions
from functools import reduce
n = int(input())
A = []
A = list(map(int, input().split()))
mod = 10**9 + 7
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
Z = lcm(*A)
ans = sum(Z//a%mod for a in A)%mod
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import fractions
N=int(input())
A=list(map(int,input().split()))
c=1
a=0
w=10**9+7
for A_ in A:
    c=c*A_//fractions.gcd(c,A_)
for A_ in A:
    a+=c//A_
print(int(a%w))
### BUGGY CODE ###

t=int(input())
for _ in range(t):
    a,b,c,d=map(int,input().split())
    e=b*(max((a-c)//b,1))
    a-=e
    while a>c:
        a-=b
    if a<0:
        print('No')
        continue
    if d<b:
        print('No')
        continue
    if c<=b and d>b:
        while a<=c:
            a+=(d-b)
        if a<b:
            print('No')
            continue
    print('Yes')
    


### FIXED CODE ###

from fractions import*
_,*t=open(0)
for t in t:
  a,b,c,d=map(int,t.split())
  g=gcd(b,d)
  print('YNeos'[b>min(a,d)or b-g+a%g>c::2])
### BUGGY CODE ###

s=input()
ans=""
q=int(input())
switch=0

for i in range(q):
  ques=list(input().split())
  if ques[0]=="1":
    switch+=1
    #print("1",s)
  else:
    if ques[1]=="1":
      if switch%2==0:
        s=ques[2]+s
        #print("2",s)
      else:
        s=s+ques[2]
    else:
      if switch%2==0:
        s=s+ques[2]
      else:
        s=ques[2]+s
        #print("22",s)
if switch%2==1:
  ans=s[::-1]
else:
  ans=s
print(ans)


### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())
ans = deque(S)
revcnt = 0
for i in range(Q):
    data = list(input().split())
    if data[0] == '1':
        revcnt += 1
        continue

    if data[1] == '1':
        if revcnt % 2 == 0:
            ans.appendleft(data[2])
        else:
            ans.append(data[2])
    else:
        if revcnt % 2 == 0:
            ans.append(data[2])
        else:
            ans.appendleft(data[2])

if revcnt % 2 != 0:
    print(''.join(reversed(list(ans))))
else:
    print(''.join(list(ans)))
### BUGGY CODE ###

import math
import itertools
n,k = map(int, input().split())
n += 1
count = 0
def combination(n,r):
    ls = []
    tmp_list = []
    ls =  list(itertools.combinations(range(n),r))
    for l in ls:
        tmp_list.append(str(len(l))+str(sum(l)))
    return len(set(tmp_list))
for i in range(k,n+1):
    count += combination(n,i)
print(count % 1000000007)

### FIXED CODE ###

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

ans = 0
mod = 10**9+7
for i in range(k, n+2):
    min = ((i-1)*i)//2
    max = ((2*n-i+1)*i)//2
    ans += max-min + 1
print(ans%mod)
### BUGGY CODE ###

n=int(input())
c = list(map(int, input().rstrip().split()))
a=0
b=10**9+7
for i in range(len(c)):
    for j in range(i+1,n):
        
        f=(c[i]%b*c[j]%b)%b
        a=a+f
        
print(a%b)

### FIXED CODE ###

n=int(input())
c = list(map(int, input().rstrip().split()))
ans=0
b=10**9+7
sum1=0
for i in range(n):
    ans=(ans+c[i]*sum1)%b
    sum1=(sum1+c[i])%b

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

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

nums=[]
jud=[]
WAs={}
for i in range(M):
  A=input().split()
  nums.append(A[0])
  jud.append(A[1])
  WAs[nums[i]]=0

ACs=[]


AC=0
pena=0

for i in range(M):
  if nums[i] in ACs:
    continue
  else:
    if jud[i]=="WA":
      WAs[nums[i]]+=1
    else:
      AC+=1
      ACs.append(nums[i])
      pena+=WAs[nums[i]]
      
print(AC, pena)


        

### FIXED CODE ###

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

pena=np.array([0]*N)
status=np.array([0]*N)


for i in range(M):
  p,s=tuple(input().split())
  p=int(p)
  if s=="WA":
    if status[p-1]!=1:
      pena[p-1]+=1
  if s=="AC":
    if status[p-1]!=1:
      status[p-1]=1
nac=sum(status)
npena=sum(pena*status)
print(nac, npena)
### BUGGY CODE ###


import bisect
import sys

N, Q = map(int, input().split())
kouzi = []
for _ in range(N):
    S, T, X = map(int, input().split())
    kouzi.append([X, S, T-1])
kouzi.sort(reverse = True)

human = [int(input()) for _ in range(Q)]
ans = [-1]*(Q+1)


N0 = 2**(Q-1).bit_length()
data = [None]*(2*N0)
INF = (-1, 2**31-1)

def update(l, r, v):
    L = l + N0; R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R-1] = v

        if L & 1:
            data[L-1] = v
            L += 1
        L >>= 1; R >>= 1
def _query(k):
    k += N0-1
    s = INF
    while k >= 0:
        if data[k]:
            s = max(s, data[k])
        k = (k - 1) // 2
    return s
def query(k):
    return _query(k)[1]
t = 0
for task in kouzi:
    t += 1
    x = task[0]
    l = bisect.bisect_left(human, task[1]-x)
    r = bisect.bisect_right(human, task[2]-x)
    if l == r:
        continue
    update(l, r, (t, x))

for i in range(Q):
    q = query(i)
    if q == 2147483647:
        print(-1)
    else:
        print(q)


### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
kouzi = []
for _ in range(N):
    S, T, X = map(int, input().split())
    kouzi.append([X, S, T-1])
kouzi.sort(reverse = True)

human = [int(input()) for _ in range(Q)]
ans = [-1]*(Q+1)


N0 = 2**(Q-1).bit_length()
data = [None]*(2*N0)
INF = (-1, 2**31-1)

def update(l, r, v):
    L = l + N0; R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            data[R-1] = v

        if L & 1:
            data[L-1] = v
            L += 1
        L >>= 1; R >>= 1
def _query(k):
    k += N0-1
    s = INF
    while k >= 0:
        if data[k]:
            s = max(s, data[k])
        k = (k - 1) // 2
    return s
def query(k):
    return _query(k)[1]
t = 0
for task in kouzi:
    t += 1
    x = task[0]
    l = bisect.bisect_left(human, task[1]-x)
    r = bisect.bisect_right(human, task[2]-x)
    if l == r:
        continue
    update(l, r, (t, x))

for i in range(Q):
    q = query(i)
    if q == 2147483647:
        print(-1)
    else:
        print(q)
### BUGGY CODE ###

# B
n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0]*(n+1)

for i in range(2, n+1):
    c_list = []
    if i-2 < k:
        for j in range(1, i):
            c_list.append(dp[i-j] + abs(h[i-1-j] - h[i-1]))
    else:
        for j in range(1,k+1):
            c_list.append(dp[i-j] + abs(h[i-1-j] - h[i-1]))
    dp[i] = min(c_list)
print(dp[-1])

### FIXED CODE ###

# B
import numpy as np
N, K = map(int, input().split())
h = np.array(input().split(), dtype="int32")
dp = np.zeros(N, dtype="int32")
 
for i in range(1, N):
    if i < K:
        dp[i] = np.min(dp[:i] + np.abs(h[i]-h[:i]))
    else:
        dp[i] = np.min(dp[i-K:i] + np.abs(h[i]-h[i-K:i]))
print(dp[-1])
### BUGGY CODE ###

N = int(input())
H = list(map(int, input().split()))
a = [0] * N

for i in range(N):
  for j in range(i, N-1):
    if H[j] >= H[j+1]:
      a[i] = a[i] + 1
    else:
      break
      
print(max(a))

### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
a = [0] * N
start = 0

for i in range(N - 1):
  if H[i] >= H[i+1]:
    a[start] += 1
  else:
    start += 1

      
print(max(a))
### BUGGY CODE ###

n,h = (int(i) for i in input().split())
x = [[int(i) for i in input().split()] for i in range(n)]
a,b = [],[]
for j in x:
	a.append(j[0])
	b.append(j[1])
num = 0
for j2 in b:
	if j2 >= max(a):
		h -= j2
		num +=1
if h%max(a)==0: answer = (h-h%max(a))//max(a) + num
else: answer = (h-h%max(a))//max(a) + num + 1
print(answer)

### FIXED CODE ###

def main():
    N, H = map(int, input().split())
    AB = (tuple(map(int, input().split())) for _ in [0] * N)
    a, b = [], []
    appenda, appendb = a.append, b.append
    for i, j in AB:
        appenda(i)
        appendb(j)

    amax = max(a)
    b = [i for i in b if i > amax]
    b.sort(reverse=1)
    energy = H
    if energy <= sum(b):
        attack = 0
        i = 0
        while energy > 0:
            energy -= b[i]
            attack += 1
            i += 1
    else:
        energy -= sum(b)
        attack = (energy + amax - 1) // amax + len(b)

    print(attack)

main()
### BUGGY CODE ###

import copy

s = input()
s_sub = copy.deepcopy(s)

tar1 = "01"
tar2 = "10"
tar3 = ["1010","1001","0101","0110"]

while((tar1 in s )or(tar2 in s)):
    for i in range(4):
        if tar3[i] in s:
            s = s.replace(tar3[i],"")
            
    if tar1 in s:
        s = s.replace(tar1,"")
    if tar2 in s:
        s = s.replace(tar2,"")



print(len(s_sub)-len(s))


### FIXED CODE ###

import copy

s = input()
s_sub = copy.deepcopy(s)
# # 
# tar1 = "01"
# tar2 = "10"
# tar3 = ["1010","1001","0101","0110","1100","0011",""]
# 
# while((tar1 in s )or(tar2 in s)):
# 
# 
#     # for i in range(4):
#     #     if tar3[i] in s:
#     #         s = s.replace(tar3[i],"")
# 
# 
#     if tar1 in s:
#         s = s.replace(tar1,"",1)
#     if tar2 in s:
#         s = s.replace(tar2,"",1)
# 
# 
# 
# print(len(s_sub)-len(s))

#0と1の数数えて差分が残るのでは？
l1 = s.count("0")
l2 = s.count("1")
l3 = abs(l1-l2)

print(len(s_sub)-l3)
### BUGGY CODE ###

import sys
from collections import Counter


N, Q = map(int, input().split())
C = list(map(int, input().split()))

e = Counter()
A = [None] * (N + 1)
A[0] = e | e
for i, c in enumerate(C):
    A[i + 1] = A[i] + Counter({c: 1})

for i in range(Q):
    l, r = map(int, sys.stdin.readline().split())
    print(len(A[r] - A[l - 1]))


### FIXED CODE ###

import sys


class BinaryIndexedTree():
    '''
    1-indexed
    '''
    def __init__(self, A):
        self.__n = len(A)
        self.__node = [0] * (self.__n + 1)
        self.__data = [0] * (self.__n + 1)

        S = [0] * (self.__n + 1)
        for i in range(self.__n):
            S[i + 1] = S[i] + A[i]

        for i in range(1, self.__n + 1):
            self.__data[i] = A[i - 1]
            self.__node[i] = S[i] - S[i - (i & -i)]

    def add(self, i, v):
        self.__data[i] += v
        while i <= self.__n:
            self.__node[i] += v
            i += i & -i

    def sum(self, i):
        ''' [1, i]の和
        '''
        rst = 0
        while i > 0:
            rst += self.__node[i]
            i -= i & -i
        return rst
    
    def get(self, i, j):
        '''[i, j]の和
        '''
        if i == j:
            return self.__data[i]
        else:
            return self.sum(j) - self.sum(i - 1)


def main():
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))

    P = [[] for _ in range(N)]
    for i, c in enumerate(C):
        P[c - 1].append(i)

    right = [0] * N
    for p in P:
        if len(p):
            right[p.pop()] = 1
    BIT = BinaryIndexedTree(right)

    query = [[] for _ in range(N)]
    for i in range(Q):
        l, r = map(int, sys.stdin.readline().split())
        query[r - 1].append((l - 1, i))

    ans = [None] * Q

    cur = N - 1
    for r, q in enumerate(reversed(query)):
        r = (N - 1) - r
        while q:
            l, i = q.pop()
            while r < cur:
                c = C[cur] - 1
                # BIT.update(cur + 1, 0)
                p = P[c]
                if len(p):
                    BIT.add(p.pop() + 1, 1)
                cur -= 1
            tmp = BIT.get(l + 1, r + 1)
            ans[i] = tmp

    print(*ans, sep='\n')


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

N = int(input())
fac = []
for i in range(1, N + 1):
  if (N % i == 0 and N // i <= i):
    print(N // i + i - 2)
    exit()

### FIXED CODE ###

N = int(input())
i = 1
ans = N
while (i ** 2 <= N):
  if (N % i == 0):
    ans = min(ans, N // i + i - 2)
  i += 1

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

import itertools
n = int(input())
a = list(map(int, input().split()))
ans = 0
p = 10 ** 9+7
for j in itertools.combinations(a,2):
    ans += (j[0]* j[1])
    ans = ans%p
print(ans)

### FIXED CODE ###

import itertools
n = int(input())
a = list(map(int, input().split()))
suma = sum(a)-a[0]
ans = 0
p = 10 ** 9+7
for i in range(len(a)-1):
    ans += a[i]*suma
    suma -= a[i+1]
    ans = ans%p
print(ans)
### BUGGY CODE ###

N = int(input())

Cost = [0]
Start = [0]
Frequency = [0]


for __ in range(N-1):
    c, s, f = map(int, input().split())
    Cost.append(c)
    Start.append(s)
    Frequency.append(f)
a = sum(Cost) + max(Start) + sum(Frequency)
DP = [[0] * (2 * a) for _ in range(N+1)]

for i in range(N-1, 0, -1):
    for j in range(a, -1, -1):
        if j < Start[i]:
            DP[i][j] = DP[i][Start[i]] + Start[i] - j
        elif j >= Start[i]:
            sa = j % Frequency[i]
            if sa == 0:
                DP[i][j] = DP[i+1][j+Cost[i]] + Cost[i]
            else:
                DP[i][j] = DP[i][j + Frequency[i] - sa] + Frequency[i] - sa
for i in range(N):
    print(DP[i+1][0])




### FIXED CODE ###

N = int(input())

Cost = [0]
Start = [0]
Frequency = [0]
Ans = [0] * (N+1)

for __ in range(N-1):
    c, s, f = map(int, input().split())
    Cost.append(c)
    Start.append(s)
    Frequency.append(f)

for i in range(1, N):
    if Ans[i] != 0:
        print(Ans[i])
    else:
        Same = []
        now = 0
        for j in range(i, N):
            if now <= Start[j]:
                if Ans[j] != 0:
                    now = Ans[j]
                    break
                Same.append(j)
                now = Start[j] + Cost[j]
            else:
                tmp = (now-1) // Frequency[j]
                tim = (tmp + 1) * Frequency[j]
                now = tim + Cost[j]
        print(now)
        for k in Same:
            Ans[k] = now
print(0)