Harryxun/stf_run huggingface dataset:
mod = 1000000007

class combination():
    def __init__(self, n):
        self.fact = [1] * (n+1)
        self.ifact = [1] * (n+1)
        for i in range(1, n+1):
            self.fact[i] = self.fact[i-1]*i % mod
        self.ifact[n] = pow(self.fact[n], mod-2, mod)
        for i in range(n, 0, -1):
            self.ifact[i-1] = self.ifact[i]*i % mod
    def comb(self, n, k):
        if k < 0 or k > n: return 0
        comb = self.fact[n]*self.ifact[k]*self.ifact[n-k] %mod
        return comb

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

comb = combination(n-k+1)
for i in range(1, k+1):
    print(comb.comb(n-k+1, i) * comb.comb(k-1, i-1) % mod)

### FIXED CODE ###

mod = 1000000007

class combination():
    def __init__(self, n):
        self.fact = [1] * (n+1)
        self.ifact = [1] * (n+1)
        for i in range(1, n+1):
            self.fact[i] = self.fact[i-1]*i % mod
        self.ifact[n] = pow(self.fact[n], mod-2, mod)
        for i in range(n, 0, -1):
            self.ifact[i-1] = self.ifact[i]*i % mod
    def comb(self, n, k):
        if k < 0 or k > n: return 0
        comb = self.fact[n]*self.ifact[k]*self.ifact[n-k] %mod
        return comb

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

comb = combination(n)
for i in range(1, k+1):
    print(comb.comb(n-k+1, i) * comb.comb(k-1, i-1) % mod)
cube = input('>> ')
print(cube **3 )

### FIXED CODE ###

x = int(input())

print(x **3)
N=int(input())
A=list(map(int,input().split()))
B=A.copy()
B.sort()
A_max=B[N]+N
sum_A=[0]*(A_max+1)
for i in range(A_max+1):
  for num in range(N):
    sum_A[i]+=abs(A[num]-i)
sum_A.sort()
print(sum_A[0])
    
  
  




### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=[]
for i in range(N):
  B.append(A[i]-(i+1))
B.sort()
if N%2==0:
  a=N/2
  b=int((B[int(a)]+B[int(a-1)])/2)
else:
  a=(N+1)/2
  b=B[int(a-1)]
for i in range(N):
  B[i]=abs(B[i]-b)
print(sum(B))
S = input()
if S[:2] == "00":
  if S[2:] > 12:
  	print("NA")
  else:
    print("YYMM")
elif S[2:] == "00":
  if S[:2] > 12:
  	print("NA")
  else:
    print("MMYY")
elif int(S[:2]) > 12 and S[2:] > 12:
  print("NA")
elif int(S[:2]) < 13 and S[2:] < 13:
  print("AMBIGUOUS")
elif int(S[:2]) < 13:
  print("MMYY")
else:
  print("YYMM")

### FIXED CODE ###

S = input()
if S[:2] == "00":
  if int(S[2:]) > 12 or S[2:] == "00":
  	print("NA")
  else:
    print("YYMM")
elif S[2:] == "00":
  if int(S[:2]) > 12:
  	print("NA")
  else:
    print("MMYY")
elif int(S[:2]) > 12 and int(S[2:]) > 12:
  print("NA")
elif int(S[:2]) < 13 and int(S[2:]) < 13:
  print("AMBIGUOUS")
elif int(S[:2]) < 13:
  print("MMYY")
else:
  print("YYMM")
a, b, h = map(int, input().split())
s = (a+b)*h/2
print(int(s))

### FIXED CODE ###

a = int(input())
b = int(input())
h = int(input())
print(int((a+b)*h/2))
p,q= input().split()
a,b =(int(p), int(q))
a_list = []
count_row = 0
for i in range(a):
    c = input()
    
    if c == '.'*b:
        count_row+=1
    else:
        a_list.append(c)
for i in range(b):
    count_clm = 0
    
    for j in range(a-count):
        if a_list[j][i] == '.':
            count_clm+=1
        else:
            break
    if count_clm == (b-count_clm):
        for j in range(a-count_row):
            a_list[j].pop(i)
            
            
for i in range(a-count_row):
    print(a_list[i])

### FIXED CODE ###

p,q= input().split()
a,b =(int(p), int(q))
a_list = []
count_row = 0
b_h ='.'*b

for i in range(a):
    c = input()
    
    if c == b_h:
        count_row+=1
    else:
        a_list.append(c)

