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

from bisect import*
def main():
    root=[[],[]]
    def search_higher(key):
        ptr0,ptr1=root
        ret=None
        while ptr1:
            i=bisect(ptr0,key)
            if i!=len(ptr0):ret=ptr0[i]
            ptr0,ptr1=ptr1[i]
        i=bisect(ptr0,key)
        if i!=len(ptr0):ret=ptr0[i]
        return ret
    def search_lower(key):
        ptr0,ptr1=root
        ret=None
        while ptr1:
            i=bisect_left(ptr0,key)
            if i!=0:ret=ptr0[i-1]
            ptr0,ptr1=ptr1[i]
        i=bisect_left(ptr0,key)
        if i!=0:ret=ptr0[i-1]
        return ret
    def insert_rec(ptr,key):
        ptr0,ptr1=ptr
        b_size=1024
        if not ptr[1]:
            insort(ptr0,key)
            if len(ptr0)==b_size*2-1:
                ret=[ptr0[:b_size],[]]
                ptr[0]=ptr0[b_size:]
                return ret
        else:
            i=bisect(ptr0,key)
            tmp=insert_rec(ptr1[i],key)
            if tmp:
                ptr0.insert(i,tmp[0].pop())
                ptr1.insert(i,tmp)
                if len(ptr1)==b_size*2:
                    ret=[ptr0[:b_size],ptr1[:b_size]]
                    ptr[0],ptr[1]=ptr0[b_size:],ptr1[b_size:]
                    return ret
    def insert(key):
        tmp=insert_rec(root,key)
        if tmp:root[0],root[1]=[tmp[0].pop()],[tmp,root]
    n,*a=map(int,open(0).read().split())
    l=[0]*n
    for i,v in enumerate(a,1):l[v-1]=i
    insert(0)
    insert(n+1)
    c=0
    for i,v in enumerate(l,1):
        c+=(search_higher(v)-v)*(v-search_lower(v))*i
        insert(v)
    print(c)
main()

### FIXED CODE ###

root=lambda x:x if par[x]==x else root(par[x])
same=lambda x,y:root(x)==root(y)
def unite(*z):
  x,y=map(root,z)
  if x!=y:
    if rank[x]<rank[y]:
      par[x]=y
      size[y]+=size[x]
    else:
      par[y]=x
      size[x]+=size[y]
      if rank[x]==rank[y]:rank[x]+=1
n,*a=map(int,open(0).read().split())
*par,=range(n)
rank=[1]*n
size=[1]*n
b=[0]*n
for i,t in enumerate(a):b[t-1]=i
c=0
for k in b[::-1]:
  l=r=1
  if k>0 and a[k-1]>a[k]:
    l+=size[root(k-1)]
    unite(k-1,k)
  if k+1<n and a[k+1]>a[k]:
    r+=size[root(k+1)]
    unite(k+1,k)
  c+=l*r*a[k]
print(c)
### BUGGY CODE ###


import sys
sys.setrecursionlimit(10 ** 7)

def resolve():
    MOD = 10 ** 9 + 7

    # 0: white, 1: black
    def dfs(v, parent):
        dp[v][0] = 1
        dp[v][1] = 1
        for to in G[v]:
            if to == parent:
                continue
            dfs(to, v)
            # 親が白の時は子は白黒どっちでも良い
            # 親が黒の時は子は白のみ
            dp[v][0] = (dp[v][0] * (dp[to][0] + dp[to][1])) % MOD
            dp[v][1] = (dp[v][1] * dp[to][0]) % MOD

    N = int(input())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        x, y = map(lambda x: int(x) - 1, input().split())
        G[x].append(y)
        G[y].append(x)
    dp = [[0] * 2 for _ in range(N + 1)]

    dfs(0, -1)
    ans = dp[0][0] + dp[0][1]
    print(ans % MOD)


if __name__ == "__main__":
    resolve()

### FIXED CODE ###


import sys
sys.setrecursionlimit(10 ** 7)
inp = sys.stdin.buffer.readline


