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

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

N=int(input())
power=1
for i in range(N):
  power*=(i+1)

print(power%(10**9+7))

### FIXED CODE ###

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

N=int(input())
power=1
for i in range(N):
  power*=(i+1)
  power%=(10**9+7)
  
print(power)
### BUGGY CODE ###

n = int(input())
import math
num = math.factorial(n)
ans = 0
for i in range(1,num+1):
  if num%i==0:
    ans+=1
print(ans)

### FIXED CODE ###

n = int(input())
import math
num = math.factorial(n)
dic={}
i = 2
ans = 1
while num != 1:
  cnt = 1
  while num%i == 0:
    num = num//i
    cnt+=1
  ans = ans*cnt
  i +=1
print(ans%(10**9+7))
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
P = []
for i in range(Q):
    P.append((int(_) for _ in input().split()))

for i in range(Q):
    l,r = P[i]
    s = S[l-1:r]
    print(s.count('AC'))


### FIXED CODE ###

def countAC(s):
    counter = 0
    index = [0]
    for i in range(1,N):
        if s[i-1] == 'A':
            if s[i] == 'C':
                counter += 1
                index.append(counter)
                continue
        index.append(counter)
    return index

N,Q = (int(_) for _ in input().split())
S = input()
SIndex = countAC(S)
out = 0
for i in range(Q):
    l,r = (int(_) for _ in input().split())
    print(SIndex[r-1] - SIndex[l-1])
### BUGGY CODE ###

n, k = map(int, input().split())
tel = list(map(int, input().split()))
log = [1]
end = True
while(end):
    log.append(tel[log[-1] - 1])
    for i in range(len(log) - 1):
        if(log[i] == log[-1]):
            star = i
            mod = len(log) - star - 1
            end = False
if(k < len(log)):
    print(log[k])
else:
    print(log[(k - star) % mod + star])

### FIXED CODE ###

n, k = map(int, input().split())
tel = list(map(int, input().split()))
log = [1]
record = [0] * n
while(True):
    log.append(tel[log[-1] - 1])
    if(record[log[-1] - 1] == 1):
        break
    record[log[-1] - 1] += 1
for i in range(len(log) - 1):
    if(log[i] == log[-1]):
        star = i
        mod = len(log) - star - 1
        break
if(k < len(log)):
    print(log[k])
else:
    print(log[(k - star) % mod + star])
### BUGGY CODE ###

s=[i for i in input()]
cnt=0
for i in range(100000000000000000):
    l=len(s)
    if l==0 or s.count("0")==l or s.count("1")==l:
        break
    else:
        for i in range(l):
            try:
                if int(s[i])+int(s[i+1])==1:
                    cnt+=2
                    s=s[0:i]+s[i+2:]
            except:
                pass
print(cnt)

### FIXED CODE ###

s=[i for i in input()]
one=s.count("1")
zero=s.count("0")
print(len(s)-abs(one-zero))
### BUGGY CODE ###

S = list(input())
S.reverse()
N = len(S)
mod = 10**9+7
dp = [[0 for r in range(13)] for n in range(N+1)]
dp[0][0] = 1
lookup = [[0 for d in range(10)] for n in range(N)]
for n in range(N):
    for d in range(10):
        lookup[n][d] = d*pow(10, n, 13) % 13
for n in range(1, N+1):
    if S[n-1] == '?':
        for d in range(10):
            for r in range(13):
                dp[n][(r+lookup[n-1][d]) % 13] += dp[n-1][r] % mod
    else:
        for r in range(13):
            dp[n][(r+lookup[n-1][int(S[n-1])]) % 13] += dp[n-1][r] % mod
print(dp[-1][5] % mod)


### FIXED CODE ###

S = list(input())
S.reverse()
N = len(S)
mod = 10**9+7
dp = [[0 for r in range(13)] for n in range(N+1)]
dp[0][0] = 1
lookup = [[0 for d in range(10)] for n in range(N)]
for n in range(N):
    for d in range(10):
        lookup[n][d] = d*pow(10, n, 13) % 13
for n in range(1, N+1):
    if S[n-1] == '?':
        for d in range(10):
            for r in range(13):
                dp[n][(r+lookup[n-1][d]) % 13] += dp[n-1][r] % mod
    else:
        for r in range(13):
            dp[n][(r+lookup[n-1][int(S[n-1])]) % 13] += dp[n-1][r] % mod