ans_list=[]
for i in range(b):
    count_clm = 0
    
    for j in range(a-count_row):
        if a_list[j][i] == '.':
            count_clm+=1
    
    
        if count_clm == (a-count_row):        
            ans_list.append(i)



for j in range(a-count_row):
    total=''
    for i in range(b):
        if i in ans_list:
            ds = 0
        else:
            total +=a_list[j][i]
            
    print(total)
n, k = map(int, input().split())
 
member = [0]*n
 
for i in range(k):
    d = int(input())
    a = [int(x) for x in input().split()]
    for j in range(d):
        
        member[a[j]-1] += 1
 
print(member.count(0))


### FIXED CODE ###

S = input()

if S =='ABC':
  print('ARC')
else:
  print('ABC')
s = list(input())
answer = []

for i range s:
        if  i == "B":
            try:
                answer.pop()
            except:
                pass
        else:
            answer.append(i)

print(answer)

### FIXED CODE ###

s = list(input())
answer = []

for i in s:
        if  i == "B":
            try:
                answer.pop()
            except IndexError:
                pass
        else:
            answer.append(i)

print("".join(answer))
# -*- coding: utf-8 -*-
from math import gcd
n,x = map(int, input().split())
ary = [abs(x-int(i)) for i in input().split()]

d = ary[0]
for i in ary[1:]:
    d = gcd(i,d)

print(d)


### FIXED CODE ###

# -*- coding: utf-8 -*-
from fractions import gcd
n,x = map(int, input().split())
ary = [abs(x-int(i)) for i in input().split()]

d = ary[0]
for i in ary[1:]:
    d = gcd(i,d)

print(d)
A,B,C=int(input()),int(input()),int(input())
if (A-B)>=C:
    print('0')
else:
    print(C-(A-B))

### FIXED CODE ###

A,B,C=map(int,input().split())
if (A-B)>=C:
    print(0)
else:
    ans=C-A+B
    print(ans)
N, K = map(int, input().split())
menu_ = []

for i in range(N):
    t, d = map(int, input().split())
    menu_.append((t, d))

menu = sorted(menu_, key = lambda x:x[1], reverse=True)
neta = set()
duplicates = []

for m in menu[:K]:
    if m[0] in neta:
        duplicates.append(m[1])
    else:
        neta.add(m[0])

p = sum([d for (t, d) in menu[:K]]) + len(neta)**2
ans = p

for m in menu[K:]:
    if m[0] not in neta:
        neta.add(m[0])
        duplicate = duplicates.pop()
        
        p += (m[1] - duplicate) + 2 * len(neta) - 1 
        #print(ans, p)
        ans = max(ans, p)

print(ans) 

### FIXED CODE ###

N, K = map(int, input().split())
menu_ = []

for i in range(N):
    t, d = map(int, input().split())
    menu_.append((t, d))

menu = sorted(menu_, key = lambda x:x[1], reverse=True)
neta = set()
duplicates = []

for m in menu[:K]:
    if m[0] in neta:
        duplicates.append(m[1])
    else:
        neta.add(m[0])

p = sum([d for (t, d) in menu[:K]]) + len(neta)**2
ans = p

for m in menu[K:]:
    if m[0] not in neta and duplicates:
        neta.add(m[0])
        duplicate = duplicates.pop()
        
        p += (m[1] - duplicate) + 2 * len(neta) - 1 
        #print(ans, p)
        ans = max(ans, p)

print(ans)
def main()
    s = input()
    f = False
    if s.count('C') == 0 or s.count('F') == 0:
        print('NO')
        return
    for i in range(len(s)):
        if s[i] == 'C':
            for j in range(i, len(s)):
                if s[j] == 'F':
                    print('Yes')
                    f = True
                    break
            if f == False:
                print('No')
main()

### FIXED CODE ###

s=input();pd=0
for i in range(0,len(s)):
    if s[i]=='C':
        pd=1
    if s[i]=='F'and pd==1:
        print('Yes')
        pd=2
        break
if pd!=2:
    print('No')
if input().count("5")==2 and input().count("7")==1:
                  print("YES")
    else:
                  print("NO")

### FIXED CODE ###

a=input().split()
if a.count("5")==2 and a.count("7")==1:
   print("YES")
else:
   print("NO")
#!usr/bin/env python3
from collections import defaultdict,deque
import sys
import math
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
mod = 1000000007