def resolve():
    MOD = 10 ** 9 + 7

    # 0: white, 1: black
    def dfs(v, parent):
        vistied[v] = True
        dp[v][0] = 1
        dp[v][1] = 1
        for to in G[v]:
            if to == parent or vistied[to]:
                continue
            dfs(to, v)
            # 親が白の時は子は白黒どっちでも良い
            # 親が黒の時は子は白のみ
            dp[v][0] *= (dp[to][0] + dp[to][1]) % MOD
            dp[v][1] *= dp[to][0] % MOD

    N = int(inp())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        x, y = map(lambda x: int(x) - 1, inp().split())
        G[x].append(y)
        G[y].append(x)
    dp = [[0] * 2 for _ in range(N)]
    vistied = [False] * N

    dfs(0, -1)
    ans = dp[0][0] + dp[0][1]
    print(ans % MOD)


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

import sys
a = input()
S = [s for s in a]

cnt = 0
while True:
    b = a
    c = a.count("BW")
    a = a.replace("BW","WB")
    if c != 0:
        cnt += c
    else:
        print(cnt)
        sys.exit(0)

### FIXED CODE ###

import sys
a = [ c for c in input()]
B = 0
W = 0
for i in range(len(a)):
    if a[i] == "B":
        B += 1
    else:
        W += B

print(W)
### BUGGY CODE ###

from sys import stdin

def main():
    n,w=map(int,stdin.readline().strip().split())
    t=[list(map(int,stdin.readline().strip().split())) for _ in range(n)]
    w1=t[0][0]
    for i in range(4):
        t.append([w1+i,0])
    arr=[sorted([x for x in t if x[0]==w1+i],reverse=True,key=lambda e:e[1]) for i in range(4)]
    # arr=[x.sort(reverse=True,key=lambda e:e[1]) for x in arr]
    arrlen=list(map(len,arr))
    ans=0
    sw=0
    sv=0
    for i0 in range(arrlen[0]):
         for i1 in range(arrlen[1]):
              for i2 in range(arrlen[2]):
                   for i3 in range(arrlen[3]):
                        sw=sum([x[0] for x in arr[0][:i0]])+sum([x[0] for x in arr[1][:i1]])\
                          +sum([x[0] for x in arr[2][:i2]])+sum([x[0] for x in arr[3][:i3]])
                        sv=sum([x[1] for x in arr[0][:i0]])+sum([x[1] for x in arr[1][:i1]])\
                          +sum([x[1] for x in arr[2][:i2]])+sum([x[1] for x in arr[3][:i3]])
                        if sw<=w:
                            ans=max(ans,sv)
    print(ans)
    # wts=list(map(lambda l:l[0]-w1-1, t))
    # val=list(map(lambda l:l[1], t))

if __name__=='__main__':
    main()   


### FIXED CODE ###

from sys import stdin
import numpy as np

def main():
    def itrsum(arr):
        n=len(arr)
        tri=np.array([[i>=j for i in range(n)] for j in range(n+1)])
        return np.dot(tri,arr).astype('int64')
    n,w=map(int,stdin.readline().strip().split())
    t=[list(map(int,stdin.readline().strip().split())) for _ in range(n)]
    w1=t[0][0]
    # arr=[sorted([x for x in t if x[0]==w1+i],reverse=True,key=lambda e:e[1]) for i in range(4)]
    arr=[[x for x in t if x[0]==w1+i] for i in range(4)]
    arr=[l for l in arr]
    lenarr=list(map(len,arr))
    arr0=[itrsum(np.array(sorted([x[0] for x in l]),dtype='int64')) for l in arr]
    arr1=[itrsum(np.array(sorted([x[1] for x in l]),dtype='int64')) for l in arr]
    # arr=[x.sort(reverse=True,key=lambda e:e[1]) for x in arr]
    arr=np.array(arr)
    arrw=0
    arrv=0
    for i in range(4):
        arrw=np.ravel(arr0[i].reshape(lenarr[i]+1,1)+np.array([arrw]))
        arrv=np.ravel(arr1[i].reshape(lenarr[i]+1,1)+np.array([arrv]))
    #print(arr0)
    #print(arr1)
    #print('\n')
    #print(arrw)
    #print(arrv)
    #print(arrv[arrw<=w])
    ansarr=arrv[arrw<=w]
    print(np.max(ansarr))
    # wts=list(map(lambda l:l[0]-w1-1, t))
    # val=list(map(lambda l:l[1], t))

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

