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

import sys

input = sys.stdin.readline

n, k = [int(x) for x in input().split()]
A = [int(a) for a in input().split()]

A.sort()

# 積がx未満となる組み合わせの数を求める
def n_comb_lt(x):
    n_comb = 0
    for i in range(n - 1): # A[0], A[1], ..., A[n-2]について
        # i < jであるjのうち、A[i] * A[j] < xとなるjの数を求める
        if A[i] > 0:
            if A[i] * A[i + 1] >= x:
                n_partner = 0
            elif A[i] * A[n - 1] < x:
                n_partner = n - 1 - i
            else:
                ok = i + 1
                ng = n - 1

                # ok >= 1, ng <= 200000 - 1
                # log2(200000) < 18
                # for _ in range(18):
                while ng - ok > 1:
                    mid = (ng + ok) // 2
                    if A[i] * A[mid] < x:
                        ok = mid
                    else:
                        ng = mid
                n_partner = ok - i
        else:
            if A[i] * A[i + 1] < x:
                n_partner = n - 1 - i
            elif A[i] * A[n - 1] >= x:
                n_partner = 0
            else:
                ng = i + 1
                ok = n - 1
                # ok >= 1, ng <= 200000 - 1
                # log2(200000) < 18
                # for _ in range(18):
                while ok - ng > 1:
                    mid = (ng + ok) // 2
                    if A[i] * A[mid] < x:
                        ok = mid
                    else:
                        ng = mid
                n_partner = n - 1 - ng
        n_comb += n_partner

    return n_comb


ok = -10 ** 18 - 1
ng = 10 ** 18 + 1

# for _ in range(62):
while ng - ok > 1:
    mid = (ng + ok) // 2
    if n_comb_lt(mid) < k:
        ok = mid
    else:
        ng = mid

print(ok)


### FIXED CODE ###

import numpy as np
import sys

input = sys.stdin.readline

n, k = [int(x) for x in input().split()]
A = np.array([int(a) for a in input().split()], dtype="int64")

A = np.sort(A)

A_pos = A[A > 0]
A_neg = A[A < 0]
A_zero = A[A == 0]

