Harryxun/stf_run huggingface dataset:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
def factor(n, m=None):
    # mを与えると、高々その素因数まで見て、残りは分解せずにそのまま出力する
    arr = defaultdict(int)
    temp = n
    M = int(-(-n**0.5//1))+1
    if m is not None:
        M = min(m+1, M)
    for i in range(2, M):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i] = cnt

    if temp!=1:
        arr[temp] = 1

    if not arr:
        arr[n] = 1

    return arr

n = int(input())
a = [None]*n
m = [[0]*19 for _ in range(19)]
ab = [None]*n
for i in range(n):
    s = input()
    if "." in s:
        ind = s.index(".")
        vv = len(s) - s.index(".") - 1
        v = int(s[:ind])*10**(vv) + int(s[(ind+1):])
        v *= 10**(9-vv)
    else:
        v = int(s)*10**9
    d = factor(v, 5)
    a,b = max(0, 18-d[2]), max(0, 18-d[5])
    m[a][b] += 1
    ab[i] = (d[2],d[5])
def cumsum2(v):
    # v: h*wの2次元リスト
    h,w = len(v), len(v[0])
    v.insert(0, [0]*w)
    for l in v:
        l.insert(0, 0)
    for i in range(1,h+1):
        for j in range(1,w+1):
            v[i][j] = v[i-1][j] + v[i][j-1] - v[i-1][j-1] + v[i][j]
    return v
m = cumsum2(m)
ans = 0
for a,b in ab:
    ans += m[a+1][b+1]
    if a>=9 and b>=9:
        ans -= 1
print(ans//2)

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
def factor(n, m=None):
    # mを与えると、高々その素因数まで見て、残りは分解せずにそのまま出力する
    arr = defaultdict(int)
    temp = n
#     M = int(-(-n**0.5//1))+1
#     if m is not None:
#         M = min(m+1, M)
    M = 6
    for i in range(2, M):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i] = cnt

    return arr

n = int(input())
a = [None]*n
m = [[0]*19 for _ in range(19)]
ab = [None]*n
for i in range(n):
    s = input()
    if "." in s:
        ind = s.index(".")
        vv = len(s) - s.index(".") - 1
        v = int(s[:ind])*10**(vv) + int(s[(ind+1):])
        v *= 10**(9-vv)
    else:
        v = int(s)*10**9
    d = factor(v, 5)
    d.setdefault(2,0)
    d.setdefault(5,0)
    a,b = max(0, 18-d[2]), max(0, 18-d[5])
    m[a][b] += 1
    ab[i] = (d[2],d[5])
def cumsum2(v):
    # v: h*wの2次元リスト
    h,w = len(v), len(v[0])
    v.insert(0, [0]*w)
    for l in v:
        l.insert(0, 0)
    for i in range(1,h+1):
        for j in range(1,w+1):
            v[i][j] = v[i-1][j] + v[i][j-1] - v[i-1][j-1] + v[i][j]
    return v
m = cumsum2(m)
ans = 0
for a,b in ab:
#     print(a,b)
    ans += m[min(19,a+1)][min(19,b+1)]
    if a>=9 and b>=9:
        ans -= 1
print(ans//2)
#入力した整数が５、７、５であるならばTrueを返す
# int,int,int -> True 

def check7(x,y,z):
    if x == 7:
        if y == z and y == 5 :
            print("YES")
        else:
            print("NO")
    elif y == 7:
        if x == z and x == 5:
            print("YES")
        else:
          print("NO")
    elif z == 7:
        if x == y and x == 5:
          print("YES")
        else:
          print("NO")
    else:
      print("NO")

if __name__ == "__main__":
    check7()


### FIXED CODE ###

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

input_list = input().split()

cnt7 = 0
cnt5 = 0

for n in input_list:
    if int(n) == 7:
        cnt7 += 1
    elif int(n) == 5:
        cnt5 += 1
    else:
        continue
if cnt7 == 1 and cnt5 == 2:
    print("YES")
else:
    print("NO")
N = int(input())
X = int(input())
T = int(input())

a = N // X
min_T = T*a

print(min_T)

### FIXED CODE ###

N, X, T = map(int, input().split())

a = N // X
if N%X == 0:
	min_T=T*a
else:
	min_T = T*(a+1)

print(min_T)
import collections
import numpy as np

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

di = collections.Counter(li)
#print(di)

arr = np.array(list(di.values()))
arrr = arr - 1
c = np.dot(arr, arrr) // 2
#print(c)

for v in li:
    x = int(di[v])
    if x == 1:
        print(c)
    else:
        print(c-(x-1))
    
#(n * n-1)-(n-1 * n-2) / 2

### FIXED CODE ###

import collections
import numpy as np

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

di = collections.Counter(li)
#print(di)

arr = np.array(list(di.values()))
arrr = arr - 1
c = np.dot(arr, arrr) // 2
#print(c)

#(n * n-1)-(n-1 * n-2) / 2 = n-1

for v in li:
    x = int(di[v])
    if x == 1:
        print(c)
    else:
        print(c-(x-1))
n = int(input())
a = list(map(int , input().split()))
pos = sorted([i for i in a if i >= 0], reverse=True)
neg = sorted([i for i in a if i < 0], reverse=True)

ans = []
if len(neg) == 0 and len(pos) == 2:
    print(pos[0] - pos[1])
    print(pos[0], pos[1])
    exit()
elif len(pos) == 0:
    tmp = neg[0]
    neg = neg[1:]
    neg.append(tmp)
elif len(neg) == 0:
    neg.append(pos.pop())

tmp = neg.pop()
while len(pos) > 1:
    a = pos.pop()
    ans.append([tmp, a])
    tmp -= a
neg.append(tmp)

tmp = pos[0]
for i in neg:
    ans.append([tmp, i])
    tmp -= i

print(tmp)
[print(*i) for i in ans]


### FIXED CODE ###

n = int(input())
a = list(map(int , input().split()))
pos = sorted([i for i in a if i >= 0], reverse=True)
neg = sorted([i for i in a if i < 0], reverse=True)

ans = []
if len(neg) == 0 and len(pos) == 2:
    print(pos[0] - pos[1])
    print(pos[0], pos[1])
    exit()
elif len(pos) == 0:
    tmp = neg[0]
    for i in range(1,len(neg)):
        ans.append([tmp, neg[i]])
        tmp -= neg[i]
    print(tmp)
    [print(*i) for i in ans]
    exit()
elif len(neg) == 0:
    neg.append(pos.pop())

tmp = neg.pop()
while len(pos) > 1:
    a = pos.pop()
    ans.append([tmp, a])
    tmp -= a
neg.append(tmp)

tmp = pos[0]
for i in neg:
    ans.append([tmp, i])
    tmp -= i

print(tmp)
[print(*i) for i in ans]
import sys
input = sys.stdin.readline
from collections import Counter

MAX = 10**6+100
MOD = 10**9+7
fact = [0]*MAX #fact[i]: i!
inv = [0]*MAX #inv[i]: iの逆元
finv = [0]*MAX #finv[i]: i!の逆元
fact[0] = 1
fact[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
    
for i in range(2, MAX):
    fact[i] = fact[i-1]*i%MOD
    inv[i] = MOD-inv[MOD%i]*(MOD//i)%MOD
    finv[i] = finv[i-1]*inv[i]%MOD

def C(n, r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fact[n]*(finv[r]*finv[n-r]%MOD)%MOD

K = int(input())
S = input()[:-1]
N = len(S)
ans = 0

for i in range(K+1):
    ans += C(N+K-i-1, N-1)*pow(26, i, MOD)*pow(25, K-i, MOD)
    ans %= MOD
    
print(ans)

### FIXED CODE ###

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

MAX = 2*10**6+100
MOD = 10**9+7
fact = [0]*MAX #fact[i]: i!
inv = [0]*MAX #inv[i]: iの逆元
finv = [0]*MAX #finv[i]: i!の逆元
fact[0] = 1
fact[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
    
for i in range(2, MAX):
    fact[i] = fact[i-1]*i%MOD
    inv[i] = MOD-inv[MOD%i]*(MOD//i)%MOD
    finv[i] = finv[i-1]*inv[i]%MOD

def C(n, r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fact[n]*(finv[r]*finv[n-r]%MOD)%MOD

K = int(input())
S = input()[:-1]
N = len(S)
ans = 0

for i in range(K+1):
    ans += C(N+K-i-1, N-1)*pow(26, i, MOD)*pow(25, K-i, MOD)
    ans %= MOD
    
print(ans)
#!/usr/bin/env python3
import sys
INF = float("inf")


def GCD(a, b):
    if a == 0:
        return b
    else:
        return GCD(b % a, a)


def LCM(a, b):
    return a*b//GCD(a, b)


def solve(N: int, M: int, a: "List[int]"):

    k = 0
    b = a[0]
    while not b & 1:
        k += 1
        b >>= 1
    b = [aa >> k for aa in a]

    gcd = b[0]
    lcm = b[0]
    for bb in b:
        gcd = GCD(gcd, bb)
        lcm = LCM(lcm, bb)

    if lcm % 2 == 0:
        print(0)
        return
    else:
        print(int((M-lcm)/(2*lcm))+1)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import math
from functools import reduce
import operator
INF = float("inf")


def GCD(a, b):
    while b:
        a, b = b, a % b
    return a


def LCM(a, b):
    return a*b//GCD(a, b)


def solve(N: int, M: int, a: "List[int]"):

    # 各aを2で割れる回数(の２べき)
    K = set()
    for i, av in enumerate(a):
        K.add(av & -av)
    if len(K) != 1:
        print(0)
        return

    lcm = a[0]//2
    for av in a:
        lcm = LCM(lcm, av//2)

    ans = int(M/lcm)
    if ans > 0 and ans % 2 == 0:
        ans -= 1
    ans = (ans+1)//2

    print(ans)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, a)


if __name__ == '__main__':
    main()
a,b=map(int,input().split())
if ((a*b)%2) == 0:
  print('even')
else:
  print('Obb’)


### FIXED CODE ###

a,b=map(int,input().split())
if ((a*b)%2) == 0:
  print('Even')
else:
  print('Odd')
import math

N = int(input())
As = [int(elm) for elm in input().split(" ")] 


def divisor(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            ass.append(n//i)
    return ass

if N >= 3:
    gs = []
    for i in range(0, (N//2)*2 , 2):
        g = math.gcd(As[i], As[i+1])
        gs.append(g)
    if N % 2 == 1:
        gs.append(As[N-1])

    while len(gs) != 2:
        #print(gs)
        new_gs = []
        N1 = len(gs)
        #print("len",len(gs), (N1//2)*2)
        for i in range(0, (N1//2)*2, 2):
            g = math.gcd(gs[i], gs[i+1])
            new_gs.append(g)
        if N1 % 2 == 1:
            new_gs.append(gs[-1])
        gs = new_gs

    g1, g2 = gs
    d1 = divisor(g1) 
    d2 = divisor(g2) 
    ds = sorted(d1 + d2, reverse=True)

    #print(gs)
    #print(ds)
    for d in ds:
        count = sum([int(A % d == 0) for A in As])
        if count >= N-1:
            out = d
            break

else:
    out = max(As)

print(out)

### FIXED CODE ###

#import math
from fractions import gcd

N = int(input())
As = [int(elm) for elm in input().split(" ")] 


def divisor(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            ass.append(n//i)
    return ass

if N >= 3:
    gs = []
    for i in range(0, (N//2)*2 , 2):
        g = gcd(As[i], As[i+1])
        gs.append(g)
    if N % 2 == 1:
        gs.append(As[N-1])

    while len(gs) != 2:
        #print(gs)
        new_gs = []
        N1 = len(gs)
        #print("len",len(gs), (N1//2)*2)
        for i in range(0, (N1//2)*2, 2):
            g = gcd(gs[i], gs[i+1])
            new_gs.append(g)
        if N1 % 2 == 1:
            new_gs.append(gs[-1])
        gs = new_gs

    g1, g2 = gs
    d1 = divisor(g1) 
    d2 = divisor(g2) 
    ds = sorted(d1 + d2, reverse=True)

    #print(gs)
    #print(ds)
    for d in ds:
        count = sum([int(A % d == 0) for A in As])
        if count >= N-1:
            out = d
            break

else:
    out = max(As)

print(out)
r = double(input())
import math
d = r * r * math.pi
l = 2 * r * math.pi
print("%f %f" %(d,l))

### FIXED CODE ###

r = float(input())
import math
d = r * r * math.pi
l = 2 * r * math.pi
print("%f %f" %(d,l))
import math
s = input()
k = int(input())

i = 0
while i < len(s):
    if int(math.log(s[i])) * (500 * 10 **12) >= math.log(k):
#         print(i, s[i], int(s[i]) ** (500 * 10 *12))
        break
    i += 1
print(s[i])

### FIXED CODE ###

s = input()
k = int(input())
if len(s) == 1 or k == 1:
    print(s[0])
else:
    i = 0
    while i < k - 1 and i < len(s):
        if s[i] != '1':
            break
        i += 1
    print(s[i])
N,K = map(int, input().split(" "))
flag = [1 for i in range(N)]
for i in range(K):
  input()
  a = map(int, input().split(" "))
  for j in a:
    flag[a - 1] = 0
print(sum(flag))

### FIXED CODE ###

N, K = map(int, input().split(" "))
flag = [1 for i in range(N)]
for i in range(K):
  input()
  for j in map(int,input().split(" ")):
    flag[j-1] = 0
print(sum(flag))
from bisect import bisect_left

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

a.sort()
z = a.count(0)
mc = bisect_left(a, 0)
pc = n - z - mc

if k <= mc * pc:
    d = a[:mc]
    u = a[mc + z:]
    H = 0
    L = d[0] * u[-1]
    D = len(d)
    while H - L > 1:
        M = (H + L) // 2
        count = 0
        P = 0
        for x in u:
            while P < D:
                if d[P] > M // x:
                    break
                P += 1
            count += P
        if count == k:
            break
        elif count < k:
            L = M
        else:
            H = M
    if count == k:
        print(M)
    else:
        print(M+1)
    exit()
elif k <= mc * pc + z * (n - z) + z * (z - 1) // 2:
    print(0)
    exit()

d = list(map(lambda x: -x, reversed(a[:mc])))
u = a[mc + z:]
D = len(d)
U = len(u)

k -= mc * pc + z * (n - z) + z * (z - 1) // 2
#print(k, mc * pc, z * (n-z), z * (z-1) // 2)
#print(U, D, mc, pc, z)
#print(d)
# #print(u)

L = 0
H = max(d[-1] * d[-1], u[-1] * u[-1])

while H - L > 1:
    M = (H + L) // 2
    count = 0
    P = 0
    for i in range(U-1, -1, -1):
        x = u[i]
        while P < U:
            if u[P] * x > M:
                break
            P += 1
        count += P
    for i in range(U):
        if u[i] ** 2 <= M:
            count -= 1
        else:
            break
    P = 0
    for i in range(D-1, -1, -1):
        x = d[i]
        while P < D:
            #print(x, P)
            if d[P] * x > M:
                break
            P += 1
        count += P
    for i in range(D):
        if d[i] ** 2 <= M:
            count -= 1
        else:
            break
    #print(M, count)
    if count < k:
        L = M
    else:
        H = M
if count == k:
    print(M)
else:
    print(M+1)


### FIXED CODE ###

import numpy as np

n, k = map(int, input().split())
a = np.array(input().split(), np.int64)

a = np.sort(a)

u = a[a > 0]
d = a[a < 0]
z = len(a[a == 0])

if len(u) * len(d) < k <= len(u) * len(d) + z * (n-z) + z * (z-1) // 2:
    print(0)
    exit()

L = - 10 ** 18
H = 10 ** 18

while H - L > 1:
    M = (H + L) // 2
    count = 0
    if M > 0:
        count += z * n
    count += np.searchsorted(a, M // u, side='right').sum()
    count += (n - np.searchsorted(a, (- M - 1) // (- d), side='right')).sum()
    count -= np.count_nonzero(a * a <= M)
    count //= 2
    #print(count)
    if count >= k:
        H = M
    else:
        L = M

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

R = [A[0]%M]


for i in range(1,N):
  R.append((R[-1]+A[i])%M)

k = set(R)
dic = {i:0 for i in k}
for item in R:
  dic[item]+=1

ans = (dic[0]*(dic[0]+1))/2

#for i in k:
 # if i !=0 :
  #  ans += (dic[i]*(dic[i]-1))/2
    

    
print(int(ans))


### FIXED CODE ###

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

R = [A[0]%M]


for i in range(1,N):
  R.append((R[-1]+A[i])%M)



import collections
c = collections.Counter(R)


ans = 0
for key in c:
  if key == 0:
    ans += (c[key]*(c[key]+1))/2
  else:
    ans += (c[key]*(c[key]-1))/2
  



print(int(ans))
x = int(input())
s = input()
i = int(input())

si = s[i]

s = s.replace('si', '*')
print(s)

### FIXED CODE ###

_  = input()
s = input()
index = int(input())-1

result = ''

t = s[index]

for i in s:
  if i != t:
    result += '*'
  else:
    result += i
print(result)
def min_cost(i, total):
    if i < 1:
        return 0

    total += min_cost(i - 1, abs(h[i] - h[i - 1]))
    total += min_cost(i - 2, abs(h[i] - h[i - 2]))
    return total


def chmin(a, b):
    if a > b:
        return b
    else:
        return a

      
N = int(input())
H = list(map(int, input().split(' ')))

dp = [10000] * 10000
dp[0] = 0

for i in range(1, N):
    dp[i] = chmin(dp[i], dp[i - 1] + abs(H[i] - H[i - 1]))
    if i > 1:
        dp[i] = chmin(dp[i], dp[i - 2] + abs(H[i] - H[i - 2]))

print(dp[N - 1])


### FIXED CODE ###

N = int(input())
H = list(map(int, input().split(' ')))

dp = [100000000] * N
dp[0] = 0
dp[1] = abs(H[0] - H[1])

for i in range(2, N):
    dp[i] = min(dp[i - 1] + abs(H[i] - H[i - 1]), dp[i - 2] + abs(H[i] - H[i - 2]))

print(dp[N - 1])
n,a,b = map(int, input().split())

if n == 1 and a == b:
  print(1)
elif n == 1:
  print(0)
elif a > b:
  print(0)
elif n == 2:
  print(1)
elif n > 2:
  print( (B-A+1) * (n-2) )

### FIXED CODE ###

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

if n == 1 and a == b:
  print(1)
elif n == 1:
  print(0)
elif a > b:
  print(0)
elif n == 2:
  print(1)	
elif n > 2:
  print( b * (n-2) - a * (n-2) + 1) 
else:
  print(0)
H,W = map(int,raw_input().split())
 
s = []
for i in range(H):
	s.append(raw_input())
 
flag=True
for i in range(H):
	for j in range(W):
		if s[i][j]=='#':
			local_flag=False
			if i+1<H:
				if s[i+1][j]=='#':
					local_flag=True
			if j+1<W:
				if s[i][j+1]=='#':
					local_flag=True
			if i-1>=0:
				if s[i-1][j]=='#':
					local_flag=True
			if j-1>=0:
				if s[i][j-1]=='#':
					local_flag=True
			if local_flag=False:
				flag=False
if flag:
	print 'Yes'
else:
	print 'No'

### FIXED CODE ###

H,W = map(int,raw_input().split())
 
s = []
for i in range(H):
	s.append(raw_input())
 
flag=True
for i in range(H):
	for j in range(W):
		if s[i][j]=='#':
			local_flag=False
			if i+1<H:
				if s[i+1][j]=='#':
					local_flag=True
			if j+1<W:
				if s[i][j+1]=='#':
					local_flag=True
			if i-1>=0:
				if s[i-1][j]=='#':
					local_flag=True
			if j-1>=0:
				if s[i][j-1]=='#':
					local_flag=True
			if local_flag==False:
				flag=False
if flag:
	print 'Yes'
else:
	print 'No'
import sys, math
from collections import deque

readline = sys.stdin.readline

S = int(readline())

M = 10 ** 9
rS = math.ceil(math.sqrt(S))

while True:
    rem = rS ** 2 - S


    if rem <= M:
        b = rem
        break
    else:
        b = 0
        a = rem // M + 1
        c = math.floor(rem ** 0.5)
        while a < c and a < M:
            if rem % a == 0:
                b = a
                break
            a += 1
        if b != 0:
            break
    
    if rS >= M:
        rS = M - 1000
    else:
        rS += 1

if rS > M or b > M:
    assert False

print('0 0 {} {} {} {}'.format(rS, b, rem // b, rS))

### FIXED CODE ###

import sys, math
from collections import deque

readline = sys.stdin.readline

S = int(readline())

M = 10 ** 9
rS = math.ceil(math.sqrt(S))

while True:
    rem = rS ** 2 - S

    if rem == 0:
        print('0 0 {} {} {} {}'.format(rS, 0, 0, rS))
        exit(0)

    if rem <= M:
        b = rem
        break
    else:
        b = 0
        a = rem // M + 1
        c = math.floor(rem ** 0.5)
        while a < c and a < M:
            if rem % a == 0:
                b = a
                break
            a += 1
        if b != 0:
            break
    
    if rS >= M:
        rS = M - 1000
    else:
        rS += 1


print('0 0 {} {} {} {}'.format(rS, b, rem // b, rS))
import sys
import math

for line in sys.stdin:
    a,b = map(int, line.split())
    gc = math.gcd(a,b)
    print("{} {}".format(gc, a*b//gc))

### FIXED CODE ###

import sys

def gcd(a,b):
    if a%b == 0:
        return b
    else:
        return gcd(b, a%b)

for line in sys.stdin:
    a,b = map(int, line.split())
    if a<b:
        tem = a
        a = b
        b = tem
    gc = gcd(a,b)
    print(gc, a*b//gc)
N,C = map(int,input().split())
lists = [list(map(lambda x:int(x),input().split())) for i in range(N)]
cal = 0
cals = []
if lists[0][0] < lists[0][1]:
    cal = cal - lists[0][0] + lists[0][1]
    cals.append(cal)
for i in range(1,N):
    cal = cal - (lists[i][0] - lists[i-1][0]) + lists[i][1]
    cals.append(cal)
print(max(cals))

### FIXED CODE ###

lists = input()
sum = 700+lists.count('o')*100
print(sum)
import sys
input = sys.stdin.readline

n,m = map(int, input().split())
G = [[] for i in range(n)]
used = [0]*n
for i in range(n+m-1):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    G[a].append(b)
    used[b] = 1
root = used.index(0)

dist = [0]*n
def rec(cur, depth):
    dist[cur] = max(dist[cur], depth)
    for to in G[cur]:
        rec(to, depth+1)

rec(root, 0)

par = [0]*n
for from_ in range(n):
    for to in G[from_]:
        if dist[from_] + 1 == dist[to]:
            par[to] = from_+1
print(*par, sep="\n")


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

n,m = map(int, input().split())
G = [[] for i in range(n)]
rG = [[] for i in range(n)]
used = [0]*n
for i in range(n+m-1):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    G[a].append(b)
    rG[b].append(a)
    used[b] = 1
root = used.index(0)

par = [-1]*n
depth = [-1]*n

def rec(cur):
    if depth[cur] != -1:
        return depth[cur]
    m = 0
    i = -1
    for p in rG[cur]:
        if rec(p)+1 > m:
            i = p
            m = rec(p)+1
    par[cur] = i
    depth[cur] = m
    return m

for i in range(n):
    rec(i)
par = [i+1 for i in par]
print(*par, sep="\n")
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
​
n,q=map(int,input().split())
STX=[tuple(map(int,input().split())) for i in range(n)]
D=[int(input()) for i in range(q)]
event=[]
for si,ti,xi in STX:
  event.append((si-xi,0,xi))
  event.append((ti-xi,-1,xi))
for di in D:
  event.append((di,1,di))
event.sort()
hq=[]; S=set()
for time, query, number in event:
  if query == 0:
    heapq.heappush(hq,number)
    S.add(number)
  elif query == -1:
    S.remove(number)
  else:
    while hq and hq[0] not in S:
      heapq.heappop(hq)
    if not hq:
      print(-1)
    else:
      print(hq[0])


### FIXED CODE ###

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect, heapq
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,q=map(int,input().split())
STX=[tuple(map(int,input().split())) for i in range(n)]
D=[int(input()) for i in range(q)]
event=[]
for si,ti,xi in STX:
  event.append((si-xi,0,xi))
  event.append((ti-xi,-1,xi))
for di in D:
  event.append((di,1,di))
event.sort()
hq=[]; S=set()
for time, query, number in event:
  if query == 0:
    heapq.heappush(hq,number)
    S.add(number)
  elif query == -1:
    S.remove(number)
  else:
    while hq and hq[0] not in S:
      heapq.heappop(hq)
    if not hq:
      print(-1)
    else:
      print(hq[0])
import numpy as np

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

A = np.empty((0, m), int)
b = np.empty((0, 1), int)

for i in range(n):
    A = np.append(A, np.array([list(map(int, input().split()))]), axis=0)

for i in range(m):
    b = np.append(b, np.array([list(map(int, input().split()))]), axis=0)

c = np.dot(A, b)

for i in range(n):
    print(int(c[i]))

### FIXED CODE ###

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

A = [list(map(int, input().split())) for i in range(n)]
bt = [int(input()) for i in range(m)]

for i in range(n):
    print(sum([x * y for (x, y) in zip(A[i], bt)]))