Harryxun/stf_run huggingface dataset:
import sys
input = sys.stdin.readline

X,Y,Z,K = (int(i) for i in input().split())
ax = [int(i) for i in input().split()]
by = [int(i) for i in input().split()]
cz = [int(i) for i in input().split()]
ans = [0] * max(3000,X*Y*Z)
cnt = 0
for i in ax:
  for j in by:
    for k in cz:
      ans[cnt] = i + j + k
      cnt += 1
ans.sort(reverse=True)
for i in range(K):
  print(ans[i])

### FIXED CODE ###

import heapq

X,Y,Z,K = (int(i) for i in 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()]
q = []
S = set()
a.sort()
b.sort()
c.sort()

heapq.heappush(q,(a[0]+b[0]+c[0],0,0,0))

for i in range(K):
  p,i,j,k=heapq.heappop(q)
  print(-p)
  if i+1 < X and not((i+1,j,k) in S):
    S.add((i+1,j,k))
    heapq.heappush(q,(a[i+1]+b[j]+c[k],i+1,j,k))
  if j+1 < Y and not((i,j+1,k) in S):
    S.add((i,j+1,k))
    heapq.heappush(q,(a[i]+b[j+1]+c[k],i,j+1,k))
  if k+1 < Z and not((i,j,k+1) in S):
    S.add((i,j,k+1))
    heapq.heappush(q,(a[i]+b[j]+c[k+1],i,j,k+1))
h,w=map(int,raw_input().split())
n=input()
g=map(int,raw_input().split())
l=[]
for i in range(n):
    l=l+[i+1]*g[i]
ans=[]
for i in range(h):
    l1=[]
    for j in range(w):
        l1.append(l[h*i+j])
    if i%2==0:
        ans=ans+[l1]
    elif i%2==1:
        l1.reverse()
        ans=ans+[l1]
for i in ans:
    for j in i:
        print j,
    print 


### FIXED CODE ###

h,w=map(int,raw_input().split())
n=input()
g=map(int,raw_input().split())
l=[]
for i in range(n):
    l=l+[i+1]*g[i]
for i in range(h):
    l1=l[i*w:(i+1)*w]
    if i%2==1:
        l1.reverse()
    for j in l1:
        print j,
    print
a,b,c=map(int,input().split())
ans=0
flag=0
for i in range(b):
  ans+=a
  if(ans%b==c):
    flag=1

if(flag=1):
  print("YES")
else:
  print("NO")

### FIXED CODE ###

a,b,c=map(int,input().split())
ans=0
flag=0
for i in range(b):
  ans+=a
  if(ans%b==c):
    flag=1

if(flag==1):
  print("YES")
else:
  print("NO")
a=int(input())
b=int(input())
if a=1:
  if b=2:
    print(3)
  else:
    print(2)
elif a=2:
  if b=1:
    print(3)
  else:
    print(1)
else:
  if a=1:
    print(2)
  else:
    print(1)

### FIXED CODE ###

a=int(input())
b=int(input())
if a==1:
  if b==2:
    print(3)
  else:
    print(2)
elif a==2:
  if b==1:
    print(3)
  else:
    print(1)
else:
  if b==1:
    print(2)
  else:
    print(1)
a, b = map(int, input().split())
s = a//(2*b+1)
if a%(2*b+1) == 0:
  print(s)
else:
  print(s+1)

### FIXED CODE ###

a = input()
b = 3*(int(a)**2)
print(b)
import math
import collections


def modinv(n, p):
    """
    逆元のmod pを求める
    """
    if n >= p:
        raise ValueError('p must be larger than n')
    return pow(n, p-2, p)


def prime_sieve(n):
    """
    n以下の素数を昇順に列挙する
    エラトステネスの篩 計算量O(Nlog(log(N)))
    """
    is_prime = [True for i in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n+1):
        if is_prime[i]:
            for j in range(i+i, n+1, i):
                is_prime[j] = False
    return [i for i in range(2, n+1) if is_prime[i]]