n,m = map(int, input().split())
if m >(n//2+1):
    print(0)
    exit()
bl = [int(input())-1 for _ in range(m)]
l = [i for i in range(n)]
for num in bl:
    l.remove(num)
    
mod = 1000000007

al = [0]*n
if 0 in l and 1 in l:
    al[0] = 1
    al[1] = 2
elif 0 in l:
    al[0] =1
elif 1 in l:
    al[1] = 1
else:
    print(0)
    exit()
    
li = [i for i in l if i>=2]
for i in li:
    al[i] = al[i-1] + al[i-2]
    if al[i] == 0:
        print(0)
        exit()

print(al[-1]%mod)

### FIXED CODE ###

n,m = map(int, input().split())
bl = [int(input())-1 for _ in range(m)]
l = [i for i in range(n)]
cnt = 0
for num in bl:
    del l[num-cnt]
    cnt +=1
    
mod = 1000000007

al = [0]*n
if 0 in l and 1 in l:
    al[0] = 1
    al[1] = 2
elif 0 in l:
    al[0] =1
elif 1 in l:
    al[1] = 1
else:
    print(0)
    exit()
    
li = [i for i in l if i>=2]
for i in li:
    al[i] = al[i-1] + al[i-2]
    if al[i] == 0:
        print(0)
        exit()

print(al[-1]%mod)
### BUGGY CODE ###

import bisect
import itertools
N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
flag1=1 if N<=30 else 0
flag2=1
flag3=1
for i in range(N):
    w[i],v[i]=map(int,input().split())
    if v[i]>100000:
        flag2=0
    if w[i]>100000:
        flag3=0
if flag1==1:
    A=[];B=[]
    for i in range(N):
        if i%2==0:
            A.append((v[i],w[i]))
        else:
            B.append((v[i],w[i]))
    Al=len(A);Bl=len(B)
    Xtmp=[]
    for seq in itertools.product(range(2),repeat=Al):
        tmp0=0
        tmp1=0
        for i in range(Al):
            if seq[i]==1:
                tmp0+=A[i][0]
                tmp1+=A[i][1]
        Xtmp.append((tmp0,tmp1))
    Xtmp.sort(key=lambda x:x[1])
    X=[]
    Xltmp=len(Xtmp)
    maxtmp=0
    for i,seq in enumerate(Xtmp):
        if maxtmp<=seq[0]:
            X.append(seq)
        maxtmp=max(maxtmp,seq[0])
    #print(X)
    wt=[i[1] for i in X]
    #print(wt)
    ans=0
    for seq in itertools.product(range(2),repeat=Bl):
        tmp0=0
        tmp1=0
        for i in range(Bl):
            if seq[i]==1:
                tmp0+=B[i][0]
                tmp1+=B[i][1]
        if W-tmp1<=0:
            continue
        index=bisect.bisect_right(wt,W-tmp1)-1
        tmp=X[index][0]+tmp0
        ans=max(ans,tmp)
    print(ans)
elif flag2==1:
    V=sum(v)
    INF=10**15
    dp=[[INF for j in range(V+1)] for i in range(N+1)]
    #dp[i][j]:iまで試して価値の合計がjのときの重さの最小値
    dp[0][0]=0
    for i in range(N):
        for j in range(V+1):
            if j-v[i]>=0:
                dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i],INF)
            else:
                dp[i+1][j]=min(dp[i][j],INF)
    b=[]
    for i in range(V+1):
        if dp[N][i]!=INF:
            b.append((dp[N][i],i))
    ans=0
    for (x,y) in b:
        if x<=W:
            ans=max(ans,y)
    print(ans)