def solve():
    def dfs(x):
        res = 1
        for y in v[x]:
            if d[y]:
                d[y] = 0
                res += dfs(y)
        t[x] = res
        return res

    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    t = [0]*n
    d = [1]*n
    d[0] = 0
    dfs(0)
    ans = 0
    p = pow(2,n-1,mod)
    for x in range(n):
        tx = t[x]
        if len(v[x]) < 2:
            continue
        s = p-1
        for y in v[x]:
            ty = t[y]
            if tx < ty:
                s -= pow(2,t[0]-tx,mod)-1
            else:
                s -= pow(2,ty,mod)-1
            s %= mod
        ans += s
        ans %= mod
    print(ans*pow(2,(mod-2)*n,mod)%mod)
    return

#Solve
if __name__ == "__main__":
    solve()


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    q = deque([0])
    d = [0]*n
    d[0] = 1
    pre = [None]*n
    while q:
        x = q.popleft()
        nd = d[x]+1
        for y in v[x]:
            if not d[y]:
                d[y] = nd
                pre[y] = x
                q.append(y)
    V = list(range(1,n))
    V.sort(key = lambda x:-d[x])
    size = [1]*n
    for i in V:
        size[pre[i]] += size[i]
    inv = pow(2,mod-2,mod)
    ans = (1-pow(inv,n,mod)-n*inv)%mod
    p = [pow(inv,i,mod) for i in range(n)]
    for i in range(1,n):
        a = size[i]
        b = n-a
        ans += (p[a]-1)*(p[b]-1)%mod
        ans %= mod
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()
a,b=int(input())
print("Yay!" if a<=8 and b<=8 else ":(")

### FIXED CODE ###

a,b=map(int,input().split())
print("Yay!" if a<=8 and b<=8 else ":(")
# D - AtCoder Express 2

import bisect, copy

N, M, Q = map(int, input().split())
LRidx = [list(map(int, input().split())) + [i] for i in range(M)]
p, q = [], []
for _ in range(Q):
    tmp_p, tmp_q = map(int, input().split())
    p.append(tmp_p)
    q.append(tmp_q)

# l,rはそれぞれ高々500通りなので、l,rの値に対して探索結果をメモしておく
LRidx = sorted(LRidx, key = lambda x: x[0])
tmp_L = [LRidx[idx][0] for idx in range(M)]
l_memo = [[-1] for _ in range(N+1)]
l_ok_idx = [[] for _ in range(Q)]
for i in range(Q):
    if l_memo[p[i]][0] == -1:
        b_idx = bisect.bisect_left(tmp_L, p[i])
        try:
            tmp = []
            for j in range(bisect.bisect_left(tmp_L, p[i]), M):
                tmp.append(LRidx[j][2])
            l_ok_idx[i] = copy.deepcopy(tmp)
            l_memo[p[i]] = copy.deepcopy(tmp)
        except:
            pass
    else:
        l_ok_idx[i] = copy.deepcopy(l_memo[p[i]])
    
LRidx = sorted(LRidx, key = lambda x: x[1])
tmp_R = [LRidx[idx][1] for idx in range(M)]
r_memo = [[-1] for _ in range(N+1)]
r_ok_idx = [[] for _ in range(Q)]
for i in range(Q):
    if r_memo[q[i]][0] == -1:
        b_idx = bisect.bisect_right(tmp_R, q[i])
        tmp = []
        for j in range(b_idx):
            tmp.append(LRidx[j][2])
        r_ok_idx[i] = copy.deepcopy(tmp)
        r_memo[q[i]] = copy.deepcopy(tmp)
    else:
        r_ok_idx[i] = copy.deepcopy(r_memo[q[i]])
    
for i in range(Q):
    print(len(set(l_ok_idx[i]) & set(r_ok_idx[i])))

### FIXED CODE ###

# D - AtCoder Express 2

import numpy as np

N, M, Q = map(int, input().split())
LR = np.zeros((N+1, N+1))

for _ in range(M):
    l, r = map(int, input().split())
    LR[l,r] += 1

np.cumsum(LR, axis = 0, out = LR)
np.cumsum(LR, axis = 1, out = LR)
    
for _ in range(Q):
    p, q = map(int, input().split())
    print(int(LR[q,q] - LR[p-1,q] - LR[q,p-1] + LR[p-1,p-1]))
N = str(input())
if N.isin('7'):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

N = str(input())
if '7' in N:
    print("Yes")