def prime_factorization(it):
    """
    数値の素因数分解をリストで返すイテレータ
    エラトステネスの篩を応用する 計算量O(A+Nlog(log(N)))
    """
    n = max(it)
    factor = [1 for i in range(n+1)]
    factor[0] = 0
    factor[1] = 1
    for i in range(2, n+1):
        if factor[i] == 1:
            for j in range(i, n+1, i):
                factor[j] = i
    for a in it:
        if a < 2:
            yield list()
        else:
            prime_factors = list()
            while a != factor[a]:
                prime_factors.append(factor[a])
                a //= factor[a]
            prime_factors.append(factor[a])
            yield list(sorted(prime_factors))


def lcm(x, p=-1):
    """
    配列xに対する最小公倍数 LCM(x_1, x_2, ..., x_n) を求める
    p > 0のときはLCM mod pを返す
    """
    max_prime_counts = dict()
    for prime in prime_sieve(max(x)):
        max_prime_counts[prime] = 0
    pfs = prime_factorization(x)
    for pf in pfs:
        prime_count = collections.Counter(pf)
        for prime in prime_count.keys():
            max_prime_counts[prime] = max(max_prime_counts[prime], prime_count[prime])
    lcm_value = 1
    for prime, factor in max_prime_counts.items():
        if p > 0:
            lcm_value *= pow(prime, factor, p)
            lcm_value %= p
        else:
            lcm_value *= pow(prime, factor)
    return lcm_value


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def solve(N, A, MOD=1000000007):
    bsum = 0
    for i in range(N):
        bsum += modinv(A[i], MOD)
        bsum %= MOD
    bsum *= lcm(A, p=MOD)
    bsum %= MOD
    return bsum


if __name__ == '__main__':
    inputs = read()
    print("%d" % solve(*inputs))

### FIXED CODE ###

def read():
    N, M = list(map(int, input().strip().split()))
    return N, M

def solve(N, M):
    return 'Yes' if N == M else 'No'


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))
n,m=map(int,input().split())
s=input()
t=input()

def gcd(x,y):
  r=x%y
  return gcd(y,r) if r else y
#最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

L=lcm(n,m)
if s[0]==t[0]:
  X=[""]*L+1
else:
  print(-1)
  exit()
for i in range(1,n):
  X[int(i*L/n)+1]=s[i]
for i in range(1,m):
  if X[int(i*L/m)+1] !="":
    if X[int(i*L/m)+1] !=t[i]:
      print(-1)
      exit()
print(L)

### FIXED CODE ###

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

def gcd(x,y):
  r=x%y
  return gcd(y,r) if r else y
#最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

L=lcm(n,m)
g=gcd(n,m)
for i in range(g):
  if s[int(i*n/g)]!=t[int(i*m/g)]:
    print(-1)
    exit()
print(L)
N = int(input())
 
for i in range(1,10):
  for j in range(1,10):
    if i*j=N:
      break
  if i*j=N:
    print("Yes")
      break
  elif i==9 and i*j!=N:
    print("No")

### FIXED CODE ###

N = int(input())

for i in range(1, 10):
    for j in range(1, 10):
        if i * j == N:
            break
    if i * j == N:
        print("Yes")
        break
    elif i == 9 and i * j != N:
        print("No")
import math

MOD = math.pow(10, 9) + 7


def check(h, w, a, b):
    c, d = h - a, w - b
    start2p = math.factorial(a + b) // math.factorial(a) // math.factorial(b)
    p2end = math.factorial(c + b) // math.factorial(c) // math.factorial(d)
    return (start2p * p2end) % MOD


def main():
    h, w, a, b = map(int, input.split())
    print(check(h, w, a, b))


if __name__ == '__main__':
    main()


### FIXED CODE ###

MOD = 1000000007


def mod_pow(a, n, mod):
    """
    二分累乗法による a^n (mod m)の実装

    :param a: 累乗の底
    :param n: 累乗の指数
    :param mod: 法
    :return: a^n (mod m)
    """

    result = 1
    a_n = a
    while n > 0:
        if n & 1:
            result = result * a_n % mod
        a_n = a_n * a_n % mod
        n >>= 1
    return result