elif flag3==1:
    dp=[[0 for i in range(W+1)] for i in range(N+1)]
    for j in range(W+1):
        dp[0][j]=0
    for i in range(N):
        for j in range(W+1):
            dp[i+1][j]=dp[i][j]
            if j-w[i]>=0:
                if dp[i][j]<dp[i][j-w[i]]+v[i]:
                    dp[i+1][j]=dp[i][j-w[i]]+v[i]
    print(dp[N][W])


### FIXED CODE ###

N,W=map(int,input().split())
w=[0 for i in range(N)]
v=[0 for i in range(N)]
for i in range(N):
    w[i],v[i]=map(int,input().split())
V=sum(v)
INF=10**15
dp=[[INF for j in range(V+1)] for i in range(N+1)]
#dp[i][j]:iまで試して価値の合計がjのときの重さの最小値
dp[0][0]=0
for i in range(N):
    for j in range(V+1):
        if j-v[i]>=0:
            dp[i+1][j]=min(dp[i][j],dp[i][j-v[i]]+w[i],INF)
        else:
            dp[i+1][j]=min(dp[i][j],INF)
b=[]
for i in range(V+1):
    if dp[N][i]!=INF:
        b.append((dp[N][i],i))
ans=0
for (x,y) in b:
    if x<=W:
        ans=max(ans,y)
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
p = [int(x) for x in input().split()]

sum = 0
e = [0] * 1001
for i in range(1, 1000 + 1):
    sum += i
    e[i] = sum / i
    # print(i, e[i])

maxV = 0
maxI = 0
for i in range(N-K+1):
    tmp = 0
    for j in range(i, i+K):
        tmp += p[j] 
    if tmp > maxV:
        maxV = tmp
        maxI = i

ans = 0
for i in range(maxI, maxI + K):
    ans += e[p[i]]

print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
p = [int(x) for x in input().split()]

sum = 0
e = [0] * 1001
for i in range(1, 1000 + 1):
    sum += i
    e[i] = sum / i
    # print(i, e[i])


maxV = 0
maxI = 0
for i in range(0, K):
    maxV += p[i]

tmp = maxV
# [1 ..  2]
for i in range(1, N-K+1):
    tmp -= p[i-1]
    tmp += p[i+K-1] 
    if tmp > maxV:
        maxV = tmp
        maxI = i
    
    
    
    
    

ans = 0
for i in range(maxI, maxI + K):
    ans += e[p[i]]

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

import itertools
import sys

def readline():
    return sys.stdin.readline()

def read_int_list():
    return list(map(int, readline().split()))

def read_int():
    return int(readline())

def main():
    N, M, R = read_int_list()

    r = [a-1 for a in read_int_list()]

    d = [[float('inf')]*N for _ in range(N)]

    for _ in range(M):
        a, b, c = read_int_list()
        d[a-1][b-1] = c
        d[b-1][a-1] = c

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

    res = float('inf')

    for a, b, c in itertools.product(range(N), repeat=3):
        d[b][c] = min(d[b][c], d[b][a]+d[a][c])

    for perm in itertools.permutations(r):
        a = 0
        for i in range(len(perm)-1):
            a += d[perm[i]][perm[i+1]]
        res = min(a, res)

    print(res)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import itertools
import sys

def readline():
    return sys.stdin.readline()

def read_int_list():
    return list(map(int, readline().split()))

def read_int():
    return int(readline())

def main():
    N, M, R = map(int, input().split())
    r = map(int, input().split())

    inf = float("inf")
    d = [[inf] * (N + 1) for _ in range(N + 1)]
    for n in range(1, N + 1):
        d[n][n] = 0

    for _ in range(M):
        a, b, c = map(int, input().split())
        d[a][b] = c
        d[b][a] = c

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

    min_cost = inf
    for p in itertools.permutations(r):
        cost = 0
        for i in range(len(p) - 1):
            src, dst = p[i:i + 2]
            cost += d[src][dst]
        min_cost = min(min_cost, cost)

    print(min_cost)


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

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

