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

n = int(input())
table = [[]]
for i in range(n):
  a = list(map(int, input().split()))
  table.append(a)
cursor = [0]*(n+1)
is_matched = [False] * (n+1)
d = 0
match = 0
while match < n * (n-1) //2:
  now_match = match
  for i in range(1, n):
    for j in range(i+1, n+1):
      if cursor[i] < n-1 and table[i][cursor[i]] == j and not is_matched[i] and table[j][cursor[j]] == i and not is_matched[j]:
        match += 1
        cursor[i] += 1
        is_matched[i] = True
        cursor[j] += 1
        is_matched[j] = True
  if now_match == match:
    print(-1)
    exit()
  d += 1
  is_matched =  [False] * (n+1)
print(d)

### FIXED CODE ###

n = int(input())
table = [[] for _ in range(n+1)]
for i in range(1, n+1):
  a = list(map(int, input().split()))
  table[i] = a
cursor = [0]*(n+1)
is_matched = set()
d = 0
match = 0
while match < n * (n-1) //2:
  now_match = match
  for i in range(1, n):
    if cursor[i] < n-1 and i not in is_matched:
      j = table[i][cursor[i]]
      if i < j and j not in is_matched and table[j][cursor[j]] == i :
        match += 1
        cursor[i] += 1
        is_matched.add(i)
        cursor[j] += 1
        is_matched.add(j)
  if now_match == match:
    print(-1)
    exit()
  if d > 30000:
    print(499500)
    exit()  
  d += 1
  is_matched.clear()
print(d)
### BUGGY CODE ###

A = "AC"
N, Q = map(int, input().split())
S = list(input())
ans = []
for j in range(N - 1):
    tmp1 = S[j] + S[j + 1]
    if tmp1 == A:
        ans.append(1)
    else:
        ans.append(0)

for i in range(Q):
    l, r = map(int, input().split())
    print(sum(ans[l-1:r-1]))



### FIXED CODE ###

A = "AC"
N, Q = map(int, input().split())
S = list(input())
ans = [0]
cnt = 0
for j in range(N - 1):
    tmp1 = S[j] + S[j + 1]
    if tmp1 == A:
        cnt += 1
    ans.append(cnt)

for i in range(Q):
    l, r = map(int, input().split())
    print(ans[r-1] - ans[l-1])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
for i in range(len(A)):
    count = 0
    d = {}
    A_ = A[:]
    A_.pop(i)
    A_.sort()
    for j in range(len(A_)-1):
        if A_[j] == A_[j+1]:
            count += 1
        elif A_[j] != A_[j+1]:
            count += 1
            d[A_[j]] = (count*(count-1))//2
            count = 0
    count += 1
    d[A_[j+1]] = (count*(count-1))//2
    print(sum(d.values()))

### FIXED CODE ###

N = int(input())
A = list(map(lambda x: int(x)-1, input().split()))
d = [0] * N
for i in A:
    d[i] += 1