def mod_inverse(a, mod):
    """
    フェルマーの小定理による a^-1 ≡ 1 (mod m)の実装
    aの逆元を計算する

    a^-1 ≡ 1 (mod m)
    a * a^-2 ≡ 1 (mod m)
    a^-2 ≡ a^-1 (mod m)

    :param a: 逆元を計算したい数
    :param mod: 法
    :return: a^-1 ≡ 1 (mod m)
    """

    return mod_pow(a=a, n=mod - 2, mod=mod)


class ModCombination:
    """
    nCk (mod m)を扱うクラス
    """

    def __init__(self, mod, n_max):
        """
        イニシャライザ
        予め 1~nの階乗と階乗の逆元を計算しておく

        :param mod: 法
        :param n_max: nの最大値(100,000で約1秒)
        """
        self.mod = mod
        self.n_max = n_max
        self.facts = [1, 1]
        self.inverses = [None, 1]
        self.fact_inverses = [1, 1]

        for i in range(2, self.n_max + 1):
            self.facts.append(self.facts[i - 1] * i % self.mod)
            # self.inverses.append(mod_inverse(i, self.mod))
            self.inverses.append(self.mod - self.inverses[self.mod % i] * (
                        self.mod // i) % self.mod)
            self.fact_inverses.append(
                self.fact_inverses[i - 1] * self.inverses[i] % self.mod
            )

    def mod_combination(self, n, k):
        """
        nCk (mod m)を計算する

        :param n: n
        :param k: k
        :return: nCk (mod m)
        """
        if not 0 < k < n:
            raise ValueError

        denominator = \
            self.fact_inverses[k] * self.fact_inverses[n - k] % self.mod
        return self.facts[n] * denominator % self.mod


def calc_routes(combination, dx, dy):
    if dx == 0 or dy == 0:
        return 1
    else:
        return combination.mod_combination(dx + dy, dx)


def check(h, w, a, b):
    combination = ModCombination(mod=MOD, n_max=h + w)
    p = (b + 1, h - a)
    all_routes = 0
    while p[0] <= w and p[1] > 0:
        d1 = (p[0] - 1, p[1] - 1)
        d2 = (w - p[0], h - p[1])
        r1 = calc_routes(combination, *d1)
        r2 = calc_routes(combination, *d2)
        routes = r1 * r2 % MOD
        all_routes += routes
        all_routes %= MOD
        p = (p[0] + 1, p[1] - 1)
    return all_routes


def main():
    h, w, a, b = map(int, input().split())
    print(check(h, w, a, b))


if __name__ == '__main__':
    main()
X, Y = map(int, input().s .- 0   			111						/plit())

if (Y%2 == 1):
  print("No")
elif (Y > (X*4)):
  print("No")
else:
  print("Yes")
  

### FIXED CODE ###

X, Y = map(int, input().split())

if (Y%2 == 1):
  print("No")
elif (Y > (X*4)):
  print("No")
else:
  yes = False
  for i in range(0,X+1):
    fNum = i
    tNum = X-i
    if ((fNum*4)+(tNum*2)==Y):
      print("Yes")
      yes = True
  if not (yes):
    print("No")
import sys
import math

lines = str(sys.stdin.read()).strip().split("\n")

for line in lines:
    line = int(line)
    pList = []
    sList = list(reversed(list(range(3, line + 1))[::2]))
    while sList[-1] < (int(math.ceil(math.sqrt(line))) + 1):
        pList.append(sList.pop())
        for p in pList:
            sList = list(filter(lambda i: i % p != 0, sList))
    pList.extend(sList)
    pList.append(2)
    print(len(pList))

### FIXED CODE ###

import sys
import math


LIMIT = 1000000
p = 2
pList = [True] * (LIMIT + 1)


while p ** 2 <= LIMIT:
    if(pList[p]):
        for i in range(p * 2, LIMIT + 1 , p):
            pList[i] = False
    p += 1

# print(pList)


lines = str(sys.stdin.read()).strip().split("\n")

for line in lines:
    line = int(line)
    count = 0
    for i in range(2, line + 1):
        if pList[i]:
            count += 1
    print(count)
n = [int(input()) for i in range(3)]

if n[0] ==1:
    print('Hello World')

else:
    print(n[1]+n[2])

### FIXED CODE ###

n = int(input())

if n ==1:
    print('Hello World')

else:
    ab = [int(input()) for i in range(2)]
    print(ab[0]+ab[1])
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

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

a = sorted(a)
ads = [0]*(2*10**5)

ans = 0
dups = []
for ai in a:
    ds = make_divisors(ai)
    ok = True
    if ads[ai]:
        if ai not in dups:
            dups.append(ai)
        continue
    for d in ds:
        if ads[d]:
            ok = False
            break
    if ok:
        ads[ai] = 1
        ans += 1

print(ans - len(dups))

### FIXED CODE ###

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

a = sorted(a)

dp  = [0] * (a[-1]+1)

for ai in a:
    if dp[ai]:
        dp[ai] += 1
        continue

    i = 1
    while True:
        if ai*i >= len(dp):
            break
        dp[ai*i] += 1
        i += 1

ans = 0
for ai in a:
    if dp[ai] == 1:
        ans += 1

print(ans)
import math

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

A, B, C, D = (int(x) for x in input().split())

Cu = B//C
Cd = -(-A//C)
Du = B//D
Dd = -(-A//D)

LCMu = B//(lcm(C,D))
LCMd = -(-A//lcm(C,D))

C_num = Cu - Cd + 1
D_num = Du - Dd + 1
LCM_num = LCMu - LCMd + 1

C_D_num = C_num + D_num - LCM_num
A_B_num = B - A  + 1

ans = A_B_num - C_D_num
print(ans)

### FIXED CODE ###

import fractions as math

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

A, B, C, D = (int(x) for x in input().split())

Cu = B//C       #Cの上限
Cd = -(-A//C)   #Cの下限
Du = B//D       #Dの上限
Dd = -(-A//D)   #Dの下限

#Least common multiple
LCMu = B//(lcm(C,D))
LCMd = -(-A//lcm(C,D))


C_num = Cu - Cd + 1
D_num = Du - Dd + 1
LCM_num = LCMu - LCMd + 1

C_D_num = C_num + D_num - LCM_num
A_B_num = B - A  + 1

ans = A_B_num - C_D_num
print(ans)
l=list(map(input().split()))
print(l.index(0)+1)

### FIXED CODE ###

l=list(map(int ,input().split()))
print(l.index(0)+1)
def modinv(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % (10**9+7)

MOD=10**9+7
am=[2]
for i in range(50):
    am.append((am[-1]**2)%MOD)
fr=[1]
for i in range(1,2*(10**5)):
    fr.append((fr[-1]*i)%MOD)

n,a,b=map(int,input().split())
a=min(a,n-a)
b=min(b,n-b)
s=bin(n)[2::][::-1]

ans=1
for i in range(len(s)):
    if s[i]=="1":
        ans*=am[i]
        ans%=MOD

for x in [a,b]:
    tmp=1
    for i in range(n-x+1,n+1):
        tmp=(tmp*i)%MOD
    tmp*=modinv(fr[x],MOD)
    ans=(ans-tmp)%MOD

ans=(ans-1)%MOD
print(ans)

### FIXED CODE ###

def modinv(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % (10**9+7)

MOD=10**9+7
am=[2]
for i in range(60):
    am.append((am[-1]**2)%MOD)

fr=[1]
for i in range(1,2*(10**5)+10):
    fr.append((fr[-1]*i)%MOD)

n,a,b=map(int,input().split())
a=min(a,n-a)
b=min(b,n-b)
s=bin(n)[2::][::-1]

ans=1
for i in range(len(s)):
    if s[i]=="1":
        ans*=am[i]
        ans%=MOD

for x in [a,b]:
    tmp=1
    for i in range(n-x+1,n+1):
        tmp=(tmp*i)%MOD
    tmp*=modinv(fr[x],MOD)
    ans=(ans-tmp)%MOD

ans=(ans-1)%MOD
print(ans)
nk = [int(i) for i in input().split()]
n = nk[0]
k = nk[1]
array = []
count = []
for i in range(n):
    num = input().split()
    a = num[0]
    b = int(num[1])
    k -= b
    array.append(a)
    if k <= 0:
        break
    else:
        array.pop()
print(array[0])
        

### FIXED CODE ###

arnum = input().split()
a = int(arnum[0])
b = int(arnum[1])
c = int(arnum[2])
if c >= a and c <= b:
    print("Yes")
else:
    print("No")
import itertools

N = int(input())
S = []

for i in range(N):
    s = int(input())
    S.append(s)

a = sum(S)

if a % 10 != 0:
    print(a)
else:
    T = [s for s in S if s%10!=0]
    if len(T) == 0:
       ans = 0
    else:
        ans = A-min(T)

print(ans)

### FIXED CODE ###

N = int(input())
S = []

for i in range(N):
    s = int(input())
    S.append(s)

a = sum(S)
ans = 0

if a % 10 != 0:
    ans = a
else:
    T = [s for s in S if s%10!=0]
    if len(T) == 0:
       ans = 0
    else:
        ans = a-min(T)

print(ans)
# ABC071-C　
N = int(input())
A_list = list(map(int, input().split()))

A_set = set(A_list)
A_set = sorted(A_set, reverse=True)

side_list = [0, 0]

for i in range(len(A_set)):   # 大きい順に取っていき，リストで個数を確認する
    if len(side_list) >= 4:
        break
    count = A_list.count(A_set[i])    # リストの個数を確認
    if count == 2 or count == 3:
        side_list.append(A_set[i])
    if count >= 4:
        side_list.append(A_set[i])
        side_list.append(A_set[i])
        
side_list.sort(reverse = True)
print(side_list[0] * side_list[1])

### FIXED CODE ###

# ABC071-A
x, a, b = map(int, input().split())
if abs(x-a) > abs(x-b):
    print('B')
else:
    print('A')
import numpy as np
IN() = lambda:map(int, input().split())

n,k = IN()
dp = np.full(n*1000+1, k+1, dtype=int)
dp[0] = 0

for _ in range(n):
  w,v = IN()
  dp[v:] = np.minimum(dp[:-v]+w, dp[v:])

print(np.max(np.where(dp <= k)))


### FIXED CODE ###

import numpy as np
IN = lambda:map(int, input().split())

n,k = IN()
dp = np.full(n*1000+1, k+1, dtype=int)
dp[0] = 0

for _ in range(n):
  w,v = IN()
  dp[v:] = np.minimum(dp[:-v]+w, dp[v:])

print(np.max(np.where(dp <= k)))
from fractions import gcd
N = int(input())
A = [int(i) for i in input().split()]
lcm = A[0]
MOD = 10**9 + 7
for a in A:
    lcm = (lcm // gcd(lcm,a) * a)
res = 0
for a in A:
    res += lcm /a
print(res % MOD)


### FIXED CODE ###

from fractions import gcd
N = int(input())
A = [int(i) for i in input().split()]
lcm = A[0]
MOD = 10**9 + 7
for a in A:
    lcm = (lcm // gcd(lcm,a) * a)
res = 0
for a in A:
    res += lcm //a
print(res % MOD)
H, W, m = map(int, input().split())
hs = [0] * H
ws = [0] * W
fs = [[0]*W for i in range(H)]
ps = []
for i in range(m):
    hi,wi  = map(int, input().split())
    hs[hi-1] += 1
    ws[wi-1] += 1
    fs[hi-1][wi-1] += 1
    ps.append((hi-1,wi-1))
mx = 0
Hs = [(h,i) for i,h in enumerate(hs)]
Ws = [(w,i) for i,w in enumerate(ws)]
Hs.sort(reverse=True)
Ws.sort(reverse=True)
cnt = 0
hmx = Hs[0][0]
wmx = Ws[0][0]
# for r in fs:
#     print(*r)
mx = 0
for nh, ih in Hs:
    for nw, iw in Ws:
        if nh < hmx and nw < wmx: continue
        if fs[ih][iw] == 0:
            mx = max(mx, nh+nw)
        if fs[ih][iw] == 1:
            mx = max(mx, nh+nw-1)
        cnt += 1
        if cnt >= m:
            print(mx)
            exit()
print(mx)

### FIXED CODE ###

H, W, m = map(int, input().split())
hs = [0] * (H+1)
ws = [0] * (W+1)
from collections import defaultdict
d = defaultdict(bool)
N = 10**6
for i in range(m):
    hi,wi = map(int, input().split())
    hi -= 1
    wi -= 1
    hs[hi] += 1
    ws[wi] += 1
    d[hi*10**6+wi] = True

hmx = max(hs)
hset = set()
for i,h in enumerate(hs):
    if h == hmx:
        hset.add(i)
wmx = max(ws)
wset = set()
for j, w in enumerate(ws):
    if w == wmx:
        wset.add(j)

flg = False
ans = 0
cnt = 0
for i in hset:
    for j in wset:
        ans = max(ans, hmx+wmx-d[i*N+j]) 
        if cnt >= m:
            flg = True
            break
        cnt += 1
    if flg:break

print(ans)
import sys
from scipy.special import comb

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

A = [0]*M

for i in range(M):
    A[i] = int(input())

A.append(N+1)

total_combo = 1
NOW = 0
for a in A:
    if NOW == a:
        print(0)
        sys.exit()
    L = a-1-NOW
    combo = 0
    for i in range(L//2 +1):
        j = L - 2*i
        combo += comb(j+1, i, exact=True)
    total_combo *= combo
    NOW = a + 1
    
print(total_combo)


### FIXED CODE ###

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

T = N
DIFFMIN = 100000
lidx = 0
ridx = N-1

while(True):
    T = (lidx + ridx)//2
    if T == N-1:
        T -= 1

    L = sum(W[:T+1])
    R = sum(W[T+1:])
    #print(T, L, R)
    if ridx - lidx <= 1:
        DIFFMIN = min(abs(L-R), abs(sum(W[:T+2])-sum(W[T+2:])))
        break
    if L<R:
        lidx = T
    elif L>R:
        ridx = T
    else:
        DIFFMIN = abs(L-R)
        break
    DIFFMIN = abs(L-R)
    
print(DIFFMIN)
a, b = map(int, input().split())
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
n = gcd(a, b)

def cd(num):
    k = []
    if num%2 == 0:
        if is_prime(2):
            k.append(i) 
    for i in range(1,num+1,2):
        if num%i == 0:
            if is_prime(i):
                k.append(i) 
    return k

def is_prime(num):
    for i in range(2, num):
        if num % i == 0:
            return False
    return True


gc = gcd(a,b)
c = cd(gc)

print(len(c))

### FIXED CODE ###

def f(n):
    res = set()
    for i in range(2, int(n ** 0.5)):
        if n % i: continue
        while not n % i: n //= i
        res.add(i)
    return res | {n}
 
a, b = map(int,input().split())
print(len(f(a) & f(b) | {1}))
def dfs(v):
  d=sorted(map(dfs,t[v]))
  l=len(d)
  return max([0]+[l-i+d for i,d in e(d)])
e=enumerate
n,*a=map(int,open(0))
t=[[]for _ in[0]+a]
for i,v in e(a,1):t[v-1]+=i,
print(dfs(0))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
e=enumerate
def dfs(v):
  d=sorted(map(dfs,t[v]))
  l=len(d)
  return max([0]+[l-i+d for i,d in e(d)])
n,*a=map(int,open(0))
t=[[]for _ in[0]+a]
for i,v in e(a,1):t[v-1]+=i,
print(dfs(0))
N, Y = map(int, input().split())
x = -1
y = -1
z = -1
for i in range(n+1):
    for j in range(n+1-i):
        k = n-i-j
        if 10000*i + 5000*j + 1000*k == y:
            x = i
            y = j
            z = k
print(x, y, z)


### FIXED CODE ###

N, Y = map(int, input().split())
x = -1
y = -1
z = -1
for i in range(N+1):
    for j in range(N+1-i):
        k = N-i-j
        if 10000*i + 5000*j + 1000*k == Y:
            x = i
            y = j
            z = k
print(x, y, z)
x = input()
n = (int)x
sum_of_digits = sum(map(int, x))
check = n % sum_of_digits
print('No' if check else 'Yes')



### FIXED CODE ###

x = input()
sum_of_digits = sum(map(int, x))
check = int(x) % sum_of_digits
print('No' if check else 'Yes')
N,M=map(int, input().split())

A = list(map(int, input().split()))
S = [list(map(int,input().split())) for i in range(M)]

A.sort()
S.sort(key=lambda x: x[1], reverse=True)

X = [0]*(len(A))
idx = 0

for i in range(M):
    for _ in range(S[i][0]):
        if idx <= len(A):
            X[idx]=S[i][1]
            idx += 1

for i in range(idx):
    A[i] = max(A[i], X[i])

print(sum(A))

### FIXED CODE ###

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

A = list(map(int, input().split()))
S = [list(map(int,input().split())) for i in range(M)]

A.sort()
S.sort(key=lambda x: x[1], reverse=True)

idx = 0

for i in range(M):
    for j in range(idx, min(N, idx + S[i][0])):
        if A[j] < S[i][1]:
            A[j] = S[i][1]
            idx += 1
        else:
            break

print(sum(A))
N, A, B = map(int(input().split()))
if A*N > B:
  print(B)
else:
  print(A*N)

### FIXED CODE ###

N, A, B = map(int, input().split())
print(min(A*N,B))
from collections import Counter
N = int(input())
A = list(map(int, input().split()))

evens = Counter(A[::2])
odds = Counter(A[1::2])
evens[0] = 0 # 番兵
odds[0] = 0

e1, e2 = evens.most_common(2)
o1, o2 = odds.most_common(2)

if e1[0] != o1[0]:
  print(N - (e1[1] + o1[1]))
else:
  print(N - max(e1[1] + o2[1], e2[1] + o1[1]))

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))

evens = Counter(A[::2])
odds = Counter(A[1::2])
evens[0] = 0 # 番兵
odds[0] = 0

e1, e2 = evens.most_common(2)
o1, o2 = odds.most_common(2)

if e1[0] != o1[0]:
  print(N - (e1[1] + o1[1]))
else:
  print(N - max(e1[1] + o2[1], e2[1] + o1[1]))
s=input()
k=int(input())
m=0
j=0
if len(set(list(s)))==1:print((len(s)*k)//2);exit()
for i in range(len(s)):
 if len(s)<=j+1:
  a=m*k
  if s[0]==s[-1]==s[len(s)//3]:print(a+k-1)
  else:print(a)
 if s[j]==s[j+1]:
  m+=1
  j+=1
 j+=1


### FIXED CODE ###

s = input()
k = int(input())
m = 0
n = 0
j = 0
for i in range(len(s)):
    if s.count(s[0]) == len(s):
        print(len(s) * k // 2)
        exit()
    if len(s) <= j + 1:
        if s[0] == s[-1] == s[-2]== s[-3]== s[-4]== s[-5]== s[len(s)//3] \
                and s[0] == s[1] == s[2]== s[3]== s[4]== s[5]:
            n+=1
        break
    if s[j] == s[j + 1]:
        if j == len(s) - 1:
            n += 1
        else:
            m += 1
        j += 1
    j += 1
print(m * k + n*(k-1))
import math
n=int(input())
a=[int(input()) for i in range(5)]
b=0
for i in range(5):
  b=max(math.ceil(n//a[i]))
print(5+b-1)


### FIXED CODE ###

import math
n=int(input())
a=[int(input()) for i in range(5)]
b=0
for i in range(5):
  b=max(math.ceil(n/a[i]),b)
print(5+b-1)