# 積がc以下となる組み合わせの数を求める
def n_comb_lt(c):
    n_comb = 0
    # A[i] > 0であるA[i]について
    target = c // A_pos  # target以下の値がA[i]の相方
    n_comb += np.searchsorted(A, target, side="right").sum()

    # A[i] == 0であるA[i]について
    n_comb += n * len(A_zero) if c >= 0 else 0

    # A[i] < 0であるA[i]について
    target = -(-c // A_neg)
    n_comb += (n - np.searchsorted(A, target, side="left")).sum()

    # 組み合わせのうち、A[i]*A[i]となっているものを引いて、2で割る
    n_comb -= A[A * A <= c].size
    n_comb //= 2

    return n_comb

ok = -10 ** 18 - 1
ng = 10 ** 18 + 1

# k番目の積は、積がm未満となる組み合わせがk個未満となる最大のm
# ←→積が(m-1)以下となる組み合わせがk個未満となる最大のm
while ng - ok > 1:
    mid = (ng + ok) // 2
    if n_comb_lt(mid - 1) < k:
        ok = mid
    else:
        ng = mid

print(ok)
### BUGGY CODE ###

if __name__ == "__main__":
  h,w = list(map(int,input().split()))
  a = [["*"*w] for i in range(h)]
  reached = [[-1 for i in range(w)] for j in range(h)]
  for i in range(h): a[i] = input()
  
  queue = []
  for i in range(h):
    for j in range(w):
      if a[i][j] == "#":
        queue.append([i,j])
        reached[i][j] = 0
  
  res = 0
  while len(queue) > 0:
    k = queue[0][0]
    l = queue[0][1]
    p = reached[k][l] + 1
    if 0 <= k+1 < h and 0 <= l < w:
      if reached[k+1][l] == -1:
        reached[k+1][l] = p
        res = p
        queue.append([k+1, l])
    if 0 <= k < h and 0 <= l+1 < w:
      if reached[k][l+1] == -1:
        reached[k][l+1] = p
        res = p
        queue.append([k, l+1])
    if 0 <= k-1 < h and 0 <= l < w:
      if reached[k-1][l] == -1:
        reached[k-1][l] = p
        res = p
        queue.append([k-1, l])
    if 0 <= k < h and 0 <= l-1 < w:
      if reached[k][l-1] == -1:
        reached[k][l-1] = p
        res = p
        queue.append([k, l-1])
    queue.pop(0)
  print(res)

### FIXED CODE ###

def main():
  h,w = map(int,input().split())

  q = []
  reached = [[True]*(w+2)]
  for i in range(1, h+1):
    reached.append([True] + [s == '#' for s in list(input())] + [True])
    for j in range(1,w+1):
      if reached[i][j]: q.append((i,j))
  reached.append([True]*(w+2))

  res = 0
  for i in range(100000000):
    qq = []
    for k,l in q:
      if not reached[k+1][l]:
        qq.append((k+1, l))
        reached[k+1][l] = True
      if not reached[k][l+1]:
        qq.append((k, l+1))
        reached[k][l+1] = True
      if not reached[k-1][l]:
        qq.append((k-1, l))
        reached[k-1][l] = True
      if not reached[k][l-1]:
        qq.append((k, l-1))
        reached[k][l-1] = True
    if len(qq) == 0:
      break
    else:
      pass

    q = qq
    res += 1

  print(res)
  return 0

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

# coding: utf-8
import numpy as np
from functools import lru_cache
import time

def main(): 
    if True:
        N,K = list(map(int,input().split()))
        S = np.asarray(list(map(int,list(str(input())))))
    else:
        pass
    SN = np.asarray([])
    first = S[0]
    tmpnum = first
    if first == 0:
        SN = np.append(SN,0)
    SN = np.append(SN,0)

    count = 0
    for n in range(N)[1:]:
        if S[n] == tmpnum:
            count += 1
        else:
            count += 1
            SN = np.append(SN,count)
            #count = 0
            tmpnum = S[n]
    else:
        count += 1
        SN = np.append(SN,count)
        if tmpnum == 0:
            SN = np.append(SN,count)

    max = 0
    flag = 0
    for n in range(SN.size)[2*K+1::2]:
        if max < SN[n] - SN[n-2*K-1]:
            max = SN[n] - SN[n-2*K-1]
        flag = 1
    if flag == 0:
        print(int(SN[-1]-SN[0]))
    else:
        print(int(max))

if __name__ =='__main__':
    main()

### FIXED CODE ###

# coding: utf-8
import numpy as np
from functools import lru_cache
import time

def main(): 
    if True:
        N,K = list(map(int,input().split()))
        S = np.asarray(list(map(int,list(str(input())))))
    else:
        N,K = [10**5,1]
        T = np.asarray(range(N))
        S = np.zeros(N)
        S[T%2==0] = 1

    SN = np.zeros(10**5+2)
    first = S[0]
    tmpnum = first
    k = 0
    if first == 0:
        k += 1
    k += 1

    count = 0
    for n in range(N)[1:]:
        if S[n] == tmpnum:
            count += 1
        else:
            count += 1
            SN[k] = count
            k += 1
            tmpnum = S[n]
    else:
        count += 1
        SN[k] = count
        if tmpnum == 0:
            SN[k+1] = count

    max = 0
    flag = 0
    for n in range(SN.size)[2*K+1::2]:
        if SN[n] == 0: break
        if max < SN[n] - SN[n-2*K-1]:
            max = SN[n] - SN[n-2*K-1]
        flag = 1
    
    if flag == 0:
        print(int(np.max(SN)))
    else:
        print(int(max))

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

N = int(input())
l = []
k = 0
for i in range(N):
    S = input()
    l.append(S)
for i in range(N):
    while True:
        try:
            a = l.index(l[i])
        except ValueError:
            k += 1
            break
print(k) 

### FIXED CODE ###

N = int(input())
l = []
k = 1
for i in range(N):
    S = input()
    l.append(S)
l.sort()
for i in range(N-1):
    if l[i] != l[i+1]:
        k += 1
    else:
        pass
print(k)
### BUGGY CODE ###

from itertools import combinations
n,k = map(int,input().split())
list1 = list(map(int,input().split()))
list2  = []
for i in combinations(list1,k) :
    list2.append(sum(i))
print(min(list2))

### FIXED CODE ###

from itertools import combinations
n,k = map(int,input().split())
list1 = list(map(int,input().split()))
print(sum(sorted(list1)[:k]))
### BUGGY CODE ###

import sys

input = sys.stdin.readline
N, M = map(int, input().split())


def merge(s1, s2):
    ls1 = len(s1)
    ls2 = len(s2)
    i1 = 0
    i2 = 0
    ans = []
    while (i1 < ls1 and i2 < ls2):
        if s1[i1] < s2[i2]:
            ans.append(s1[i1])
            i1 += 1
        else:
            ans.append(s2[i2])
            i2 += 1
    for i in range(i1, ls1):
        ans.append(s1[i])
    for i in range(i2, ls2):
        ans.append(s2[i])
    return ans


import bisect

ABs = [[] for _ in range(M + 1)]
for i in range(N):
    A, B = map(int, input().split())
    if A <= M:
        bisect.insort_left(ABs[A], B)

As = 0
for i in range(M + 1):
    if i > 0:
        ABs[0] = merge(ABs[0], ABs[i])
    if len(ABs[0]) > 0:
        As += ABs[0].pop()
print(As)

### FIXED CODE ###

import sys

input = sys.stdin.readline
N, M = map(int, input().split())

import bisect

ABs = [[] for _ in range(M + 1)]
for i in range(N):
    A, B = map(int, input().split())
    if A <= M:
        ABs[A].append(B)
ABs[0].sort()

As = 0
for i in range(M + 1):
    if i > 0:
        for b in ABs[i]:
            bisect.insort_left(ABs[0], b)
    if len(ABs[0]) > 0:
        As += ABs[0].pop()
print(As)
### BUGGY CODE ###

from math import factorial as fac
N,M = map( int, input().split() )
break_list = []
for i in range(M):
    break_list.append( int( input() ) )
break_list.append( N + 1 )
start = 0
ans = 1
for i in break_list:
    sum_c = 0
    end = i - 1
    if start > end:
        i = -1
        break
    step_1 = end - start
    step_2 = int( ( end - start ) / 2 )
    for j in range(step_2 + 1):
        k = step_1 - 2 * j
        sum_c += fac(k + j) // ( fac(j) * fac(k) ) 
    ans *= sum_c
    start = i + 1
    
if i > -1:
    print( ans % 1000000007 )
else:
    print(0)

### FIXED CODE ###

N,M = map( int, input().split() )
break_list = []
for i in range(M):
    break_list.append( int( input() ) )

break_list.append(-10)
t = 0
fib = [0] * (N + 1)
if break_list[0] == 1:
    fib[1] = 0
    t += 1
else:
    fib[1] = 1
    
fib[0] = 1

for i in range(N - 1):
    if ( i + 2 ) ==  break_list[t]:
        fib[i + 2] = 0
        t += 1
    else:
        fib[i + 2] = fib[i] + fib[i + 1]
 
if N == 1:
    print( fib[1] )
else:
    print( fib[i+2] %  1000000007 )
### BUGGY CODE ###

x, y, z, k = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

A.sort(reverse=1)
B.sort(reverse=1)
C.sort(reverse=1)

D = []

for i in range(min(k, x)):
    for j in range(min(k, y)):
        D.append(A[i] + B[j])

D.sort(reverse=1)
E = []

for i in range(min(k, len(D))):
    for j in range(min(k, z)):
        E.append(D[i] + C[j])

E.sort(reverse=1)

for i in range(k):
    print(E[i])

### FIXED CODE ###

x, y, z, k = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

A.sort(reverse=1)
B.sort(reverse=1)
C.sort(reverse=1)

D = [0] * (min(k, x) * min(k, y))

for i in range(min(k, x)):
    for j in range(min(k, y)):
        D.append(A[i] + B[j])

D.sort(reverse=1)
E = [0] * (min(k, len(D)) * min(k, z))

for i in range(min(k, len(D))):
    for j in range(min(k, z)):
        E.append(D[i] + C[j])

E.sort(reverse=1)

for i in range(k):
    print(E[i])
### BUGGY CODE ###

N=int(input())
S=input()

pin={}

l=len(S)
for i in range(10):
  for j in range(10):
    for k in range(10):
     pin['{}{}{}'.format(i,j,k)]='{}{}{}'.format(i,j,k)

ans=0
for key in pin:
  s=pin[key]
  flag=0
  start=0
  for i in range(N) :
    if S[i]==s[0]:
      start=i+1
      flag+=1
      break
  if flag==1:
    for j in range(start,N):
      if S[j]==s[1]:
        start=j+1
        flag+=1
        break
  if flag==2:
    for k in range(start,N):
      if S[k]==s[2]:
        flag+=1
        break
  if flag==3:
    ans+=1

print(ans)

### FIXED CODE ###

N=int(input())
S=input()
S=list(map(int,S))
ans=0
for s in range(1000):
      A=s//100
      B=(s-A*100)//10
      C=s-A*100-B*10
      isOne=0
      isTen=0
      isHundred=0
      for i in range(N) :
        if isOne==0:
          if S[i]==A: 
            isOne=1
        elif isTen==0:
          if S[i]==B: 
            isTen=1
        elif isHundred==0:
          if S[i]==C:
            isHundred=1
            ans+=1
        else:
          break

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

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

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

A.append(1)
a = A[0]
b = A[1]
lcm = a * b // GCD(a,b)
for i in range(2,N):
  a = lcm
  b = A[i]
  lcm = a * b // GCD(a,b)
ans = 0
for i in range(N):
  ans = (ans + (lcm // A[i]))
print(ans%MOD)


### FIXED CODE ###

import fractions
from functools import reduce

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

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

lcm = lcm_list(A)
ans = 0
for i in range(N):
  ans = (ans + (lcm // A[i]))
print(ans % MOD)
### BUGGY CODE ###

import sys
from math import sqrt
from collections import Counter

input = sys.stdin.readline


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


inf = float("inf")
mod = 10 ** 9 + 7


def main():
    _ = I()
    a_list = input().split()

    c = Counter(a_list)
    dict = {}
    for k1, v1 in c.items():
        t = 0
        for k2, v2 in c.items():
            if k1 == k2:
                v2 -= 1
            if v2 >= 2:
                t += int(v2 * (v2 - 1) / 2)
            dict[k1] = t

    for a in a_list:
        print(dict[a])
    pass


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from math import sqrt
from collections import Counter

input = sys.stdin.readline


def I():
    return int(input())


def MI():
    return map(int, input().split())


def LI():
    return list(MI())


inf = float("inf")
mod = 10 ** 9 + 7


def main():
    _ = I()
    a_list = input().split()

    c = Counter(a_list)
    n = {}
    t = 0
    for k, v in c.items():
        n[k] = v - 1
        if v >= 2:
            t += int(v * (v - 1) / 2)

    for a in a_list:
        print(t - n[a])
    pass


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

H, W = map(int, input().split())

S = []
for i in range(H):
  S.append(list(input()))

dp = [[0] * W for h in range(H)]
dp1 = [[[0, 0] for w in range(W+1)] for h in range(H+1)]
for h in range(H):
  for w in range(W):
    if S[h][w] == '#':
      continue
    
    dp1[h+1][w+1] = [dp1[h][w+1][0]+1, dp1[h+1][w][1]+1]
    dp[h][w] = sum(dp1[h+1][w+1])


ans = 0
dp2 = [[[0, 0] for w in range(W+1)] for i in range(H+1)]
for h in range(H)[::-1]:
  for w in range(W)[::-1]:
    if S[h][w] == '#':
      continue

    dp2[h][w] = [dp2[h+1][w][0]+1, dp2[h][w+1][1]+1]
    dp[h][w] += sum(dp2[h][w])
    ans = max(ans, dp[h][w]-3)

print(ans)

### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())

S = np.ones([H+2, W+2], dtype=bool)
for h in range(H):
  S[h+1] = np.array(['.'] + list(input()) + ['.']) == '.'

dp1 = np.zeros([H+2, W+2, 2], dtype=int) # [up, left]
for h in range(H):
  dp1[h+1, :, 0] = (dp1[h, :, 0] + 1)*S[h+1]

for w in range(W):
  dp1[:, w+1, 1] = (dp1[:, w, 1] + 1)*S[:, w+1]

dp2 = np.zeros([H+2, W+2, 2], dtype=int) # [down, right]
for h in range(H, 0, -1):
  dp2[h, :, 0] = (dp2[h+1, :, 0] + 1)*S[h]

for w in range(W, 0, -1):
  dp2[:, w, 1] = (dp2[:, w+1, 1] + 1)*S[:, w]

print(np.max((np.sum(dp1, axis=2)+np.sum(dp2, axis=2))[1:-1, 1:-1])-3)
### BUGGY CODE ###

from math import factorial
n = int(input())
a_list = sorted(list(map(int, input().split())))

a_i_index = len(a_list) - 1
a_i = a_list[-1]
max = 0
max_j_index = None
for j_index in range(n):
    a_j = a_list[j_index]
    comb = factorial(a_i) / (factorial(a_i - a_j) * factorial(a_j))
    if comb > max:
        max = comb
        max_j_index = j_index
print(a_i, " ", a_list[max_j_index])

### FIXED CODE ###

n = int(input())
a_list = sorted(list(map(int, input().split())))
 
a_i_index = len(a_list) - 1
a_i = a_list[-1]
max = 0
max_j_index = None
 
nobori = True
 
tmp = a_list[0]
koeta = None
for j_index in range(n):
    if a_list[j_index] * 2 > a_i:
        koeta = j_index
        break
    else:
        tmp = j_index
 
comb2 = 0
if n == 2:
    print(*[a_list[1], a_list[0]])
elif koeta == 0:
    print(*[a_i, a_list[koeta]])
elif (a_list[koeta]- a_i/2) > (a_i/2 - a_list[koeta-1]):
    print(*[a_i,a_list[koeta-1]])
else:
    print(*[a_i, a_list[koeta]])
### BUGGY CODE ###

import sys

def is_ok(mid, gen=None, diff=0):
    print(mid, flush=True)
    res = input()
    if res == "Vacant":
        sys.exit()
    if gen is None:
        return res
    if diff % 2 == 0:
        return gen == res
    else:
        return gen != res


def meguru_bisect_kai(ng, ok, gen):
    cnt = 0
    while (abs(ok - ng) > 1) and cnt <= 20:
        mid = (ok + ng) // 2
        if is_ok(mid, gen, ok - mid):
            if (ok - mid) % 2 == 0:
                if gen == "Male":
                    gen = "Famale"
                else:
                    gen = "Male"
            ok = mid
        else:
            ng = mid
        cnt += 1
    return ok


n = int(input())
gen = is_ok(0)
is_ok(n - 1)
meguru_bisect_kai(0, n - 1, gen)

### FIXED CODE ###

n = int(input())

print(0, flush=True)
res = input()
if res == "Vacant":
    exit()

left = 0
right = n
gen = res


while True:
    mid = (left + right) // 2
    print(mid, flush=True)
    res = input()

    if res == "Vacant":
        exit()

    if gen == res:
        if (mid - left) % 2:
            right = mid
        else:
            left = mid
    else:
        if (mid - left) % 2:
            left = mid
            gen = res
        else:
            right = mid
### BUGGY CODE ###

x,y,z,k=map(int,input().split())
a=[int(i)for i in input().split()]
b=[int(i)for i in input().split()]
c=[int(i)for i in input().split()]
ans=[]
for A in a:
    for B in b:
        for C in c:
            ans+=[A+B+C]
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])

### FIXED CODE ###

def ca():
    x,y,z,k=map(int,input().split())
    a=[int(i)for i in input().split()]
    b=[int(i)for i in input().split()]
    c=[int(i)for i in input().split()]
    c.sort(reverse=True)
    AB=[i+j for i in a for j in b]
    AB.sort(reverse=True)
    ans=[i+j for i in AB[:k]for j in c]
    ans.sort(reverse=True)
    for i in ans[:k]:
        print(i)
    exit()
print(ca())
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

def chmin(cumsum, a):
    #print("chmin:", cumsum, a)
    if cumsum > a:
        return a
    else:
        return cumsum


def solve(N: int, K: int, h: "List[int]"):
    cumsums = [float("inf")]*N
    cumsums[0]=0
    cumsums[1]=abs(h[1]-h[0])

    for i in range(1, N):
        for j in range(1, K+1):
            if i >= j:
                cumsums[i] = chmin(cumsums[i], cumsums[i-j]+abs(h[i]-h[i-j]))
        #print(cumsums)
    return cumsums[-1]


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    K = int(next(tokens))  # type: int
    h = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    print(solve(N, K, h))

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

def solve(N: int, K: int, h: "List[int]"):
    cumsums = [float("inf")]*N
    cumsums[0]=0
    cumsums[1]=abs(h[1]-h[0])

    for i in range(1, N):
        for j in range(1, K+1):
            if i >= j:
                cumsums[i] = min(cumsums[i], cumsums[i-j]+abs(h[i]-h[i-j]))
        #print(cumsums)
    return cumsums[-1]

N, K = map(int, sys.stdin.readline().rstrip().split())
h = list(map(int, sys.stdin.readline().rstrip().split()))
print(solve(N, K, h))
### BUGGY CODE ###

N = int(input())
A = [int(_) for _ in input().split()]

A.sort(reverse=True)

while True:
    if len(A) == 1:
        break
    A[0] = A[0] % A[1]
    if A[0] == 0:
        A.pop(0)
    A.sort(reverse=True)

print(A[0])


### FIXED CODE ###

import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

N = int(input())
A = [int(_) for _ in input().split()]

print(gcd_list(A))
### BUGGY CODE ###

from collections import deque

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

dic = {}
npflag = [True] * N
p = [None] * N
dep = [float("-inf")] * N

for i in range(N+M-1):

    A,B = map(int,input().split())
    A -= 1
    B -= 1

    if A not in dic:
        dic[A] = []

    dic[A].append(B)
    npflag[B] = False

for i in range(N):

    if npflag[i]:
        root = i
        break

p[i] = -1
q = deque([i])
dep[i] = 0

while len(q) > 0:

    now = q.popleft()

    if now in dic:
        for i in dic[now]:

            if p[i] == None:
                p[i] = now
                dep[i] = dep[now] + 1
                q.append(i)

            elif dep[i] < dep[now] + 1:
                p[i] = now
                dep[i] = dep[now] + 1
                q.append(i)

for i in range(N):

    print (p[i]+1)

### FIXED CODE ###

from collections import deque

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

dic = {}
npflag = [True] * N
pnum = [0] * N
p = [None] * N
dep = [float("-inf")] * N

for i in range(N+M-1):

    A,B = map(int,input().split())
    A -= 1
    B -= 1

    if A not in dic:
        dic[A] = []

    dic[A].append(B)
    npflag[B] = False
    pnum[B] += 1

for i in range(N):

    if npflag[i]:
        root = i
        break

p[i] = -1
q = deque([i])
dep[i] = 0

while len(q) > 0:

    now = q.popleft()

    if now in dic:
        for i in dic[now]:

            if p[i] == None:
                p[i] = now
                dep[i] = dep[now] + 1
                pnum[i] -= 1
                if pnum[i] == 0:
                    q.append(i)

            elif dep[i] < dep[now] + 1:
                p[i] = now
                dep[i] = dep[now] + 1
                pnum[i] -= 1
                if pnum[i] == 0:
                    q.append(i)
                

for i in range(N):

    print (p[i]+1)