s = sum(map(lambda x: x*(x-1)//2, d))
for i in A:
    print(s + (1 - d[i]))
### BUGGY CODE ###

# 入力文字列
get_str = input()

# 操作回数
N = int(input())

# 操作
for i in range(N):
    # 取得操作
    inp_cmd = input().split()

    # inp_cmd[0] = 1 なら反転
    if(int(inp_cmd[0]) == 1):
        get_str = get_str[::-1]
    # inp_cmd[0] = 2
    else:
        # inp_cmd[1]なら、先頭に文字追加
        if(int(inp_cmd[1]) == 1):
            get_str = inp_cmd[2] + get_str
        # inp_cmd[2]なら、末尾に文字追加
        else:
            get_str = get_str + inp_cmd[2]
print(get_str)

### FIXED CODE ###

# 入力文字列
get_str = list(input())

# 操作回数
N = int(input())

# リバースフラグ
r_flag = 0

left_str = []
right_str = []
# 操作
for i in range(N):
    # 取得操作
    inp_cmd = list(input().split())
    # inp_cmd[0] = 1 ならリバースフラグ更新
    if(inp_cmd[0] == '1'):
        r_flag = (r_flag+1) % 2
    else:
        # inp_cmd[1]=1、かつリバースフラグなし
        # inp_cmd[1]=2、かつリバースフラグあり
        # 先頭に文字追加
        if((inp_cmd[1] == '1' and r_flag == 0) or (inp_cmd[1] == '2' and r_flag == 1)):
            left_str.append(inp_cmd[2])
        # 上記以外は後ろに追加
        else:
            right_str.append(inp_cmd[2])

# 左文字列リストを反転
left_str = left_str[::-1]

# 文字列結合
list_str = []
list_str = left_str + get_str + right_str

# リバースフラグあり
if(r_flag == 1):
    list_str = list_str[::-1]

out_str = ''.join(list_str)
print(out_str)
### BUGGY CODE ###

n = input()
A = [int(x) for x in input().split()]
product = 1

for a in A:
    product *= a

print(product if product <= 10**18 else -1)


### FIXED CODE ###

import sys

n = input()
A = sorted([int(x) for x in input().split()], reverse=True)

if A[-1] == 0:
    print(0)
    sys.exit()

product = 1
for a in A:
    product *= a
    if product > 10**18:
        product = -1
        break

print(product)
### BUGGY CODE ###

n=int(input())
a = input()

c = 0
for i in range(n):
  for j in range(n):
    if j + 2*i < n:
      if a[j] != a[j+i] and a[j+i] != a[j+2*i] and a[j] != a[j+2*i]:
        c+=1

ans = a.count("R") * a.count("G") * a.count("B") - c
print(ans)

### FIXED CODE ###

n=int(input())
a = input()

c = 0
for i in range(1,n//2 +1):
  for j in range(n-2*i):
    if a[j] != a[j+i] and a[j+i] != a[j+2*i] and a[j] != a[j+2*i]:
      c+=1

ans = a.count("R") * a.count("G") * a.count("B") - c
print(ans)
### BUGGY CODE ###

import numpy as np
N, K, Q = [int(i) for i in input().split()]
A = []
for i in range(Q):
    A.append(int(input())-1)

point = np.array([A.count(i) for i in range(N)])

score = K - Q + point
result = ['Yes' if score[i] > 0 else 'No' for i in range(len(score))]
for i in range(len(result)):
    print(result[i])

### FIXED CODE ###

N, K, Q = [int(i) for i in input().split()]

score = [K - Q] * N

for i in range(Q):
    score[int(input())-1] += 1

for i in range(N):
    if score[i] > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import sys
l = raw_input().split()
N = int(l[0])
M = int(l[1])
nlist = []
list1 = []
flag = True
for i in range(0, M):
    tmp = raw_input().split()
    a = int(tmp[0])
    b = int(tmp[1])
    if b == N:
        nlist.append(a)
    if a == 1:
        list1.append(b)
for i in list1:
    if i in nlist:
        print('POSSIBLE')
        flag = False
        break
if flag:
    print('IMPOSSIBLE')

### FIXED CODE ###

import sys
l = raw_input().split()
N = int(l[0])
M = int(l[1])
nlist = []
list1 = []
for i in range(0, M):
    tmp = raw_input().split()
    a = int(tmp[0])
    b = int(tmp[1])
    if a == 1:
        list1.append(b)
        continue
    if b == N:
        nlist.append(a)
        continue
matched_list = list(set(list1) & set(nlist))
if len(matched_list) == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')
### BUGGY CODE ###

from collections import defaultdict
def main():
    n = int(input())
    A = list(map(int, input().split()))
    d = defaultdict(int)
    for a in A:
        B = list(f'{a:030b}')
        for i, b in enumerate(B):
            if b == '1':
                d[i] += 1
    ANS = []
    for a in A:
        B = list(f'{a:030b}')
        ans = 0
        for i, b in enumerate(B):
            if b == '1':
                k = d[i] - 1
            else:
                k = d[i]
            if k % 2 == 1:
                ans += pow(2, 29 - i)
        ANS.append(str(ans))
    print(' '.join(ANS))





if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict
def main():
    n = int(input())
    A = list(map(int, input().split()))
    d = defaultdict(int)
    for a in A:
        B = list(f'{a:030b}')
        for i, b in enumerate(B):
            if b == '1':
                d[i] += 1
    ANS = []
    for a in A:
        B = list(f'{a:030b}')
        ans = 0
        for i, b in enumerate(B):
            if b == '1':
                k = d[i] - 1
            else:
                k = d[i]
            if k % 2 == 1:
                ans += pow(2, 29 - i)
        ANS.append(str(ans))
    print(' '.join(ANS))





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

import math
from collections import defaultdict

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

A = defaultdict(int)
p = 10 ** 9 + 7

if m == 1:
    print(1)
    exit()

def fact(n, p=10**9 + 7):
    f = [1]
    for i in range(1, n+1):
        f.append(f[-1]*i%p)
    return f

def invfact(n, f, p=10**9 + 7):
    inv = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        inv.append(inv[-1]*i%p)
    return inv[::-1]

f = fact(30+10**5)
invf = invfact(30+10**5, f)

def comb(a, b):
    return f[a] * invf[b] * invf[a-b] % p

i = 2
rt = math.sqrt(m) + 1

while m != 1 and (A or i <= rt):
    while m % i == 0:
        m //= i
        A[i] += 1
    i += 1

if not A:
    print(n)
    exit()

n -= 1
ans = 1

for v in A.values():
    ans *= comb(v+n, n)
    ans %= p

print(ans)

### FIXED CODE ###

import math
from collections import defaultdict

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

A = defaultdict(int)
p = 10 ** 9 + 7

if m == 1:
    print(1)
    exit()

def fact(n, p=10**9 + 7):
    f = [1]
    for i in range(1, n+1):
        f.append(f[-1]*i%p)
    return f

def invfact(n, f, p=10**9 + 7):
    inv = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        inv.append(inv[-1]*i%p)
    return inv[::-1]

f = fact(30+10**5)
invf = invfact(30+10**5, f)

def comb(a, b):
    return f[a] * invf[b] * invf[a-b] % p

i = 2

while m != 1 and i <= math.sqrt(m) + 1:
    while m % i == 0:
        m //= i
        A[i] += 1
    i += 1

if not A:
    print(n)
    exit()

if m != 1:
    A[m] = 1

n -= 1
ans = 1

for v in A.values():
    ans *= comb(v+n, n)
    ans %= p

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

N = int(input())
alist = list(map(int, input().split()))
alist.sort(reverse=True)
sumscore=0
posit = list()
posit.append(alist[0])
for n in range(1,N):
  sumscore = sumscore + posit[0]
  posit = posit[1:]
  posit.append(alist[n])
  posit.append(alist[n])

print(sumscore)

### FIXED CODE ###

N = int(input())
alist = list(map(int, input().split()))
alist.sort(reverse=True)
sumscore=alist[0]
for n in range(1,int(N/2)):
  sumscore = sumscore + alist[n]*2
if N%2==1:
  sumscore += alist[n+1]

print(sumscore)
### BUGGY CODE ###

import math
import fractions
import collections
import itertools
from collections import deque
d=collections.deque()
S=input()
N=len(S)
cnt=0

amari=[0]*(N+1)
num=0
for i in range(N):
    d.append(int(S[i]))
#print(d)
for i in range(N):
    n=d.pop()
    num=(num+pow(10,i)*n)%2019
    amari[i+1]=num
#print(amari)
c=collections.Counter(amari)
values=list(c.values())	#aのCollectionのvalue値のリスト(n_1こ、n_2こ…)

#for i in range(len(key)):
#    l.append([key[i],values[i]])#lは[要素i,n_i]の情報を詰めたmatrix
#xprint(l)
for i in range(len(values)):
    cnt=cnt+(values[i]*(values[i]-1))//2
print(cnt)

### FIXED CODE ###

import math
import fractions
import collections
import itertools
from collections import deque
d=collections.deque()
S=list(input())
N=len(S)
cnt=0

amari=[0]*(N+1)
num=0
for i in range(N):
    d.append(int(S[i]))
#print(d)
for i in range(N):
    n=d.pop()
    num=(num+pow(10,i,2019)*n)%2019
    amari[i+1]=num
#print(amari)
#c=collections.Counter(amari)
#values=list(c.values())	#aのCollectionのvalue値のリスト(n_1こ、n_2こ…)
amari.sort()
#for i in range(len(key)):
#    l.append([key[i],values[i]])#lは[要素i,n_i]の情報を詰めたmatrix
#xprint(l)
buf=0
#print(amari)
c=collections.Counter(amari)
values=list(c.values())	#aのCollectionのvalue値のリスト(n_1こ、n_2こ…)
key=list(c.keys())	#先のvalue値に相当する要素のリスト(要素1,要素2,…)
#for i in range(len(key)):
#    l.append([key[i],values[i]])#lは[要素i,n_i]の情報を詰めたmatrix
#xprint(l)
for i in range(len(values)):
    cnt=cnt+(values[i]*(values[i]-1))//2
print(cnt)
### BUGGY CODE ###

n,m,s,t = map(int,input().split())
en = []
su = []
for i in range(m):
    x1,y1,z1,a1=[int(i) for i in input().split()]
    en.append([x1-1,y1-1,z1])
    en.append([y1-1,x1-1,z1])
    su.append([x1-1,y1-1,a1])
    su.append([y1-1,x1-1,a1])
def shortest_path(edge,num_v,start):
    inf = float("inf")
    d = [inf for f in range(num_v)]
    d[start] = 0;
    while True:
        update = False
        for e in edge:
            if d[e[0]] != inf and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True
        if not update:
            break
    return d
from collections import deque
ans = deque([])
tori = shortest_path(en,n,s-1)
kae = shortest_path(su,n,t-1)
sai = float("inf")
for i in range(n-1,-1,-1):
  kon = kae[i]+tori[i]
  if sai > kon:
     ans.appendleft(kon)
     sai = kon
  else:
    ans.appendleft(sai)
    
moti = 10**15
for i in range(n):
  print(moti-ans[i])

### FIXED CODE ###

import heapq
n,m,s,t = map(int,input().split())
en = []
su = []
for i in range(m):
    x1,y1,z1,a1=[int(i) for i in input().split()]
    en.append([x1-1,y1-1,z1])
    su.append([x1-1,y1-1,a1])
def shortest_path(edge,num_v,start):
    inf = float("inf")
    cost = [[] for i in range(n+1)]
    for path in edge:
      cost[path[0]].append((path[1],path[2]))
      cost[path[1]].append((path[0],path[2]))
    d = [inf for j in range(num_v)]
    q = []
    heapq.heappush(q, (0, start))
    d[start] = 0
    while len(q) != 0:
      prov_cost, src = heapq.heappop(q)
      if d[src] < prov_cost:
                continue
      for dest,weight in cost[src]:
        if weight != float('inf') and d[dest] > d[src] + weight:
          d[dest] = d[src] + weight
          heapq.heappush(q, (d[dest], dest))
    return d
 
 
from collections import deque
ans = deque([])
tori = shortest_path(en,n,s-1)
kae = shortest_path(su,n,t-1)
sai = float("inf")
for i in range(n-1,-1,-1):
  kon = kae[i]+tori[i]
  if sai > kon:
     ans.appendleft(kon)
     sai = kon
  else:
    ans.appendleft(sai)
    
moti = 10**15
for i in range(n):
  print(moti-ans[i])
### BUGGY CODE ###

import math
import numpy as np
from fractions import gcd
import fractions as math
import statistics
import collections
from functools import reduce
import itertools
from collections import defaultdict
import bisect
from fractions import Fraction
 
 
N = int(input())
A=list(map(int, input().split()))
 
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
 
num = lcm_list(A)
 
ans = 0
 
for i in range(N):
    ans += (num // A[i])
    ans %= 10**9+7

print(ans)

### FIXED CODE ###

import fractions as math
from functools import reduce
 
 
N = int(input())
A=list(map(int, input().split()))
 
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
 
num = lcm_list(A)
 
ans = 0
 
for i in range(N):
    ans += (num // A[i])
 
print(ans%(10**9+7))
### BUGGY CODE ###

import numpy as np
inf = np.inf
N, M = list(map(int, input().split(" ")))
keys = []
for _ in range(M):
	c = list(map(int, input().split(" ")))
	j = list(map(int, input().split(" ")))
	keys.append([c[0], np.sum([1 << k-1 for k in j])])
dp = [inf for _ in range(1 << N)]
dp[0] = 0
for i in range(len(dp)):
    for key in keys:
        t = i | key[1]
        dp[t] = min(dp[t], key[0] + dp[i])
if dp[-1]==inf:
    print(-1)
else:
    print(dp[-1])

### FIXED CODE ###

def main():
  Inf = 10**8
  N, M = list(map(int, input().split(" ")))
  keys = []
  for _ in range(M):
      c = list(map(int, input().split(" ")))
      j = list(map(int, input().split(" ")))
      keys.append([c[0], sum([1 << k-1 for k in j])])
  dp = [Inf for _ in range(1 << N)]
  dp[0] = 0
  for i in range(len(dp)):
      for key in keys:
          t = i | key[1]
          dp[t] = min(dp[t], key[0] + dp[i])
  if dp[-1]==Inf:
      print(-1)
  else:
      print(dp[-1])
main()
### BUGGY CODE ###

import math
k = int(input())
ans = 0
for x in range(1,k+1):
    for y in range(1,k+1):
        for z in range(1,k+1):
            key = []
            key.append(math.gcd(x,math.gcd(y,z)))
            key.append(math.gcd(y,math.gcd(x,z)))
            key.append(math.gcd(z,math.gcd(y,x)))
            ans += max(key)
print(ans)

### FIXED CODE ###

import math
k = int(input())
ans = 0
for x in range(1,k+1):
    for y in range(1,k+1):
        for z in range(1,k+1):
            ans += math.gcd(x,math.gcd(y,z))
print(ans)
### BUGGY CODE ###

N = int(input())
Ps = list(map(int,input().split()))
ans = 1
for n in range(2,N+1):
    if Ps[n-1] == min(Ps[:n]):
        ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
Ps = list(map(int,input().split()))
ans = 0
minP = N
for p in Ps:
    if p <= minP:
        ans += 1
    minP = min(minP, p)
print(ans)
### BUGGY CODE ###

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

ans = 0
for i in range(n):
    for j in range(i+1,n):
        if a[i]+a[j] == j-i:
            ans += 1
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int,input().split()))
l = [0]*n
r = [0]*n
for i in range(n):
    l[i] = i+a[i]
    r[i] = i-a[i]
    
l=Counter(l)
r=Counter(r)
ans = 0
for i in range(max(r.keys())+1):
    ans += l[i]*r[i]
print(ans)
### BUGGY CODE ###

import sys
h, n = map(int, input().split())
A = [0] * n
B = [0] * n
for i in range(n):
    A[i], B[i] = map(int, input().split())
min_hp = h

dp = [sys.maxsize] * (min_hp + 1)
dp[0] = 0

for i in range(0, min_hp + 1):
    for j in range(n): # type of spell
        next_index = min(i + A[j], min_hp)
        dp[next_index] = min(dp[next_index], dp[i] + B[j])

# dp = [[sys.maxsize] * (max_hp + 1) for i in range(n + 1)]
# for i in range(n + 1):
#     for j in range(min(A[1:]) + 1):
#         dp[i][j] = min(B[1:])
#
# for i in range(1, n + 1):
#     for j in range(1, max_hp + 1):
#         dp[i][j] = dp[i-1][j] if A[i] > j else min(dp[i-1][j-A[i]] + B[i], dp[i-1][j])
#         # dp[i][j] = dp[i][j-1] + B[i] if A[i] > j else min(dp[i][j-A[i]] + B[i], dp[i][j-1] + B[i])
print(dp[h])


### FIXED CODE ###

H, N = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]
max_a = max(a for a, b in ab)
dp = [0]*(H+max_a)
for i in range(1, H+max_a):
    dp[i] = min(dp[i-a]+b for a, b in ab)
print(dp[H])
### BUGGY CODE ###

X = int(input())
for A in range(-10000, 10000):
    for B in range(-10000, 10000):
        if A**5 - B**5 == X:
            print(A, B)
            break
    else:
        continue
    break

### FIXED CODE ###

X = int(input())
for A in range(-200, 200):
    for B in range(-200, 200):
        if A**5 - B**5 == X:
            print(A, B)
            break
    else:
        continue
    break
### BUGGY CODE ###

N, A, B = map(int, input().split(' '))


def main():
    blue = red = 0

    for i in range(10 ** 100):
        blue += A

        if blue + red > N:
            blue -= blue + red - N
            break

        red += B

        if blue + red > N:
            red -= blue + red - N
            break

    return blue


print(main())


### FIXED CODE ###

N, A, B = map(int, input().split(' '))


def main():
    blue = (N // (A+B)) * A

    blue += min(A, N % (A+B))

    return blue


print(main())
### BUGGY CODE ###

import sys

def main():
    _,S = open(0).read().split()
    s1 = S[:int(len(S)*3/4)+1]

    maxLen = 0
    lenS1 = len(s1)
    for i in range(lenS1):
        for j in range(i+1+maxLen,lenS1):
            # print(s1[i:j], S[j:], j,i)
            if s1[i:j] in S[j:] and j-i+1 > maxLen:
                maxLen = j-i

    print(maxLen)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

def main():
    _,S = open(0).read().split()
    s1 = S[:int(len(S)*3/4)+1]

    maxLen = 0
    lenS1 = len(s1)
    for i in range(lenS1):
        for j in range(i+1+maxLen,lenS1):
            # print(s1[i:j], S[j:], j,i)
            if len(s1[i:j]) > len(S[j:]):
                break
            if s1[i:j] in S[j:]:
                maxLen = j-i
            else:
                break

    print(maxLen)

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

n,m=[int(x) for x in input().split()]
X=[int(x) for x in input().split()]
Y=[int(x) for x in input().split()]
from itertools import product,combinations
mod=10**9+7
ans=0
for x,y in product(combinations(X,2),combinations(Y,2)):
    ans=(ans+(x[1]-x[0])*(y[1]-y[0]))%mod
print(ans)

### FIXED CODE ###

n,m=[int(x) for x in input().split()]
x=[int(x) for x in input().split()]
y=[int(x) for x in input().split()]
mod=10**9+7
ans=0
ysum=0
for j in range(1,m):
    ysum+=(y[j]-y[j-1])*j*(m-j)
for i in range(1,n):
    ans=ans+(x[i]-x[i-1])*i*(n-i)*ysum
print(ans%mod)
### BUGGY CODE ###

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

genzaichi=1
rireki=[]
houmon=[0]*(N+1)
flag=0

for i in range(1,K+1):
    genzaichi=A[genzaichi-1]
    if genzaichi not in rireki:
        houmon[genzaichi]=i
        rireki.append(genzaichi)
    else:
        roop_from=genzaichi
        x=houmon[roop_from]
        roop=i-x
        flag=1
        break

if flag==0:
    print(genzaichi)
else:
    genzaichi=roop_from
    K=(K-x)-((K-x)//roop)*roop
    for i in range(K):
        genzaichi=A[genzaichi-1]
    print(genzaichi)

### FIXED CODE ###

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

genzaichi=1
rireki=set()
houmon=[0]*(N+1)
flag=0

for i in range(1,K+1):
    genzaichi=A[genzaichi-1]
    if genzaichi not in rireki:
        houmon[genzaichi]=i
        rireki.add(genzaichi)
    else:
        roop_from=genzaichi
        x=houmon[roop_from]
        roop=i-x
        flag=1
        break

if flag==0:
    print(genzaichi)
else:
    genzaichi=roop_from
    K=(K-x)-((K-x)//roop)*roop
    for i in range(K):
        genzaichi=A[genzaichi-1]
    print(genzaichi)
### BUGGY CODE ###

import sys
import bisect
from heapq import heappush, heappop
sys.setrecursionlimit(10 ** 7)

# TLE

N, Q = map(int, input().split())
STX = [[int(x) for x in input().split()] for _ in range(N)]
EVENT = []
for s, t, x in STX:
    EVENT.append((s-x, 1, x))
    EVENT.append((t-x, 0, x))

for i in range(Q):
    d = int(input())
    EVENT.append((d, 2, i))

ans = [-1] * Q

EVENT.sort()

# print(EVENT)

STOP = set()
h = []
for t, op, x in EVENT:
    if op == 2 and STOP:
        while h[0] not in STOP:
            heappop(h)
        ans[x] = h[0]
    elif op == 1:
        STOP.add(x)
        heappush(h, x)
    elif op == 0:
        STOP.remove(x)


print("\n".join(map(str, ans)))


### FIXED CODE ###

#D in [S_i-X_i,T_i-X_i) → Xiで止まる
import sys
input = sys.stdin.readline
from heapq import heappop,heappush
from collections import defaultdict

N,Q = map(int,input().split())
task = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  task.append((t-x,0,x)) # xで止まらなくなる
  task.append((s-x,1,x)) # xで止まる

for i in range(Q):
  d = int(input())
  task.append((d,2,i)) # 止まる位置を答える
answer = [-1]*Q

task.sort()

# 引っかかってる場所の管理
se = set()
se_hp = [] # heapで最小値を先頭に保つ

# 小さい時刻から順に見ていく
for a,b,c in task:
  if not b: # b == 0
    se.remove(c)
  elif b&1: # b == 1
    se.add(c)
    heappush(se_hp,c)
  else: # b == 2
    while se_hp and se_hp[0] not in se:
      heappop(se_hp)
    answer[c] = se_hp[0] if se_hp else -1

print('\n'.join(map(str,answer)))
### BUGGY CODE ###

n = int(input())

str_list = []
for n in range(n):
    str_list.append(input())

cnt_dict = {_ : str_list.count(_) for _ in set(str_list)}


for ans in sorted([l[0] for l in cnt_dict.items() if l[1] == max(cnt_dict.values())]):
	print(ans)


### FIXED CODE ###

from collections import Counter

N = int(input())
S = [input() for _ in range(N)]

dic = Counter(S)

tmp = max(dic.values())
ans = [key for key, value in dic.items() if value == tmp]

# もうちょいかっこいい書き方があるはず。リストを1行1str出力 and 最後に改行しないように
for key in sorted(ans):
    print(key, end="")
    print("")
### BUGGY CODE ###

n, y = map(int,input().split())
flag = False

for i in range(y//10000+1):
    for j in range(y//5000+1):
        tmp = y - 10000*i - 5000*j
        k = tmp//1000
        if i+j+k == n and k >= 0:
            print('{0} {1} {2}'.format(i,j,k))
            flag = True
            break
    if flag:
        break
if not flag:
    print('-1 -1 -1')


### FIXED CODE ###

n, y = map(int,input().split())
flag = False

for i in range(y//10000+1):
    for j in range(y//5000+1):
        tmp = y - 10000*i - 5000*j
        k = tmp//1000
        if i+j+k == n and k >= 0:
            print('{0} {1} {2}'.format(i,j,k))
            flag = True
            break
    if flag:
        break
if not flag:
    print('-1 -1 -1')