else:
    print("No")
#ABC 141 C  Attack Survival
N,K,Q= map(int,input().split())
A=[K-Q]*N
for i in range(1,Q+1):
    A[int(input())]+=1
for a in A:
    if a < 1:
        print('No')
    else:
        print('Yes')

### FIXED CODE ###

#ABC 141 C  Attack Survival
N,K,Q= map(int,input().split())
A=[K-Q]*N
for i in range(Q):
    A[int(input())-1]+=1
for a in A:
    if a < 1:
        print('No')
    else:
        print('Yes')
import numpy as np

def main():
    H,N = [int(x) for x in input().split()]
    A,B = [],[]
    for _ in range(N):
        a,b = [int(x) for x in input().split()]
        A.append(a)
        B.append(b)

    # dp = np.full((N+1,H+1),10 ** 18)
    # dp[0][0] = 0
    dp = [float('inf')]*(H+1)
    dp[0] = 0
    for i in range(N):
        for j in range(H+1):
            # print(i,j,dp[j],A[i],B[i])
            dp[min(j+A[i],H)] = min(dp[min(j+A[i],H)], dp[j]+B[i])
            # dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            # dp[i+1][min(j+A[i],H)] = min(dp[i+1][j]+B[i], dp[i+1][min(j+A[i],H)])
            # print(dp)
    print(int(dp[H]))


if __name__ == '__main__':
    main()

### FIXED CODE ###

# import numpy as np

def main():
    H,N = [int(x) for x in input().split()]
    A,B = [],[]
    for _ in range(N):
        a,b = [int(x) for x in input().split()]
        A.append(a)
        B.append(b)

    # dp = np.full((N+1,H+1),10 ** 18)
    # dp[0][0] = 0
    dp = [float('inf')]*(H+1)
    dp[0] = 0
    for i in range(N):
        for j in range(H+1):
            # print(i,j,dp[j],A[i],B[i])
            dp[min(j+A[i],H)] = min(dp[min(j+A[i],H)], dp[j]+B[i])
            # dp[i+1][j] = min(dp[i+1][j], dp[i][j])
            # dp[i+1][min(j+A[i],H)] = min(dp[i+1][j]+B[i], dp[i+1][min(j+A[i],H)])
            # print(dp)
    print(int(dp[H]))


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

### FIXED CODE ###

p, q, r = map(int, input().split())
 
m = 10e9
 
m = min(m, p + q)
m = min(m, r + q)
m = min(m, p + r)
 
print(m)
def fact(a): return a and a*fact(a-1) or 1

n,m,r = map(int,input().split())
r-=n*m
if r < 0:
    print(0)