for i in range(1,n+1):
    print(li.index(i)+1,end=" ")

### FIXED CODE ###

n=int(input())
li=list(map(int,input().split()))
an=[0]*n

for i in range(n):
    an[li[i]-1]=i+1

print(*an)
### BUGGY CODE ###

def main():
    n, s = map(int, input().split())
    mod = 998244353
    a = list(map(int, input().split()))
    dp = [[0]*(s+1) for _ in range(n+1)]
    dp[0][0] = 1
    dio = dp[0]
    for i in range(1, n+1):
        ai = a[i-1]
        di = dp[i]
        for j in range(min(s+1, ai)):
            di[j] = (di[j]+2*dio[j])%mod
        for j in range(ai, s+1):
            di[j] = (di[j]+2*dio[j]+dio[j-ai])%mod
        dp[i] = di
        dio = di
    print(dp[n][s])
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n, s = map(int, input().split())
    mod = 998244353
    a = list(map(int, input().split()))
    dp = [[0]*(s+1) for _ in range(n+1)]
    dp[0][0] = 1
    dio = dp[0]
    for i in range(1, n+1):
        ai = a[i-1]
        di = dp[i]
        for j in range(min(s+1, ai)):
            di[j] = (di[j]+2*dio[j])%mod
        for j in range(ai, s+1):
            di[j] = (di[j]+2*dio[j]+dio[j-ai])%mod
        dp[i] = di
        dio = di
    print(dp[n][s])
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

a,v = map(int,input().split())
b,w = map(int,input().split())
t = int(input())
flg = 0

for _ in range(t):
    if a < b:
        if a+v >= b+w:
            flg = 1
        a = a+v
        b= b+w
    else:
        if a-v <= b-w:
            flg = 1
        a = a-v
        b=b-w
        
if flg == 0:
    print("NO")
else:
    print("YES")

### FIXED CODE ###

import sys
a,v = map(int,input().split())
b,w = map(int,input().split())
t = int(input())

if v<=w:
    print("NO")
    sys.exit()

if a<b:
    if a+t*v>=b+t*w:
        print("YES")
    else:
        print("NO")
else:
    if a-t*v<=b-t*w:
        print("YES")
    else:
        print("NO")
### BUGGY CODE ###

n, s = map(int, input().split())
ans = 0
for x in range(n+1):
  for y in range(n+1):
    for z in range(n+1):
      if x + y + z == s:
        ans += 1
print(ans)

### FIXED CODE ###

n, s = map(int, input().split())
ans = 0
for x in range(n+1):
  for y in range(n+1):
    if 0 <= s - x - y <= n:
        ans += 1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 0
flag = True

