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

N,M,P=map(int,input().split())
A=[0 for i in range(M)]
B=[0 for i in range(M)]
C=[0 for i in range(M)]
G=[dict() for i in range(N)]
H=[dict() for i in range(N)]
for i in range(M):
    A[i],B[i],C[i]=map(int,input().split())
    G[B[i]-1][A[i]-1]=C[i]
    H[A[i]-1][B[i]-1]=C[i]
reached1=[0 for i in range(N)]
q=[N-1]
while(len(q)>0):
    r=q.pop()
    reached1[r]=1
    for p in G[r]:
        if reached1[p]==0:
            q.append(p)
reached2=[0 for i in range(N)]
q=[0]
while(len(q)>0):
    r=q.pop()
    reached2[r]=1
    for p in H[r]:
        if reached2[p]==0:
            q.append(p)
reached=[reached1[i]*reached2[i] for i in range(N)]
vertex_list=[]
vertex_num=[-1 for i in range(N)]
tmp=1
for i in range(N):
    if reached[i]==1:
        vertex_list.append(i+1)
        vertex_num[i]=tmp
        tmp+=1
num_v=len(vertex_list)
edges=[]
for i in range(M):
    if reached[A[i]-1]==1 and reached[B[i]-1]==1:
        edges.append((vertex_num[A[i]-1],vertex_num[B[i]-1],P-C[i]))
inf=10**10
dist=[inf for i in range(num_v)]
dist[0]=0
#print(reached)
#print(edges)
#print(vertex_list)
#print(vertex_num)
#辺の緩和
for i in range(num_v):
    for edge in edges:
        if edge[0] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
            dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
            if i==num_v-1:
                print(-1)
                exit()
print(max(-dist[-1],0))


### FIXED CODE ###

N,M,P=map(int,input().split())
A=[0 for i in range(M)]
B=[0 for i in range(M)]
C=[0 for i in range(M)]
G=[dict() for i in range(N)]
H=[dict() for i in range(N)]
for i in range(M):
    A[i],B[i],C[i]=map(int,input().split())
    G[B[i]-1][A[i]-1]=C[i]
    H[A[i]-1][B[i]-1]=C[i]
reached1=[0 for i in range(N)]
q=[N-1]
while(len(q)>0):
    r=q.pop()
    reached1[r]=1
    for p in G[r]:
        if reached1[p]==0:
            q.append(p)
reached2=[0 for i in range(N)]
q=[0]
while(len(q)>0):
    r=q.pop()
    reached2[r]=1
    for p in H[r]:
        if reached2[p]==0:
            q.append(p)
reached=[reached1[i]*reached2[i] for i in range(N)]
vertex_list=[]
vertex_num=[-1 for i in range(N)]
tmp=1
for i in range(N):
    if reached[i]==1:
        vertex_list.append(i+1)
        vertex_num[i]=tmp
        tmp+=1
num_v=len(vertex_list)
edges=[]
for i in range(M):
    if reached[A[i]-1]==1 and reached[B[i]-1]==1:
        edges.append((vertex_num[A[i]-1],vertex_num[B[i]-1],P-C[i]))
inf=10**10
dist=[inf for i in range(num_v)]
dist[0]=0
#print(reached)
#print(edges)
#print(vertex_list)
#print(vertex_num)
#辺の緩和
for i in range(num_v):
    for edge in edges:
        if edge[0] != inf and dist[edge[1]-1] > dist[edge[0]-1] + edge[2]:
            dist[edge[1]-1] = dist[edge[0]-1] + edge[2]
            if i==num_v-1:
                print(-1)
                exit()
print(max(-dist[-1],0))
### BUGGY CODE ###

l=input()
deg=len(l)-1
mod=10**9+7
ans=(3**deg)%mod
x=[]
n=len(l)
for i in range(1,n+1):
    if l[-i]=='1':
        x.append(i)
c=len(x)
ans+=2**c
for i in range(1,c):
    ans+=((2**(c-i))*(3**(x[i-1]-1)))%mod
    ans%=mod
print(ans)

### FIXED CODE ###

l=input()
deg=len(l)-1
mod=10**9+7
ans=(3**deg)%mod
x=[]
n=len(l)
for i in range(1,n+1):
    if l[-i]=='1':
        x.append(i)