print(dp[-1][5] % mod)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = int(1e+9 + 7)
L = A[0]
p = mod - 2
X = []
while p != 0:
  X = [p%2] + X[:]
  p //= 2

def inved(x):
  y = 1
  for i in range(len(X)):
    if X[i] == 1:
      y *= x
      y %= mod
    if i != len(X) - 1:
      y *= y
      y %= mod
  return y

for i in range(N-1):
  a, b = L, A[i+1]
  while b != 0:
    a, b = b, a % b
  L //= a
  b = A[i+1] // a
  L = a * b * L
S = 0
for i in range(N):
  S += (L * inved(A[i])) % mod
  S %= mod
print(S)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = int(1e+9 + 7)
L = A[0]
p = mod - 2
X = []
while p != 0:
  X = [p%2] + X[:]
  p //= 2

def inved(x):
  y = 1
  for i in range(len(X)):
    if X[i] == 1:
      y *= x
      y %= mod
    if i != len(X) - 1:
      y *= y
      y %= mod
  return y

for i in range(N-1):
  a, b = L, A[i+1]
  while b != 0:
    a, b = b, a % b
  b = A[i+1] // a
  L = b * L
S = 0
for i in range(N):
  S += (L * inved(A[i])) % mod
  S %= mod
print(S)
### BUGGY CODE ###

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


b=set(a)

cnt=0

for item in b:
  t=a.count(item)
  if t>item:
    cnt+=t-item
  elif t==item:
    pass
  else:
    cnt+=t
    
print(cnt)

### FIXED CODE ###

import collections

N=int(input())
a=list(map(int,input().split()))
a.sort()

cnt=0

c=collections.Counter(a)
#print(c)

for item in c:
  t=c[item]
  if t>item:
    cnt+=t-item
  elif t==item:
    pass
  else:
    cnt+=t

#while len(a)>0:
#  item=a[0]
#  t=(item)
#  #print(item,t,a)
#  if t>item:
#    cnt+=t-item
#  elif t==item:
#    pass
#  else:
#    cnt+=t
#  del a[0:t]
#  #print("after",a)
  
print(cnt)
### BUGGY CODE ###

s = list(input())
ans = 0
while True:
    end = 0
    for i in range(len(s) - 1):
        if len(s) == 0:
            end = 0
            break
        if s[i] != s[i + 1]:
            ans += 2
            end = 1
            del s[i:i + 2]
            break
    if end == 0:
        break
print(ans)

### FIXED CODE ###

s = list(input())
n = len(s)
i = s.count("0")
print(min(i, n-i)*2)
### BUGGY CODE ###

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

Max = 0

for x in range(1,1+N):
    fx = int(A*x/B) - A * int(x/B)
    Max = max(Max,fx)
print(Max)


### FIXED CODE ###

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


if B < N:
    Max = int(A*(B-1)/B)
    X = int(N/B)
    fx = int(A*(B*X-1)/B) - A * int((B*X-1)/B)
    # Max = max(fx,Max)
    # for x in range(1,X):
    #     fx = int(A*x/B) - A * int(x/B)
    #     Max = max(Max,fx)
elif B == N:
    Max = int(A*(B-1)/B)
else:
    Max = int(A*N/B)
print(Max)
### BUGGY CODE ###

n,m = list(map(int,input().split()))
a = []
b = []
dic = {}
count = 0
"""
for i in range(n):
    x,y = list(map(int,input().split()))
    dic[x] = y
dic = sorted(dic.items())



for key in dic:
    if m - dic[key] > 0:
        count += key * dic[key]
        m = m - dic[key]
    else:
        count += m * key
        break
print(count)
"""
            



for i in range(n):
    x,y = list(map(int,input().split()))
    a.append(x)
    b.append(y)
count = 0


while m > 0:
    mi = min(a)
    if m - b[a.index(mi)] > 0 : # Bi本買う
        m = m-b[a.index(mi)]
        count += b[a.index(mi)] * min(a)
    else:
        count += m * mi
        break
    d = a.index(mi)
    del a[d]
    del b[d]
print(count)






### FIXED CODE ###

n,m = list(map(int,input().split()))
a = []
b = []
dic = {}
count = 0
data = [0] * n
for i in range(n):
    x,y = list(map(int,input().split()))
    data[i] = [x,y]