if n % 2 == 1:
    if 0 not in A:
        flag = False
    for i in range(n//2):
        if A.count(2*(i+1)) != 2:
            flag = False
else:
    for i in range(n//2):
        if A.count(2*i + 1) != 2:
            flag = False

if flag == True:
    ans = 2**(n//2) % (10**9 + 7)

print(ans)

### FIXED CODE ###

n = int(input())
nums = {0:0}

for i in list(map(int, input().split())):
    if i in nums:
        nums[i] += 1
        if nums[i] > 2:
            ans = 0
            break
    else:
        nums[i] = 1
        
if n % 2 == 0:
    if 1 in nums.values():
        ans = 0
    else:
        ans = 2**(n//2)
        
else:
    if nums[0] == 1:
        del nums[0]
        if 1 in nums.values():
            ans = 0
        else:
            ans = 2**((n-1)//2)
    else:
        ans = 0
        
print(ans % (10**9+7))
### BUGGY CODE ###

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

MAX = 999999

p = [[] for _ in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    lrd.append([l-1, r-1, d, 0])
    p[l-1].append(i)
    p[r-1].append(i)

if m <= 1:
    print('Yes')
    exit()

a = [MAX for _ in range(n)]

a[lrd[0][0]] = 0
temp = [lrd[0][0]]
next = []
t = 0
s = 0
max_a = 0
min_a = 0
while 1:
    next = []
    for x in temp:
        for y in p[x]:
            if lrd[y][0] == x:
                t = lrd[y][1]
                s = a[x] + lrd[y][2]
            else:
                t = lrd[y][0]
                s = a[x] - lrd[y][2]

            lrd[y][3] = 1
            if a[t] == MAX:
                a[t] = s
                next.append(t)
            elif a[t] != s:
                print('No')
                exit()

    if len(next) == 0:
        target = 0
        i = 0
        check = 0
        for i in range(m):
            if lrd[i][3] == 0:
                target = lrd[i][0]
                check = 1
        if check == 0:
            break
        a[target] = 0
        next = [target]

    temp = [] + list(set(next))

print('Yes')


### FIXED CODE ###

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

MAX = 999999

p = [[] for _ in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    lrd.append([l-1, r-1, d, 0])
    p[l-1].append(i)
    p[r-1].append(i)

if m <= 1:
    print('Yes')
    exit()

a = [MAX for _ in range(n)]


target = lrd[0][0]
a[target] = 0
temp = [target]
t = 0
while 1:
    next = []
    for x in temp:
        for y in p[x]:
            if lrd[y][3] == 1:
                continue

            if lrd[y][0] == x:
                t = lrd[y][1]
                d = a[x] + lrd[y][2]
            else:
                t = lrd[y][0]
                d = a[x] - lrd[y][2]

            lrd[y][3] = 1

            if a[t] == MAX:
                a[t] = d
                next.append(t)
            elif a[t] != d:
                print('No')
                exit()

    if len(next) == 0:
        check = 0
        for i in range(m):
            if lrd[i][3] == 0:
                check = 1
                target = lrd[i][0]
                break

        if check == 1:
            temp = [target]
            a[target] = 0
            continue
        else:
            break

    temp = [] + list(set(next))

print('Yes')
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]

a.sort()
b = []
c = 0
for i, v in enumerate(a):
    flag = True
    for j in b:          
        if v % j == 0:
            flag = False
            break
        elif v / 2 <= j:
            if a[i-1] == v:
                flag = False
            break
    if flag == True:
        b.append(v)
        if i+1 >= len(a):
            c += 1
        elif a[i+1] != v:
            c += 1
     
print(c)

### FIXED CODE ###

import math
n = int(input())
a = [int(i) for i in input().split()]

a.sort()
b = [0 for _ in range(a[-1])]
c = 0
for i in a:
    x = i-1
    while len(b) > x:
        b[x] += 1
        x += i 
for i in a:
    if b[i-1] == 1:
        c += 1
print(c)
### BUGGY CODE ###

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

# Function of Combination mod M
# set n >= max p expected
M = 10**9+7


if k >= n-1:
    fac = [1]+[0]*(2*n-1)
    for i in range(1,2*n): fac[i] = fac[i-1]*i %M
    comb = lambda p,q:(fac[p]*pow(fac[q],M-2,M)*pow(fac[p-q],M-2,M))%M
    y = comb(2*n-1,n-1)
    
else:

    y = 1
    c1,c2=1,1
    for i in range(1,k+1):
        c1 = c1*(n+1-i)*pow(i,M-2,M) #//i 
        c2 = c2*(n-i)*pow(i,M-2,M)
        y += c1*c2%M
print(y%M)


### FIXED CODE ###

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

# Function of Combination mod M
# set n >= max p expected
M = 10**9+7


if k >= n-1:
    fac = [1]+[0]*(2*n-1)
    for i in range(1,2*n): fac[i] = fac[i-1]*i %M
    comb = lambda p,q:(fac[p]*pow(fac[q],M-2,M)*pow(fac[p-q],M-2,M))%M
    y = comb(2*n-1,n-1)
    
else:
    y = 1
    c1,c2=1,1
    for i in range(1,k+1):
        p = pow(i,M-2,M)
        c1 = c1*(n+1-i)*p%M
        c2 = c2*(n-i)*p%M
        y += c1*c2%M
        # y = (y+c1*c2)%M
print(y%M)
### BUGGY CODE ###

N=int(input())

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

C=[0]*(N-1)
S=[0]*(N-1)
F=[0]*(N-1)

for i in range(N-1):
    C[i],S[i],F[i]=map(int,input().split())

for i in range(N-1):
    Time=0
    for j in range(i,N-1):
        if j==i:
            Time=S[i]
        else:
            cnt=0
            while S[j]+F[j]*cnt<Time+C[j-1]:
                cnt+=1
            Time=S[j]+F[j]*cnt
    Time+=C[N-2]
    print(Time)
print(0)





### FIXED CODE ###

N=int(input())

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


C=[0]*(N-1)
S=[0]*(N-1)
F=[0]*(N-1)

for i in range(N-1):
    C[i],S[i],F[i]=map(int,input().split())

for i in range(N-1):
    Time=0
    for j in range(i,N-1):
        if j==i:
            Time=S[i]
        else:
            cnt=max(0,(Time+C[j-1]-S[j]-1+F[j])//F[j])
            Time=S[j]+F[j]*cnt
    Time+=C[N-2]
    print(Time)
print(0)
### BUGGY CODE ###

from collections import defaultdict
import heapq


vertice,edge,source = map(int,input().split(" "))
link = defaultdict(dict)
weight = defaultdict(dict)
for e in range(edge):
    i,j,w = map(int,input().split(" "))
    link[i] = link.get(i,set()) | {j}
    weight[i].update({j:w})
#print(weight,link)
for v in range(vertice):
    goal = v
    queue = []
    heapq.heappush(queue,(0,source))
    heapq.heapify(queue)
    went = {n:0 for n in range(vertice)}

    while queue != []:
        #print(queue)
        now_cost,here = heapq.heappop(queue)
        #print(now_cost,here,queue)
        if here == goal:
            print(now_cost)
            break

        can_go = link[here]

        #print(v,here,now_cost,not_went,queue)
        for nw in can_go:
            if went[nw]:
                continue
            next_cost = now_cost + weight[here][nw]
            heapq.heappush(queue,(next_cost,nw))
        went[here] = 1
    else:
        print("INF")

### FIXED CODE ###

import sys
from heapq import heappush, heappop
readline = sys.stdin.readline
from collections import defaultdict
vertices, edges, start = map(int, readline().split())
connect = defaultdict(list)
cost = defaultdict(dict)
answer = ["INF" for n in range(vertices)]
for _ in range(edges):
    s, t, w = map(int, readline().split())
    connect[s].append(t)
    cost[s].update({t:w})
 
 
now = start
weight = 0
p_queue = []
heappush(p_queue, (0, now))
visited = set()
while p_queue:
    weight, now = heappop(p_queue)
    if now in visited:
        continue
    visited |= {now}
    answer[now] = weight
    for c in connect[now]:
        if c not in visited:
            heappush(p_queue, (weight + cost[now][c], c))
for a in answer:
    print(a)
### BUGGY CODE ###

N, K = map(int, input().split())
h_list = list(map(int, input().split()))
def chmin(a, b):
    if a > b:
        return b
    else:
        return a
import numpy as np
dp_list = [np.inf] * N
dp_list[0] = 0
dp_list[1] = abs(h_list[1] - h_list[0])
for n in range(1, N):
    for k in range(1, K+1):
        dp_list[n] = chmin(dp_list[n], dp_list[n-k] + abs(h_list[n-k] - h_list[n]))
        if n-k == 0:
            break
print(dp_list[-1])

### FIXED CODE ###

N, K = map(int, input().split())
h_list = list(map(int, input().split()))
def chmin(a, b):
    if a > b:
        return b
    else:
        return a
dp_list = [1000000000] * N
dp_list[0] = 0
dp_list[1] = abs(h_list[1] - h_list[0])
for n in range(1, N):
    for k in range(1, K+1):
        dp_list[n] = chmin(dp_list[n], dp_list[n-k] + abs(h_list[n-k] - h_list[n]))
        if n-k == 0:
            break
print(dp_list[-1])