c=len(x)
ans+=2**c
two=(2**c)%mod
three=1
x_ref=1
for i in range(1,c):
    if two%2==0:
        two=two//2
    else:
        two=(two+mod)//2
    three=(three*3**(x[i-1]-x_ref))%mod
    x_ref=x[i-1]
    ans+=(two%mod)*(three%mod)
    ans%=mod
print(ans)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right

def solve():
    N, M = map(int, input().split())
    As = list(map(int, input().split()))

    As.sort()

    def isOK(x):
        num = 0
        for A in As:
            i = bisect_left(As, x-A)
            num += N-i
        return num >= M

    ng, ok = 2*10**5+1, 0
    while abs(ok-ng) > 1:
        mid = (ng+ok) // 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid
#    print('ok:', ok)

    scores = []
    for A in As:
        i = bisect_right(As, ok-A)
        for B in As[i:]:
            scores.append(A+B)
#    print('scores:', scores, len(scores))

    ans = sum(scores) + ok*(M-len(scores))
    print(ans)


solve()


### FIXED CODE ###

from bisect import bisect_left, bisect_right

maxA = 10**5

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

As.sort()

def isOK(v):
    num = 0
    for A in As:
        i = bisect_left(As, v-A)
        num += N-i
    return num >= M

ng, ok = 2*maxA+1, 0
while abs(ok-ng) > 1:
    mid = (ng+ok) // 2
    if isOK(mid):
        ok = mid
    else:
        ng = mid

accRevAs = [As[-1]]
for A in reversed(As[:-1]):
    accRevAs.append(accRevAs[-1]+A)
accRevAs.reverse()

v = ok
ans = 0
numGt = 0
#numEq = 0
for A in As:
#    iL = bisect_left(As, v-A)
    iR = bisect_right(As, v-A)
    if iR < N:
        ans += accRevAs[iR] + A*(N-iR)
    numGt += N-iR
#    numEq += iR-iL

ans += v * (M-numGt)
print(ans)
### BUGGY CODE ###

N = int(input())

import math

for i in range(int(math.sqrt(N)), N):
    if N % i == 0:
        print(i-1 + int(N / i) -1)
        break


### FIXED CODE ###

N = int(input())