data = sorted(data,key = lambda x : x[0])
for i in range(n):
    if m > data[i][1]:
        count += data[i][0] * data[i][1]
        m -= data[i][1]
    else:
        count += data[i][0] * m
        break
print(count)

"""
for i in range(n):
    x,y = list(map(int,input().split()))
    dic[x] = y
dic = sorted(dic.items())



for key in dic:
    if m - dic[key] > 0:
        count += key * dic[key]
        m = m - dic[key]
    else:
        count += m * key
        break
print(count)
"""
            

"""

for i in range(n):
    x,y = list(map(int,input().split()))
    a.append(x)
    b.append(y)
count = 0


while m > 0:
    mi = min(a)
    d = a.index(mi)
    if m > b[d]  : # Bi本買う
        m -= b[d]
        count += b[d] * mi
    else:
        count += m * mi
        break
    del a[d]
    del b[d]
print(count)



"""
### BUGGY CODE ###

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

#print(L)

count=0
for i in range(0, n,1):
  x=0
  for j in range(i+1,n,1):
    for k in range(j+1,n,1):
      if (L[j] + L[k] > L[i]):
        count +=1
      else:
        if k == j+1:
          x=1
        break
    if x==1:
      break

print(count)

### FIXED CODE ###

from bisect import bisect_left
N = int(input())
L = sorted(list(map(int, input().split())))
ans = 0
for i in range(N):
    for j in range(i+1,N):
        ans += bisect_left(L, L[i]+L[j])-j-1
print(ans)
### BUGGY CODE ###

from collections import Counter

N = int(input())
X = input()
x = []
for i in range(N):
    x.append(X[i])
    
def popcount(n):
    return Counter(bin(n))['1']

def f(n):
    cnt = 0
    while n != 0:
        n %= popcount(n)
        cnt += 1
    return cnt

for i in range(N):
    n = x.copy()
    if x[i] == '1':
        n[i] = '0'
    else:
        n[i] = '1'
    n = ''.join(n)
    print(f(int(n, 2)))

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def pop_cnt(n):
    return bin(n).count('1')


def f(n):
    cnt = 0
    while n != 0:
        n = n % pop_cnt(n)
        cnt += 1
    return cnt
 
n = int(readline())
x2 = list(readline().decode().rstrip())
x10 = int(''.join(x2), 2)

c = x2.count('1')
mod1 = x10 % (c + 1)
mod2 = x10 % (c - 1) if c-1 != 0 else 0

for i in range(n):
    ans = 0
    if x2[i] == '0':
        t = (mod1 + pow(2, n-i-1, c+1)) % (c+1)
    else:
        if c-1 != 0:
            t = (mod2 - pow(2, n-i-1, c-1)) % (c-1)
        else:
            print(0)
            continue
    
    ans = f(t) + 1
    print(ans)
### BUGGY CODE ###

# 2020/07/25
# M-SOLUTIONS プロコンオープン 2020 - C

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

# Calc
pt = a[0]
km1 = k - 1

for i in range(k):
    pt = pt * a[i]

for i in range(k, n):
    bef_pt = pt
    pt = pt / a[i-k] * a[i]

    # Output
    if bef_pt < pt:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

# 2020/07/25
# M-SOLUTIONS プロコンオープン 2020 - C

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