else:
    print(fact(r+n-1)//fact(n-1)//fact(r))

### FIXED CODE ###

def fact(n):
    res = 1
    for i in range(1, n+1):
        res *= i
    return res
 
def combination(n, k):
    return fact(n)//fact(n-k)//fact(k)
 
n, m, r = list(map(int, input().split()))
 
print(combination(r - n*m + n - 1, n-1))
n, d = map(int, input().split()
print(-(-n//(2*d+1)))

### FIXED CODE ###

n, d = map(int, input().split())
if n/(2*d +1) == n//(2*d+1):
  print(n//(2*d+1))
else:
  print(n//(2*d+1)+1)
x, n = map(int, input().split())
if n == 0:
    print(x)
    sys.exit()

p = list(map(int, input().split()))

p.sort()

for i in range(len(p)):
    if x -i not in p:
        print(x-i)
        exit()
    elif x +i not in p:
        print(x+i)
        exit()

### FIXED CODE ###

x, n = map(int, input().split())
if n == 0:
    print(x)
    exit()

p = list(map(int, input().split()))

#p.sort()

for i in range(101):
    if x -i not in p:
        print(x-i)
        exit()
    elif x +i not in p:
        print(x+i)
        exit()
def bubblesort(N, A):
    c, flag = 0, 1
    while flag:
        flag = False
        for j in range(N-1, 0, -1):
            if A[j] < A[j-1]:
                A[j], A[j-1] = A[j- 1], A[j]
                c += 1
                flag = True
    return (A, c)

A, c = bubblesort(int(input()), list(map(int, input().split())))
print(A)
print(c)

### FIXED CODE ###

def bubblesort(N, A):
    c, flag = 0, 1
    while flag:
        flag = False
        for j in range(N-1, 0, -1):
            if A[j] < A[j-1]:
                A[j], A[j-1] = A[j- 1], A[j]
                c += 1
                flag = True
    return (A, c)

A, c = bubblesort(int(input()), list(map(int, input().split())))
print(' '.join([str(v) for v in A]))
print(c)
# -*- coding: utf-8 -*-
MOD = 1000000007
N, M = map(int, input().split())
a = []
for _ in range(M):
    a.append(int(input()))


def getPatternNum(num):
    pattern = [0] * num
    for i in range(num):
        if i == 0 or i == 1:
            pattern[i] = 1
            continue
        pattern[i] = pattern[i - 2] + pattern[i - 1]
    return pattern


def solve():
    # 階段の連続してる数のリスト
    stepsList = [0] * (M + 1)
    maxSteps = 0
    stepsList[0] = a[0] - 1
    for j in range(1, M):
        stepsList[j] = a[j] - a[j - 1] - 1
        if stepsList[j] == 0:
            return 0
    stepsList[M] = N - a[M - 1] - 1
    pattern = getPatternNum(max(stepsList) + 1)
    # こわれてるところ以外のパターンを掛ける
    for k in range(len(stepsList)):
        if k == 0:
            total = pattern[stepsList[k]]

        else:
            total = total * (pattern[stepsList[k]]) % MOD

    return total


ans = solve()
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
MOD = 1000000007
N, M = map(int, input().split())
a = []
for _ in range(M):
    a.append(int(input()))

# 0-num段目までのパターン数を取得する
# numは連続した階段の一番高いところが何段目かを意味する


def getPatternNum(num):
    pattern = [0] * num
    for i in range(num):
        if i == 0 or i == 1:
            pattern[i] = 1
            continue
        pattern[i] = (pattern[i - 2] + pattern[i - 1]) % MOD
    return pattern


def solve():
    # 階段の連続してる数のリスト

    if M > 0:
        stepsList = [0] * (M + 1)
        maxSteps = 0
        stepsList[0] = a[0]
        for j in range(1, M):
            stepsList[j] = a[j] - a[j - 1] - 1
            if stepsList[j] == 0:
                return 0
        stepsList[M] = N - a[M - 1]
    else:
        stepsList = [N + 1]

    # 連続数が一番大きいところの一番上の段を引数でわたす
    pattern = getPatternNum(max(stepsList) + 1)

    # こわれてるところ以外のパターンを掛ける
    for k in range(len(stepsList)):
        if k == 0:
            # 連続段数が３なら一番上の段は０段目から数えて２段目になるため１引く
            total = pattern[stepsList[k] - 1]

        else:
            total = (total * (pattern[stepsList[k] - 1])) % MOD

    return total


print(solve())
s = input()
q = int(input())
q1 = [list(map(str,input().split())) for i in range(q)]

ap = ["", ""]
revCount = 0

for j in q1:
  if j[0] == "1":
    revCount = (revCount+1) % 2

  else:
    if revCount == 0:
      ap[j[1] - 1] = ap[j[1] - 1] + j[2]
    else:
      ap[j[1] - 2] = ap[j[1] - 2] + j[2]
        

if revCount == 0:
  ap[0] = ap[0][::-1]
  print(ap[0] + s + ap[1])

else:
  aps = (s+ap[1])[::-1]
  print(aps + ap[0])


### FIXED CODE ###

s = input()
q = int(input())
q1 = [list(map(str,input().split())) for i in range(q)]

ap = ["", ""]
revCount = 0

for j in q1:
  if j[0] == "1":
    revCount = revCount ^ 1

  else:
    ind = revCount ^ int(j[1]) - 1
    ap[ind] = ap[ind] + j[2]

if revCount == 0:
  ap[0] = ap[0][::-1]
  print(ap[0] + s + ap[1])

else:
  aps = (s+ap[1])[::-1]
  print(aps + ap[0])
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
V = []
W = []
for _ in range(n):
    v, w = LI()
    V.append(v)
    W.append(w)

q = I()
vl = []
maxL = 0
for _ in range(q):
    v, l = LI()
    maxL = max(maxL, l)
    vl.append([v,l])

m = int(math.sqrt(n))
dp = [[0]*(maxL + 1) for _ in range(m + 1)]

for i in range(1, m+1):
    for j in range(maxL+1):
        if j < W[i-1]:
            dp[i][j] = dp[i//2][j]
        else:
            dp[i][j] = max(dp[i//2][j],dp[i//2][j-W[i-1]] + V[i-1])

for i in range(q):
    v, L = vl[i]
    if v <= m:
        print(dp[v][L])
        continue
    x = v.bit_length() - m.bit_length()
    ret = 0
    for j in range(1 << x):
        weight_sum = 0
        value_sum = 0
        tmp = v
        idx = j
        for _ in range(x):
            if idx & 1:
                weight_sum += W[tmp - 1]
                if weight_sum > L:
                    break
                value_sum += V[tmp - 1]
            tmp //= 2
            idx >>= 1 
        else:
            value_sum += dp[tmp][L - weight_sum]
            ret = max(ret, value_sum)
    print(ret)


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []

    maxL = 10**5
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1)]
    
    for i in range(n):
        v, w = LI()
        if i <= m:
            d_ = dp[(i+1)>>1][:]
            for j in range(w, maxL+1)[::-1]:
                d_[j] = max(d_[j], d_[j - w] + v)
            dp.append(d_)
        V.append(v)
        W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        v_ = []
        w_ = []
        while v > m:
            v_.append(V[v-1])
            w_.append(W[v-1])
            v >>= 1
            cnt += 1
        ret = dp[v][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_t = w_tmp[b - lsb] + w_[l-1]
            w_tmp[b] = w_t
            if w_t <= L:
                v_t = v_tmp[b - lsb] + v_[l-1]
                v_tmp[b] = v_t
                ret = max(ret, v_t + dp[v][L - w_t])
        print(ret)
    return

if __name__ == "__main__":
    main()
n = int(input())
a = list(map(int, input().split()))
c = []
for i in range(n):
    c += [i+1]*a[i]
ans = []
for h_ in range(h):
    a = c[h_*w: w+h_*w]
    if h_ % 2 == 0:
        ans.append(a)
    else:
        ans.append(a[::-1])
for i in ans:
    print(*i)

### FIXED CODE ###

h, w = map(int, input().split())
n = int(input())
a = list(map(int, input().split()))
c = []
for i in range(n):
    c += [i+1]*a[i]
ans = []
for h_ in range(h):
    a = c[h_*w: w+h_*w]
    if h_ % 2 == 0:
        ans.append(a)
    else:
        ans.append(a[::-1])
for i in ans:
    print(*i)
from math import ceil,log2

def Bellman_Ford(node_num:int,start:int,VWC:list)->list:
    Ans = [float("inf")]*(node_num + 1)
    node = start
    Ans[start] = 0
    changeable = {}
    for v,w,c in VWC:
        if v not in changeable:
            changeable[v] = True
        if w not in changeable:
            changeable[w] = True
        
    for _ in range(node_num-1):
        for v,w,c in VWC:
            Ans[w] = min(Ans[w], Ans[v] + c)
    Pre = Ans.copy()
    for _ in range(2*(node_num-1)):
        for v,w,c in VWC:
            Ans[w] = min(Ans[w], Ans[v] + c)
    for node in changeable.keys():
        if Ans[node] == Pre[node]:
            return Ans
    return [float("inf")]*(node_num + 1)

def main():
    N,M = map(int,input().split())
    ABC = [list(map(int,input().split())) for _ in  range(M)]
    newABC = [[a,b,-c] for a,b,c in ABC]
    Ans1 = Bellman_Ford(N,1,newABC)
    print("inf" if Ans1[N] == float("inf") else -Ans1[N])
    return
if __name__ == "__main__":
    main()

### FIXED CODE ###


def Bellman_Ford(node_num:int,start:int,goal:int,VWC:list)->list:
    Ans = [float("inf")]*(node_num + 1)
    node = start
    Ans[start] = 0        
    for _ in range(node_num-1):
        for v,w,c in VWC:
            Ans[w] = min(Ans[w], Ans[v] + c)
    Pre = list(Ans)
    for _ in range(node_num-1):
        for v,w,c in VWC:
            Ans[w] = min(Ans[w], Ans[v] + c)
    if Ans[goal] == Pre[goal]:
        return Ans[goal]
    else:
        return float("inf")
def main():
    N,M = map(int,input().split())
    ABC = [list(map(int,input().split())) for _ in  range(M)]
    newABC = [[a,b,-c] for a,b,c in ABC]
    ans = Bellman_Ford(N,1,N,newABC)
    print(-ans if ans < float("inf") else "inf")
    return


if __name__ == "__main__":
    main()