def divisors(n, sort=False):
    """
    nの約数をO(√n)で列挙する
    """
    d = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            d.append((i, n//i))  #タプル括弧の中に数字が二つはいる
    if sort:
        d.sort()
    return d
l = []
for d1, d2 in divisors(N):
    m = d1 + d2
    l.append(m)
print(min(l) - 2)
### BUGGY CODE ###

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

while M - 2 * N > 0:
  M -= 2
  N += 1

print(M // 2)

### FIXED CODE ###

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

x = M - 2 * N
if x > 0:
  N += x // 4

print(min(N, M // 2))
### BUGGY CODE ###

N, K, Q = list(map(int, input().split()))
points = [K for x in range(N)]

for i in range(Q):
    s = int(input())
    points = list(map(lambda x: x-1, points))
    points[s-1] += 1

for point in points:
    if point <= 0:
        print('No')
    else:
        print('Yes')

### FIXED CODE ###

N, K, Q = list(map(int, input().split()))
points = [K for x in range(N)]
points = list(map(lambda x: x-Q, points))
for i in range(Q):
    s = int(input())
    points[s-1] += 1

for point in points:
    if point <= 0:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

n = int(input())
a, b = [], []
for _ in range(n):
    x, y = map(int, input().split())
    a.append(x)
    b.append(y)


who = True
dishes = list(range(n))
takahashi = aoki = 0
while dishes:
    if who:
        dishes.sort(key=lambda dish: (b[dish], a[dish]))
        takahashi += a[dishes.pop()]
    else:
        dishes.sort(key=lambda dish: (a[dish], b[dish]))
        aoki += b[dishes.pop()]
    who = not who

print(takahashi - aoki)


### FIXED CODE ###

n = int(input())
dishes = []
for _ in range(n):
    a, b = map(int, input().split())
    dishes.append((a, b, a + b))
dishes.sort(key=lambda dish: dish[2], reverse=True)

x = y = 0
for i in range(n):
    a, b, _ = dishes[i]
    if i % 2 == 0:
        x += a
    else:
        y += b

print(x - y)
### BUGGY CODE ###

import numpy as np

def main():
    n,m,q=map(int,input().split())
    lst=np.zeros((n,n),dtype=int)

    for _ in range(m):
        s,t=map(int,input().split())
        lst[:s,t-1:]+=1
    
    for _ in range(q):
        s,t=map(int,input().split())
        print(lst[s-1][t-1])

main()

### FIXED CODE ###

import numpy as np

def main():
    n,m,q=map(int,input().split())
    lst=np.zeros((n,n),dtype=int)

    for _ in range(m):
        s,t=map(int,input().split())
        lst[s-1][t-1]+=1
    lst=lst.cumsum(axis=1)[::-1].cumsum(axis=0)[::-1]

    for _ in range(q):
        s,t=map(int,input().split())
        print(lst[s-1][t-1])

main()
### BUGGY CODE ###

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

change = False
str_list = list(s)
for data in w:
    if int(data[0]) == 1:
        change = not change
    else:
        if change:
            change = False
            str_list.reverse()
        if int(data[1]) == 1:
            str_list.insert(0, data[2])
        else:
            str_list.append(data[2])
if change:
    str_list.reverse()
print("".join(str_list))

### FIXED CODE ###

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

reverse = False
front_list = []
end_list = []

for data in w:
    if int(data[0]) == 1:
        reverse = not reverse
    else:
        if (int(data[1]) == 1 and not reverse) or (int(data[1]) == 2 and reverse):
            front_list.append(data[2])
        else:
            end_list.append(data[2])
if not reverse:
    front_list.reverse()
    print("".join(front_list + s + end_list))
else:
    end_list.reverse()
    s.reverse()
    print("".join(end_list + s + front_list))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
import collections

def main():
    N = int(input())
    Q = [collections.deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    while 1:
        gamed = 0
        for i in range(N-1):
            if (gamed >> i) % 2 or not len(Q[i]):
                continue
            j = Q[i][0] - 1
            if (gamed >> j) % 2 or not len(Q[j]):
                continue
            if Q[j][0] == i+1:
#                print("game:", j+1, i+1, days)
                Q[i].popleft()
                Q[j].popleft()
                gamed += 1<<i
                gamed += 1<<j
                games -= 1
        days += 1
        if not gamed:
            print(-1)
            return
        if games == 0:
            break

    print(days)
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline
from collections import deque

def main():
    N = int(input())
    Q = [deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    nxt = [i for i in range(N)] # 翌日に対戦相手を更新する選手のリスト
    opp = [0]*N # 選手毎の、次の対戦相手のリスト
    while 1:
        days += 1
        for i in nxt:
            opp[i] = Q[i].popleft() - 1 if Q[i] else -1

        tmp = set() # 次の日の更新のため、試合をした選手をメモ
        for i in nxt:
            if i not in tmp and i == opp[opp[i]]:
#                print("game:", i+1, opp[i]+1, days)
                tmp.add(i)
                tmp.add(opp[i])
                games -= 1
        if games == 0:
            break
        elif not tmp:
            print(-1)
            return
        nxt = tmp
    print(days)

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

def main():
    import sys
    input = sys.stdin.readline

    N, K = map(int, input().split())
    P = tuple(map(float, input().split()))

    pl = [(K + sum(P[i:i+K])) * 0.5 for i in range(N-K+1)]
    ans = max(pl)

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import numpy as np

N, K = map(int, input().split())
E = list(map(lambda x: (int(x)+1)/2, input().split()))
E_cumsum = np.cumsum(E)

ans = E_cumsum[K-1]
for i in range(0, N-K):
    e = E_cumsum[i+K] - E_cumsum[i]
    ans = max(ans, e)
print(ans)
### BUGGY CODE ###

n=int(input())
a=[input() for _ in range(n)]
l=[]
for i in range(n):
    if a[i] in l:
        l.remove(a[i])
    else:
        l.append(a[i])
#print(l)
print(len(l))

### FIXED CODE ###

n=int(input())
a=[input() for _ in range(n)]
l={}
for i in a:
    if i in l:
        del l[i]
    else:
        l[i]=0
print(len(l))
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    
    r = 0
    for i in range(n):
        x = a[i]
        if all(x <= a[j] for j in range(i)):
            r += 1
    
    print(r)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    
    d = set()
    mini = a[0]
    for i in range(n):
        if mini >= a[i]:
            mini = a[i]
        d.add(mini)
    print(len(d))

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

xs, ys, xt, yt = map(int, input().split())
n = int(input())
p = [(xs, ys, 0), (xt, yt, 0)]
for i in range(n):
    p.append(tuple(map(int, input().split())))
edge = [[0] * (n + 2) for _ in range(n + 2)]
for i in range(n + 2):
    for j in range(i, n + 2):
        edge[i][j] = max(0, ((p[i][0] - p[j][0])**2 + (p[i][1] - p[j][1])**2)**0.5 - p[i][2] - p[j][2])
        edge[j][i] = max(0, ((p[i][0] - p[j][0])**2 + (p[i][1] - p[j][1])**2)**0.5 - p[i][2] - p[j][2])


def dijkstra(s, n, edges):
    INF = float('inf')
    d = [INF] * n
    d[s] = 0
    import heapq
    pq = [(0, s)]
    while len(pq):
        c, v = heapq.heappop(pq)
        if d[v] < c:
            continue
        # for v2nvcost, nv in edges[v]:
        for nv, v2nvcost in enumerate(edges[v]):
            if c + v2nvcost < d[nv]:
                d[nv] = c + v2nvcost
                heapq.heappush(pq, (d[nv], nv))
    return d


dist = dijkstra(0, n + 2, edge)
print(dist[1])


### FIXED CODE ###

xs, ys, xt, yt = map(int, input().split())
n = int(input())
p = [(xs, ys, 0), (xt, yt, 0)]
for i in range(n):
    p.append(tuple(map(int, input().split())))
edge = [[0] * (n + 2) for _ in range(n + 2)]
for i in range(n + 2):
    for j in range(i, n + 2):
        edge[i][j] = max(0, ((p[i][0] - p[j][0])**2 + (p[i][1] - p[j][1])**2)**0.5 - p[i][2] - p[j][2])
        edge[j][i] = max(0, ((p[i][0] - p[j][0])**2 + (p[i][1] - p[j][1])**2)**0.5 - p[i][2] - p[j][2])


def dijkstra(s, n, edges):
    INF = float('inf')
    d = [INF] * n
    d[s] = 0
    import heapq
    pq = [(0, s)]
    while len(pq):
        c, v = heapq.heappop(pq)
        if d[v] < c:
            continue
        # for v2nvcost, nv in edges[v]:
        for nv, v2nvcost in enumerate(edges[v]):
            if c + v2nvcost < d[nv]:
                d[nv] = c + v2nvcost
                heapq.heappush(pq, (d[nv], nv))
    return d


dist = dijkstra(0, n + 2, edge)
print(dist[1])
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')

#import math
#import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#sys.setrecursionlimit(10**7)

#map(int,input().split())

def main():
	n,m=map(int,input().split())
	li=[]
	li2=[[] for _ in range(n+1)]
	for i in range(m):
		l,r,d=map(int,input().split())
		li.append((l,r,d))
		#li.append((r,l,-d))
		li2[l].append((r,d))
		li2[r].append((l,-d))
	
	stack=[]
	check=set()
	a=[""]*(n+1)

	for i in li:
		if i[0] in check:
			continue
		else:
			stack.append(i[0])
			a[i[0]]=0
			while stack:
				now=stack.pop()
				check.add(now)
				for j in li2[now]:
					if j[0] in check:
						if a[j[0]]-a[now]!=j[1]:
							print("No")
							exit(0)
						else:
							continue
					if j[0] in stack:
						continue
					a[j[0]] = a[now] + j[1]
					stack.append(j[0])
					
	print("Yes")
	
	
if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')

#import math
#import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#sys.setrecursionlimit(10**7)

#map(int,input().split())

def main():
	n,m=map(int,input().split())
	li=[[] for _ in range(n+1)]
	for i in range(m):
		l,r,d=map(int,input().split())
		li[l].append((r,d))
		li[r].append((l,-d))
	
	q=deque()
	a=[None]*(n+1)

	for i in range(1,n+1):
		if a[i]==None:
			q=[i]
			a[i]=0
			while q:
				now=q.pop()
				for r,d in li[now]:
					if a[r]==None:
						a[r] = a[now] + d
						q.append(r)
					else:
						if a[r]-a[now]!=d:
							print("No")
							exit(0)
						else:
							continue
					
	print("Yes")
	
	
if __name__ == '__main__':
	main()
### BUGGY CODE ###

n, k = [int(elem) for elem in input().split()]
h = [int(elem) for elem in input().split()]

def calc_min(h, i, k, dp):
  for j in range(1, k+1):
    if len(h) > (i+j):
      tmp = dp[i] + abs(h[i] - h[i+j])
      if dp[i+j] == 0:
        dp[i+j] = tmp
      else:
        if dp[i+j] > tmp:
          dp[i+j] = tmp
  return dp

dp=[0]*n
for i in range(0, n):
  dp = calc_min(h, i, k, dp)

print(dp[-1])

### FIXED CODE ###

INF = 10**10
 
def main():
    n, k = map(int, input().split())
    hs = list(map(int, input().split()))
 
    dp = [INF]*n
    dp[0] = 0
 
    for i in range(1,n):
        from_ = max(i-k, 0)
        dp[i] = min(d + abs(hs[i]-h) for d, h in zip(dp[from_:i], hs[from_:i]))
    print(dp[-1])
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

# coding: utf-8

N , M = map(int,input().split())
list = [ list(map(int,input().split())) for i in range(M) ]
ans = "IMPOSSIBLE"
for i in range(M):
    if list[i][0] == 1:
        for j in range(M):
            if list[j][1] == N:
                if list[i][1] == list[j][0]:
                    if list[j][1] == N:
                        ans = "POSSIBLE"
print(ans)

### FIXED CODE ###

# coding: utf-8
from sys import stdin
input = stdin.readline

N , M = map(int,input().split())
start_input = set()
goal_input = set()

for _ in range(M):
    x , y = map(int,input().split())
    if x == 1:
        start_input.add(y)
    elif y == N:
        goal_input.add(x)
    
if start_input & goal_input:
    print("POSSIBLE")
else :
    print("IMPOSSIBLE")
### BUGGY CODE ###

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

for i in range(n-1):
    cnt=0
    for j in range(i,n-1):
        if abs(a[i]-a[j])<=2:
            cnt+=1

    ans=max(ans,cnt)
print(ans)


### FIXED CODE ###

from collections import Counter
n=int(input())
a=list(map(int,input().split()))
c=Counter(a)

ans=1

for x in range(1,10**5):
    ans=max(c[x-1]+c[x]+c[x+1],ans)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    H,W = map(int,input().split())
    Gd = [list(input()) for _ in range(H)]
    INF = H*W
    direc = [[1,0],[0,1]]
    def dfs(start):
        Dis = [[INF]*W for _ in range(H)]
        Dis[start[0]][start[1]]= (Gd[start[0]][start[1]] == '#')
        q = deque([])   # スタック
        q.append(start)
        while len(q)!=0:
            h,w = q.popleft()   # スタック取りだし（先頭）
            for d in direc:
                hs, ws = h + d[0], w + d[1]
                if not (0<=hs<H and 0<=ws<W):
                    continue
                else:
                    q.append([hs,ws])
                    Dis[hs][ws] = min(Dis[hs][ws], Dis[h][w] + (Gd[hs][ws]=='#'))
        print(Dis[H-1][W-1])
    dfs([0, 0])

if __name__=='__main__':
    main()


### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    H, W = map(int,input().split())
    sth, stw = 0, 0
    glh, glw = H-1, W-1

    INF = 10000
    Gmap = [list(input()) for _ in range(H)]
    Dist = [[INF]*W for _ in range(H)]
    direc = {(1,0), (0,1)}

    if Gmap[0][0]=='#':
        Dist[0][0]=1
    else:
        Dist[0][0]=0

    for h in range(H):
        for w in range(W):
            nw = Gmap[h][w]
            for d in direc:
                hs, ws = h + d[0], w + d[1]
                if 0<=hs<H and 0<=ws<W:
                    cr = Gmap[hs][ws]
                    Dist[hs][ws] = min(Dist[hs][ws], Dist[h][w] + (cr=='#' and nw=='.'))
    print(Dist[glh][glw])

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

N,M = map(int,input().split())
AB = [tuple(map(int,input().split())) for _ in range(N-1+M)]

# 隣接リスト
A = [[] for _ in range(N)]

# 根
root = -1
R = [True]*N
for (a,b) in AB:
    R[b-1] = False
    A[a-1].append(b-1)

for i in range(N):
    if R[i]:
        root = i
        break

# 親
P = [-1]*N
P[root] = -1

Q = [root]
while Q!=[]:
    tmpQ = []
    for q in Q:
        for i in A[q]:
            # 親の更新
            P[i] = q
            # 自身をtmpQに
            tmpQ.append(i)
    Q = tmpQ

for i in range(N):
    print(P[i]+1)





### FIXED CODE ###

N,M = map(int,input().split())
AB = [tuple(map(int,input().split())) for _ in range(N-1+M)]

A = [[] for _ in range(N)]
P = [0]*N
C = [0]*N
root = -1

for (a,b) in AB:
    # a -> b
    A[a-1].append(b-1)
    C[b-1] += 1

for i in range(N):
    if C[i]==0:
        root = i
P[root] = -1

from collections import deque
que = deque((a,root) for a in A[root])
while que:
    n,par = que.popleft()
    C[n] -= 1
    if C[n]==0:
        P[n] = par
        for i in A[n]:
            que.append((i,n))

for p in P:
    print(p+1)
### BUGGY CODE ###

# 解説AC
from collections import defaultdict

N,M = map(int, input().split())
S = [int(i) for i in input().split()]
T = [int(i) for i in input().split()]

MOD = 10 ** 9 + 7

# dp[i][j]: S[:i]とT[:j]での共通部分列の個数
dp = [[0] * (M + 1) for _ in range(N + 1)]

# 初期条件
for i in range(N + 1):
    dp[i][0] = 1
for j in range(M + 1):
    dp[0][j] = 1

# 貰うDP
for i, s in enumerate(S):
    for j, t in enumerate(T):
        dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j]

        if s == t:
            dp[i + 1][j + 1] += dp[i][j]
        
        # ダブルカウントを除く
        dp[i + 1][j + 1] -= dp[i][j]

        dp[i + 1][j + 1] %= MOD

print(dp[N][M])

### FIXED CODE ###

# 解説AC
N,M = map(int, input().split())
S = [int(i) for i in input().split()]
T = [int(i) for i in input().split()]

MOD = 10 ** 9 + 7

# dp[i][j]: S[:i]とT[:j]での共通部分列の個数
dp = [[0] * (M + 1) for _ in range(N + 1)]

def main():
    # 初期条件
    for i in range(N + 1):
        dp[i][0] = 1
    for j in range(M + 1):
        dp[0][j] = 1

    # 貰うDP
    for i, s in enumerate(S):
        for j, t in enumerate(T):
            dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j]

            if s == t:
                dp[i + 1][j + 1] += dp[i][j]
            
            # ダブルカウントを除く
            dp[i + 1][j + 1] -= dp[i][j]

            dp[i + 1][j + 1] %= MOD

    print(dp[N][M])

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

def resolve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    for _ in range(k):
        dp = [0] * (n + 1)
        for index, i in enumerate(a):
            dp[max(0, index - i)] += 1
            dp[min(n, index + i + 1)] -= 1
        a[0] = dp[0]
        for i in range(1, n):
            a[i] = a[i - 1] + dp[i]
    print(*a)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

def resolve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    for _ in range(min(k,100)):
        dp = [0] * (n + 1)
        for index, i in enumerate(a):
            dp[max(0, index - i)] += 1
            dp[min(n, index + i + 1)] -= 1
        a[0] = dp[0]
        for i in range(1, n):
            a[i] = a[i - 1] + dp[i]
    print(*a)


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

R, G, B, N = map(int, input().split())
cnt = 0

for r in range(N//R+1):
	for g in range(N+1):
		if R * r + G * g == N:
			cnt += 1
		b = (N - R * r - G * g) / B
		if b.is_integer() and b > 0:
			cnt += 1
print(cnt)


### FIXED CODE ###

R, G, B, N = map(int, input().split())
cnt = 0

for r in range(N//R+1):
	for g in range((N-R*r)//G+1):
		if (N - R * r - G * g) % B == 0:
			cnt += 1
print(cnt)