# Calc
for i in range(k, n):
    # Output
    if a[i] > a[i-k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

from itertools import*
import math
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 1000003
from functools import reduce
import sys
sys.setrecursionlimit(10**7)
input=sys.stdin.readline

Max = mod-1
#二項係数とその逆元テーブルを作る前処理
fac = [0]*(Max)
finv = [0]*(Max)
inv = [0]*(Max)
fac[0]=fac[1]=1
finv[0]=finv[1]=1
inv[1]=1
for i in range(2,Max):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i]*(mod//i)%mod
        finv[i] = finv[i-1]*inv[i]%mod
#O(1)でmod計算した組合せ数を計算
def Comb(n,r):
    if n < r:
        return 0
    if n < 0 or r < 0 :
        return 0
    return fac[n]*(finv[r]*finv[n-r]%mod)%mod
def pow_mod(x,n):
    if n==0: return 1
    if n%2:return x*pow_mod(x,n-1)%mod
    a = pow_mod(x,n//2)
    return a*a%mod

Q = int(input())
def query(x,d,n):
    if x == 0:
        return 0
    if d == 0:
        return pow_mod(x,n)
    k = (x*inv[d])%mod
    if k+n-1 >= mod:
        return 0
    ans = fac[k+n-1]*finv[k-1]%mod
    ans *= pow(d,n)
    ans %= mod
    return ans
for i in range(Q):
    x,d,n = map(int,input().split())
    print(query(x,d,n))

### FIXED CODE ###

from itertools import*
import math
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 1000003
from functools import reduce
import sys
sys.setrecursionlimit(10**7)


Max = mod
#二項係数とその逆元テーブルを作る前処理
fac = [0]*(Max)
finv = [0]*(Max)
inv = [0]*(Max)
fac[0]=fac[1]=1
finv[0]=finv[1]=1
inv[1]=1
for i in range(2,Max):
        fac[i] = fac[i-1] * i % mod
        inv[i] = mod - inv[mod%i]*(mod//i)%mod
        finv[i] = finv[i-1]*inv[i]%mod
#O(1)でmod計算した組合せ数を計算
def Comb(n,r):
    if n < r:
        return 0
    if n < 0 or r < 0 :
        return 0
    return fac[n]*(finv[r]*finv[n-r]%mod)%mod


Q = int(input())
def query(x,d,n):
    if x == 0:
        return 0
    if d == 0:
        return pow(x,n,mod)
    k = (x*inv[d])%mod
    if k+n-1 >= mod:
        return 0
    ans = fac[k+n-1]*finv[k-1]%mod
    ans *= pow(d,n,mod)
    ans %= mod
    return ans
for i in range(Q):
    x,d,n = map(int,input().split())
    print(query(x,d,n))
### BUGGY CODE ###

import sys
input=lambda: sys.stdin.readline().rstrip()
import collections
D=collections.defaultdict(int)
r,c,k=map(int,input().split())
for _ in range(k):
	ri,ci,v=map(int,input().split())
	ri-=1
	ci-=1
	D[ri*10**5+ci]=v

DP=[[[0]*4 for _ in range(c+1)] for i in range(r+1)]
for i in range(r+1):
	for j in range(c+1):
		v=D[i*10**5+j]
		
		DP[i][j][0]=max(DP[i-1][j])
		if v!=0:
			DP[i][j][1]=max(DP[i-1][j])+v
		for ii in range(4):
		
			DP[i][j][ii]=max(DP[i][j][ii],DP[i][j-1][ii])
			if v!=0 and ii!=0:
				DP[i][j][ii]=max(DP[i][j][ii],DP[i][j-1][ii-1]+v)
		
ans=max(DP[r-1][c-1])
print(ans)



### FIXED CODE ###

import sys
input=lambda: sys.stdin.readline().rstrip()

r,c,k=map(int,input().split())
D=[[0]*c for _ in range(r)] 
for _ in range(k):
	ri,ci,v=map(int,input().split())
	ri-=1
	ci-=1
	D[ri][ci]=v

DP0=[[0]*(c+1) for i in range(r+1)]
DP1=[[0]*(c+1) for i in range(r+1)]
DP2=[[0]*(c+1) for i in range(r+1)]
DP3=[[0]*(c+1) for i in range(r+1)]
for i in range(r):
	for j in range(c):
		v=D[i][j]
		if v!=0:
			DP1[i][j]=max(DP0[i-1][j],DP1[i-1][j],DP2[i-1][j],DP3[i-1][j])+v

		DP0[i][j]=max(DP0[i][j],DP0[i-1][j],DP1[i-1][j],DP2[i-1][j],DP3[i-1][j])
		if v!=0:
			DP1[i][j]=max(DP1[i][j],DP0[i-1][j]+v,DP1[i-1][j]+v,DP2[i-1][j]+v,DP3[i-1][j]+v)
		DP0[i][j]=max(DP0[i][j],DP0[i][j-1])
		DP1[i][j]=max(DP1[i][j],DP1[i][j-1])
		DP2[i][j]=max(DP2[i][j],DP2[i][j-1])
		DP3[i][j]=max(DP3[i][j],DP3[i][j-1])
		if v!=0:
			DP1[i][j]=max(DP1[i][j],DP0[i][j-1]+v)
			DP2[i][j]=max(DP2[i][j],DP1[i][j-1]+v)
			DP3[i][j]=max(DP3[i][j],DP2[i][j-1]+v)
		
ans=max(DP0[r-1][c-1],DP1[r-1][c-1],DP2[r-1][c-1],DP3[r-1][c-1])
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

N,Q = map(int,input().split())
edges = [list(map(int,input().split())) for _ in range(N-1)]
PX = [list(map(int,input().split())) for _ in range(Q)]

c = [0]*N
res = [-1]*N
for p,x in PX:
    c[p-1] += x

def BFS(start,edges,N,c):
    roots=[[] for _ in range(N)]
    for a,b in edges:
        roots[a-1]+=[(b-1,c[b-1])]
    queue=[]
    queue.append(start)
    res[start] = c[start]
    while queue:
        label = queue.pop()
        for i,c in roots[label]:
            if res[i] == -1:
                res[i]= res[label]+c
                queue += [i]
    return res
print(*BFS(0,edges,N,c))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

N,Q = map(int,input().split())
edges = [list(map(int,input().split())) for _ in range(N-1)]
PX = [list(map(int,input().split())) for _ in range(Q)]

c = [0]*N
res = [-1]*N
for p,x in PX:
    c[p-1] += x

def BFS(start,edges,N,c):
    roots=[[] for _ in range(N)]
    for a,b in edges:
        roots[a-1]+=[(b-1,c[b-1])]
    queue=[]
    queue.append(start)
    res[start] = c[start]
    while queue:
        label = queue.pop()
        for i,c in roots[label]:
            if res[i] == -1:
                res[i]= res[label]+c
                queue += [i]
    return res
print(*BFS(0,edges,N,c))
### BUGGY CODE ###

import heapq
def SME(start,end):
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    D.add(idx)
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    i = L
    while i < N :
        if None in ANS[i:i+L] :
            while True:
                if ANS[i] :
                    i += 1
                    continue
                else : 
                    ANS[i] = min(Whole[i+1-L:i+1])
                    i += 1
                    break
        else :
            i += L
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
C = [i for i in range(N)]
D = set([])
parameter = 0.99
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

import math
N, Q = map(int, input().split())
queries = []
for i in range(Q):
    v, w = map(int, input().split())
    queries.append([v, w])

if N == 1:
    for v, w in queries:
        print(min(v, w))
else:
    for v, w in queries:
        if 1 in [v, w]:
            print(1)
        else:
            # v < w にする
            v, w = min(v,w), max(v, w)
            v -= 2
            w -= 2
            v_parents = [v]
            isReported = False
            while v > 0:
                v_parents.append(v // N - 1)
                v = v//N-1
            while w > 0:
                w = w // N-1
                if w in v_parents:
                    print(w+2)
                    isReported = True
                    break
            if not isReported:
                print(1)
        

### FIXED CODE ###

import math
N, Q = map(int, input().split())
queries = []
for i in range(Q):
    v, w = map(int, input().split())
    queries.append([v, w])

if N == 1:
    for v, w in queries:
        print(min(v, w))
else:
    for v, w in queries:
        if 1 in [v, w]:
            print(1)
        else:
            # v < w にする
            v, w = min(v,w), max(v, w)
            v -= 2
            w -= 2
            v_parents = [v]
            isReported = False
            while v > 0:
                v_parents.append(v // N - 1)
                v = v//N-1
            while w > 0:
                w = w // N-1
                if w in v_parents:
                    print(w+2)
                    isReported = True
                    break
            if not isReported:
                print(1)
### BUGGY CODE ###

N,K,Q = map(int,input().split())
A = []
p = []
for i in range(Q):
    A.append(int((input())))
    
for i in range(N):
    p.append(A.count(i+1))

for i in range(N):
    P = K - Q + p[i]
    if P > 0:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

N,K,Q = map(int,input().split())
A = [int(input()) for i in range(Q)]
p = [0] * N 
for i in A:
    p[i-1] += 1    

for i in range(N):
    P = K - Q + p[i]
    if P > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

K=int(input())

queue = list(range(1,10))

for i in range(K):
  lunlun = queue.pop(0)
  #print(lunlun)
  last = lunlun%10
  if last!=0:
    queue.append(10*lunlun+last-1)
  queue.append(10*lunlun+last)
  if last!=9:
    queue.append(10*lunlun+last+1)

print(lunlun)

### FIXED CODE ###

K=int(input())
from collections import deque

#queue = list(range(1,10))
queue = deque(list(range(1,10)))

for i in range(K):
  lunlun = queue.popleft()
  #print(lunlun)
  last = lunlun%10
  if last!=0:
    queue.append(10*lunlun+last-1)
  queue.append(10*lunlun+last)
  if last!=9:
    queue.append(10*lunlun+last+1)

print(lunlun)
### BUGGY CODE ###

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

# abc123_d
import itertools
import math

# input
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 = range(1000)
# B = range(1000)
# C = range(1000)
# getans
arr = itertools.product(A, B)
arr = map(sum, arr)
arr = sorted(arr, reverse=True)[:K]
arr = itertools.product(arr, C)
arr = map(sum, arr)
arr = sorted(arr, reverse=True)[:K]
# output
ans = '\n'.join(map(str, arr))
print(ans)



### FIXED CODE ###

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

# abc123_d
import itertools
import math

# input
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 = range(1000)
# B = range(1000)
# C = range(1000)
# getans
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
arr = []
for i in range(X):
    for j in range(Y):
        for k in range(Z):
            if (i+1)*(j+1)*(k+1) > K:
                break
            arr.append(A[i]+B[j]+C[k])
#print(len(arr))
arr.sort(reverse=True)
# output
ans = '\n'.join(map(str, arr[:K]))
print(ans)
### BUGGY CODE ###

N = int(input())
B = [10 ** 9 + 1]
for i in range(N):
  A = int(input())
  flag = True
  for j in range(len(B)):
    if A > B[j]:
      B[j] = A
      flag = False
      break
  if flag:
    B.append(A)
print(len(B) - 1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect

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

Color = []
for a in A:
  idx = bisect.bisect_right(Color,a)
  if idx == len(Color):
    Color.append(a)
  else:
    Color[idx] = a
  #Color.sort()
  #print(Color)
print(len(Color))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N=input()
A=[[]]+[ map(int, raw_input().split()) for _ in range(N)]

Now=[0 for _ in range(N+1)]

day=0
goal_person=0

while True:
	flag=False
	Visit=[ None for _ in range(N+1) ]
	for me in range(1,N+1):
		now=Now[me]
		if now<N-1:	#現在値がN-1になっていたら、もうアガリ
			opponent=A[me][now]

			opponentnow=Now[opponent]
			opp_of_opp=A[opponent][opponentnow]

			if me==opp_of_opp and Visit[me] is None and Visit[opponent] is None:
				flag=True	#前進フラグ　1回前よりも状態が進めばTrueになる
				Now[me]+=1
				Now[opponent]+=1
				Visit[me]=1
				Visit[opponent]=1
				if Now[me]==N-1:		goal_person+=1
				if Now[opponent]==N-1:	goal_person+=1

	else:
			if not flag:
				print -1
				quit()
	day+=1

	if goal_person==N:
		print day
		quit()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
from collections import defaultdict,deque

N=input()
A=[[]]+[ map(int, sys.stdin.readline().split()) for _ in range(N) ]
C=defaultdict(lambda: 0)

Now=[ 0 for _ in range(N+1)]
game=set()
next_game=set()

for i in range(1,N+1):
	a=i
	b=A[i][0]
	if a>b: a,b=b,a
	game.add((a,b))

day=0

while game:
	next_game=set()
	Visit=defaultdict(lambda: None) 

	for x,y in game:
		now_x=Now[x]
		now_y=Now[y]

		xopp=A[x][now_x]
		yopp=A[y][now_y]

		if (x,y)==(yopp,xopp) and Visit[x] is None and Visit[y] is None:
			Visit[x]=1
			Visit[y]=1
			if now_x<N-2:
				now_x+=1
				Now[x]=now_x
				x_nextopp=A[x][now_x]
				if x_nextopp<x: x,x_nextopp=x_nextopp,x
				next_game.add((x,x_nextopp))

			if now_y<N-2:
				now_y+=1
				Now[y]=now_y
				y_nextopp=A[y][now_y]
				if y_nextopp<y: y,y_nextopp=y_nextopp,y
				next_game.add((y,y_nextopp))

	game=next_game
	day+=1


for i in range(1,N+1):
	if Now[i] != N-2:
		print -1
		quit()
else:
	print day