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

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

import math

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()
b.sort()
c.sort()

cnum = []

takadaka = math.ceil(k ** 0.75)

for i in range(min(takadaka,x)):
    for j in range(min(takadaka,y)):
        for l in range(min(takadaka,z)):
            cnum.append(a[i] + b[j] + c[l])

cnum.sort()
cnum.reverse()

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


### FIXED CODE ###

# -*- coding: utf-8 -*-
x,y,z,k = map(int,input().split())
a,b,c = [],[],[]
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

ab = []

for i in range(x):
    for j in range(y):
        ab.append(a[i] + b[j])

ab.sort()

abc = []

for i in range(min(len(ab),k)):
    for j in range(min(z,k)):
        abc.append(ab[-(i+1)] + c[j])

abc.sort()

for i in range(k):
    print(abc[-(i+1)])
### BUGGY CODE ###

n=int(input())
t=[int(input()) for _ in range(n)]  

mt=t[0]
mx=t[0]
for i in t:
  for j in range(min(i,mx),0,-1):
    if i%j==0 and mx%j==0:
      mt=j
      break
  mx=i*mx//mt

print(mx)  

### FIXED CODE ###

import fractions
from functools import reduce

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

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

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

n=int(input())
print(lcm_list([int(input()) for _ in range(n)]))
### BUGGY CODE ###

import math

def f(x, y):
    return math.factorial(x) // (math.factorial(x - y) * math.factorial(y))

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

sum = 0
for i in range(n//2):
    x = f(n, i+1)
    sum += x
ans = sum*2+1

if n%2 == 0:
    ans = sum*2+1-x
ans = ans - f(n, a) - f(n, b)
ans %= ((10**9)+7)
print(ans)

### FIXED CODE ###

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

MOD = 10**9 + 7
x = 1
y = 1
ans = pow(2, n, MOD) - 1

for i in range(1, b+1):
    x = x * i % MOD
    y = y * (n-i+1) % MOD
    if i == a or i == b:
        ans -= y * pow(x, MOD-2, MOD)

print(ans%MOD)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

n,W=LI()
w=[]
v=[]
for _ in range(n):
  a,b=LI()
  w.append(a)
  v.append(b)

dp=[[-1 for _ in range(W+1)] for __ in range(n+1)]

def rec(i,j):
  if dp[i][j]>=0:
    return dp[i][j]

  if i==n:
    ret=0
  elif j<w[i]:
    ret=rec(i+1,j)
  else:
    ret=max(rec(i+1,j),rec(i+1,j-w[i])+v[i])
  dp[i][j]=ret
  return ret

def main():
  return rec(0,W)

# main()
print(main())


### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,W=LI()
  w=[]
  v=[]
  dp=[[0 for _ in range(W+1)] for __ in range(n+1)]
  for _ in range(n):
    a,b=LI()
    w.append(a)
    v.append(b)

  for i in range(n)[::-1]:
    for j in range(W+1):

      if j<w[i]:
        dp[i][j]=dp[i+1][j]

      else:
        dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])

  return dp[0][W]

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

S = input()
Q = int(input())
t = []
f = []
c = []
for i in range(Q):
    in_ = list(input().split())
    if in_[0] == "1":
        t.append(1)
        f.append(0)
        c.append(0)
    else:
        t.append(2)
        f.append(int(in_[1]))
        c.append(in_[2])
        
acc = [0 for _ in range(Q)]
if t[-1] == 1:  acc[-1] = 1
for i in reversed(range(Q - 1)):
    if t[i] == 1:
        acc[i] = acc[i + 1] + 1
    else:
        acc[i] = acc[i + 1]
        
if acc[0] % 2 == 0:
    ans = S
else:
    ans = S[::-1]
    
for i in range(Q):
    if t[i] == 2:
        if (f[i] + acc[i]) % 2 == 1:
            ans = c[i] + ans
        else:
            ans = ans + c[i]
print(ans)

### FIXED CODE ###

from collections import deque
S = input()
Q = int(input())
t = []
f = []
c = []
for i in range(Q):
    in_ = list(input().split())
    if in_[0] == "1":
        t.append(1)
        f.append(0)
        c.append(0)
    else:
        t.append(2)
        f.append(int(in_[1]))
        c.append(in_[2])
acc = [0 for _ in range(Q)]
if t[-1] == 1:  acc[-1] = 1
for i in reversed(range(Q - 1)):
    if t[i] == 1:
        acc[i] = acc[i + 1] + 1
    else:
        acc[i] = acc[i + 1]
        
if acc[0] % 2 == 0:
    ans = deque(S)
else:
    ans = deque(S[::-1])
    
for i in range(Q):
    if t[i] == 2:
        if (f[i] + acc[i]) % 2 == 1:
            ans.appendleft(c[i])
        else:
            ans.append(c[i])
print("".join(ans))
### BUGGY CODE ###

import queue
N,M=map(int,input().split())
G=[dict() for i in range(N)]
for i in range(M):
    u,v,s=map(int,input().split())
    G[u-1][v-1]=s
    G[v-1][u-1]=s
H=[[] for i in range(N)]
reached=[0 for i in range(N)]
q=queue.Queue()
q.put(0)
H[0].append((0,1))
while(not(q.empty())):
    r=q.get()
    reached[r]=1
    for p in G[r]:
        if reached[p]==0:
            q.put(p)
            for s in H[r]:
                H[p].append((G[r][p]-s[0],-s[1]))
flag=0
x=-1
for i in range(N):
    if len(H[i])>=2:
        X=set()
        Y=set()
        for r in H[i]:
            if r[1]==-1:
                X.add(r)
            else:
                Y.add(r)
        if len(X)>=2 or len(Y)>=2:
            print(0)
            exit()
        else:
            a=list(X)[0]
            b=list(Y)[0]
            z=a[0]-b[0]
            if z%2==1:
                print(0)
                exit()
            x=z//2
            if x<0:
                print(0)
                exit()
        flag=1
if flag==1 and x!=-1:
    print(1)
elif flag==1 and x==-1:
    print(0)
else:
    L=[]
    R=[]
    for i in range(N):
        if H[i][0][1]==-1:
            L.append(H[i][0][0])
        else:
            R.append(H[i][0][0])
    print(max([min(L)+min(R)-1,0]))


### FIXED CODE ###

#(x,y)...xt+yが書かれる
from collections import deque
N,M=map(int,input().split())
G=[{} for i in range(N)]
for i in range(M):
    u,v,s=map(int,input().split())
    u-=1;v-=1
    G[u][v]=s;G[v][u]=s
H=[(0,0) for i in range(N)]
t=None
q=deque([0])
H[0]=(1,0)
while(q):
    r=q.pop()
    for p in G[r]:
        s=G[r][p]
        tmp=(-H[r][0],s-H[r][1])
        if H[p]==(0,0):
            H[p]=tmp
            q.append(p)
        elif H[p]==tmp:
            pass
        else:
            if H[p][0]==tmp[0]:
                print(0)
                exit()
            else:
                a=H[p][1]
                b=tmp[1]
                if H[p][0]==-1:
                    a,b=b,a
                #t+a=-t+b
                #2t=b-a
                if (b-a)%2:
                    print(0)
                    exit()
                else:
                    t=(b-a)//2
'''
t+a>=0:t>=-a
-t+b>=0:t<=b
inf=max(a)
sup=min(b)
'''
if t==None:
    inf=0
    sup=10**18
    for i in range(N):
        if H[i][0]==1:
            inf=max(inf,-H[i][1])
        else:
            sup=min(sup,H[i][1])
    print(max(sup-inf-1,0))
else:
    ans=[None for i in range(N)]
    q=deque([0])
    ans[0]=t
    while(q):
        r=q.pop()
        for p in G[r]:
            if ans[p]==None:
                ans[p]=G[r][p]-ans[r]
                q.append(p)
    flag=1
    for i in range(N):
        for j in G[i]:
            if ans[i]+ans[j]!=G[i][j]:
                flag=0
                break
        if flag==0:
            break
    if flag and min(ans)>0:
        print(1)
    else:
        print(0)
### BUGGY CODE ###

h,w=map(int,input().split())
grid=[None]*h
seen=[[-1 for i in range(w)] for j in range(h)]
from collections import deque
que=deque()
for i in range(h):
  grid[i]=input()
  for j in range(len(grid[i])):
    if grid[i][j]=="#":
      que.append([i,j,0])
      
grid=None
      
ans=0
while que:
  node=que.popleft()
  y=node[0]
  x=node[1]
  p=node[2]
  if seen[y][x]==-1:
    seen[y][x]=p
  else:
    continue
  ans=p
  if y-1>=0 and seen[y-1][x]==-1:
    que.append([y-1,x,p+1])
  if y+1<h and seen[y+1][x]==-1:
    que.append([y+1,x,p+1])
  if x-1>=0 and seen[y][x-1]==-1:
    que.append([y,x-1,p+1])
  if x+1<w and seen[y][x+1]==-1:
    que.append([y,x+1,p+1])
print(ans)

### FIXED CODE ###

H,W=map(int,input().split())
INF=10**4
import numpy as np
a=np.full((H,W),INF,dtype=int)
for i in range(H):
  s=input()
  for j in range(len(s)):
    if s[j]=="#":
      a[i,j]=0

for i in range(0,W-1):
  np.minimum(a[:,i]+1,a[:,i+1],out=a[:,i+1])
for i in range(W-1,0,-1):
  np.minimum(a[:,i]+1,a[:,i-1],out=a[:,i-1])
for j in range(0,H-1):
  np.minimum(a[j,]+1,a[j+1,],out=a[j+1,])
for j in range(H-1,0,-1):
  np.minimum(a[j,]+1,a[j-1,],out=a[j-1,])

print(a.max())
### BUGGY CODE ###

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

Es = [[] for _ in range(N)]
for i in range(M):
    A , B = list(map(int, input().split()))
    Es[A-1].append(B-1)
    Es[B-1].append(A-1)


i = 1
j = 1
dis = 0
#ans = [-1 for _ in range(N)]
cand = []
used = [-1 for i in range(N)]
used[0] = 0
tar = 0
cnt = 1
print("Yes")
p = 0
while True:
    for each in Es[tar]:
        if used[each] <0 :
            used[each] = tar
            cand.append(each)
            cnt += 1
    if len(cand) == 0:
        break
    if cnt == N:
        break
    tar = cand.pop(0)

for i in range(1,N):
    print(used[i]+1)


### FIXED CODE ###

import math, sys
from collections import deque
N , M = list(map(int, input().split()))

Es = [[] for _ in range(N+1)]
for i in range(M):
    A , B = list(map(int, input().split()))
    Es[A].append(B)
    Es[B].append(A)

used = [False]*(N+1)
used[1] = True

ans = [-1]*(N+1)

cand = deque([1])
while len(cand)>0:
    tar = cand.popleft()
    for each in Es[tar]:
        if used[each]:
            continue
        cand.append(each)
        ans[each]=tar
        used[each]= True

print("Yes")
for i in range(2,N+1):
    print(ans[i])
### BUGGY CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a 
def multiple_gcd(a):
    ans = a[0]
    for i in range(1, len(a)):
        ans = gcd(ans, a[i])
    return ans

def pairwise_coprime():
    for i in range(N-1):
        for j in range(i+1, N):
            if gcd(A[i], A[j]) != 1:
                return 0
    return 1

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

if pairwise_coprime() == 1:
    print('pairwise coprime')
elif multiple_gcd(A) == 1:
    print('setwise coprime')
else:
    print('not coprime')


### FIXED CODE ###

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
    
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a 
def multiple_gcd(a):
    ans = a[0]
    for i in range(1, len(a)):
        ans = gcd(ans, a[i])
    return ans

def pairwise_coprime_gcd():
    for i in range(N-1):
        for j in range(i+1, N):
            if gcd(A[i], A[j]) != 1:
                return 0
    return 1
def pairwise_coprime(A):
    prime = set()
    for i in range(N):
        fact = factorization(A[i])
        for x in fact:
            if x[0] in prime:
                return 0
            if x[0] != 1:
                prime.add(x[0])
    return 1

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

if pairwise_coprime(A) == 1:
    print('pairwise coprime')
elif multiple_gcd(A) == 1:
    print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###

n,m=map(int,input().split())
a=sorted(map(int,input().split()))
mx=0
for i in range(m):
    b,c=map(int,input().split())
    j=0
    tmp=0
    while a[j]<c and j+1<=b:
        a[j]=c
        j+=1
        if j>=n:break
    a.sort()        
print(sum(a))

### FIXED CODE ###

# 2019/07/20

from heapq import heappop,heappush,heapify

n,m=map(int,input().split())
a=list(map(int,input().split()))
heapify(a)
bc=[]
for i in range(m):
    b,c=map(int,input().split())
    hq=(-c,b)
    heappush(bc,hq)



def cg(res):

    while bc:
        c,b=heappop(bc)
        c=-c
        while b and a:
            b-=1
            v=heappop(a)
            if c>v:res+=c
            else:
                res+=v
                return res
    return res
res=0
res=cg(res)
print(sum(a)+res)
### BUGGY CODE ###

n = int(input())
s = input()
cou = 0
for i in range(1000):
  bit =0
  i = "{0:03d}".format(i)
  a,b,c = i[0],i[1],i[2]
  for j in range(n):
    if s[j]==a and bit==0:
      for k in range(j+1,n):
        if s[k]==b and bit==0:
          for m in range(k+1,n):
            if s[m]==c and bit==0:
              cou += 1
              bit = 1 
print(cou)

### FIXED CODE ###

n = int(input())
s = input()
cou = 0
for i in range(1000):
  i = "{0:03d}".format(i)
  t = 0
  r = 0
  while r!=n:
    if s[r]==i[t]:
      t += 1
    if t==3:
      cou += 1
      r = n-1
    r += 1            
print(cou)
### BUGGY CODE ###

import sys
import math
import fractions
import bisect
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint
N, K = map(int, input().split())

1行のstring
S, T = input().split()

1行の整数配列
P = list(map(int,input().split()))

改行あり
x = []
y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)

N行M列の初期化
dp = [[INF] * M for i in range(N)]

'''

N, D, A = map(int, input().split())
XH = []
X = []

for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    XH.append([x1, y1])
    X.append(x1)

    
def counting(hp):
    return hp//A + int(hp%A!=0)

ans = 0
XH.sort()
X.sort()

begin = 0
last = XH[begin][0] + 2*D
while True:
    need = counting(XH[begin][1])
    ans += need
    
    # これより手前までを減らす
    end = bisect.bisect_right(X, last)

    # 爆発
    for i in range(begin, end):
        # 最後に達したら終える
        if i == N:
            break
        XH[i][1] -= need*A
        
    # 次の範囲に更新
    for i in range(begin, end):
        
        if XH[i][1] > 0:
            begin = i
            last = XH[begin][0] + 2*D
            break

        # 最後まで０にできてたらおしまい
        elif i == N-1:
            print(ans)
            sys.exit()

        # 範囲がすべて０以下なら次に行く
        elif i == end-1:
            begin = end
            last = XH[begin][0] + 2*D








"""
ATTENTION: Pythonで間に合うか？？

            <目安>
 文字列結合、再帰関数を含む→Python
 上を含まず時間が不安→PyPy3

"""

### FIXED CODE ###

import sys
import math
import fractions
import bisect
import queue
import heapq
from collections import deque
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint
N, K = map(int, input().split())

1行のstring
S, T = input().split()

1行の整数配列
P = list(map(int,input().split()))

改行あり
x = []
y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    x.append(x1)
    y.append(y1)

N行M列の初期化
dp = [[INF] * M for i in range(N)]

'''

N, D, A = map(int, input().split())
XH = []

for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    XH.append([x1, y1])

    
def counting(hp):
    if hp < 0:
        return 0
    return hp//A + int(hp%A!=0)

XH.sort()


bombs = deque([]) # 有効な爆弾の威力と範囲を保存する
power = 0 # 有効な爆弾の威力の合計

ans = 0
for i in range(N):
    
    # 使えない爆弾を捨てる
    while len(bombs)>0 and bombs[0][0] < XH[i][0]:
        power -= bombs.popleft()[1]

    # パワーの不足分の爆弾
    add = counting(XH[i][1]-power) 
    ans += add
    
    # 追加した爆弾をキューに加える
    bombs.append((XH[i][0] + 2*D, add*A))
    power += add*A


print(ans)









"""
ATTENTION: Pythonで間に合うか？？

            <目安>
 文字列結合、再帰関数を含む→Python
 上を含まず時間が不安→PyPy3

"""
### BUGGY CODE ###

import sys

N, *A = map(int, sys.stdin.read().split())

mod = 10**9 + 7
ans = 0
for n, i in enumerate(A[:-1]):
    for j in A[n + 1:]:
        ans += i ^ j
print(ans % mod)


### FIXED CODE ###

import sys

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

mod = 10**9 + 7

cnt = [0] * 61
for a in A:
    for i in range(61):
        if a >> i & 1:
            cnt[i] += 1

ans = 0
p = 1
for i in cnt:
    ans = (ans + (p * i * (N - i)) % mod) % mod
    # ans %= mod
    p = p * 2 % mod
    # p %= mod

print(ans % mod)
### BUGGY CODE ###

import sys

n = int(input())

a = []
for i in range(n):
  v = list(map(int, input().split(' ')))
  a.append(v)

f = True
day = 1
while(f):
  done = []
  nokori = 0
  for m in range(n):
    if m in done:
      pass
    elif len(a[m]):
      teki = a[m][0]
      jibun = m + 1
      if not len(a[teki - 1]):
        print(-1)
        sys.exit()
      elif a[teki - 1][0] == jibun and teki - 1 not in done:
        a[m].pop(0)
        a[teki - 1].pop(0)
        done.append(m)
        done.append(teki - 1)
    nokori += len(a[m])
  if not nokori:
    for m in range(n):
      if len(a[m]):
        print(-1)
        sys.exit()
    print(day)
    sys.exit()
  day += 1

### FIXED CODE ###

import sys
import time
from collections import deque

start = time.time()

input = sys.stdin.readline

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]
nokori_games = n * (n - 1) / 2 
day = 1
r5000 = range(5000)
player_in_this_game = set()
rn = range(n)
for _ in r5000:
  for m in rn: #選手ごとに判定
    #整合性のある対戦組み合わせがあれば配列から消す
    #全員の判定が終わって試合が残っていたら1日増やす
    if m in player_in_this_game:
      #自分が既に試合が組まれている
      continue

    la = len(a[m])      
    if la: #選手に試合予定が残っている
      teki = a[m][0] #対戦相手
      jibun = m + 1 #自分
      teki_idx = teki - 1
      if teki_idx in player_in_this_game:
        #相手が既に試合に組まれている
        continue

      if a[teki_idx][0] == jibun: #対戦相手の予定も自分でかつ相手がこのターンで試合中ではない
        a[m].popleft() #自分の予定を消す
        a[teki_idx].popleft() #相手の予定を消す
        player_in_this_game.add(m) #自分を試合中にする
        player_in_this_game.add(teki_idx) #相手を試合中にする
        nokori_games -= 1 #残り試合予定を1つ減らす

  if nokori_games: #残り試合があるのに
    if not len(player_in_this_game): #今回対戦が組まれなければ残りの予定が不整合なのでエラー
      print(-1)
      sys.exit()
  else: #誰も残り試合予定がなければ終了
    print(day)
    sys.exit()
  day += 1
  player_in_this_game.clear()
  elapsed_time = time.time() - start
  if elapsed_time > 1:
    print(n*(n-1)//2)
    exit()
### BUGGY CODE ###

# divide this matrix into 3 groups according to the remainder
# then consider the cost

from itertools import permutations

N, C = [int(elem) for elem in input().split(' ')]
D_matrix = [[int(elem) for elem in input().split(' ')] for _ in range(C)]
assert len(D_matrix) == C
assert len(D_matrix[0]) == C
c_matrix = [[int(elem) for elem in input().split(' ')] for _ in range(N)]
assert len(c_matrix) == N
assert len(c_matrix[0]) == N

# grouping
# O(N^2)
mod_0, mod_1, mod_2 = [], [], []
for i in range(N):
    for j in range(N):
        if (i + j) % 3 == 0:
            mod_0.append((i, j))
        elif (i + j) % 3 == 1:
            mod_1.append((i, j))
        else:
            mod_2.append((i, j))

# O(C^3 * N^2)
min_cost = float('inf')
for colors in permutations(range(C), 3):
    total_cost = 0
    for idx_color, mod in enumerate((mod_0, mod_1, mod_2)):
        for i, j in mod:
            color = c_matrix[i][j] - 1
            total_cost += D_matrix[color][colors[idx_color] - 1]
    min_cost = min(min_cost, total_cost)

print(min_cost)

### FIXED CODE ###

from itertools import permutations

N, C = [int(elem) for elem in input().split(' ')]
D_matrix = [[int(elem) for elem in input().split(' ')] for _ in range(C)]
assert len(D_matrix) == C
assert len(D_matrix[0]) == C
c_matrix = [[int(elem) for elem in input().split(' ')] for _ in range(N)]
assert len(c_matrix) == N
assert len(c_matrix[0]) == N

# grouping
# O(N^2)
mod_list = [[] for _ in range(3)]
for i in range(N):
    for j in range(N):
        mod_list[(i + j) % 3].append((i, j))

# O(N^2)
mod_color_list = [[0] * C for _ in range(3)]
for k, mod in enumerate(mod_list):
    for i, j in mod:
        mod_color_list[k][c_matrix[i][j] - 1] += 1

# O(C^3 * N^2) -> O(C^4)
min_cost = float('inf')
for colors in permutations(range(C), 3):
    total_cost = 0
    for color, mod_color in zip(colors, mod_color_list):
        total_cost += sum([D_matrix[X][color] * mod_color[X] for X in range(C)])
    min_cost = min(min_cost, total_cost)

print(min_cost)
### BUGGY CODE ###

N,Q = map(int, input().split())
import copy
import sys

sys.setrecursionlimit(10**6)
es = {}
for i in range(N-1):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    if a in es:
        es[a].append(b)
    else:
        es[a] = [b]


point_root = [0] * N
query = [None]
for i in range(Q):
    p,x = map(int, input().split())
    point_root[p-1] += x 
point_root = tuple(point_root)
ans = [0] * N
visited = [False] * N
#ans[0] = point_root[0]
#visited[0] = True
def solve(node, point):
    #print("aa", *ans)
    ans[node] += point
    visited[node] = True
    if all(visited) == True:
        print(*ans)
        exit()

    if es.get(node, None) != None:
        next_nodes = (es[node]) # これからポイントを足し行くやつら
        for i in next_nodes:
            solve(i, point+point_root[i])
solve(0, point_root[0])

### FIXED CODE ###

N,Q = map(int, input().split())
import copy
import sys

sys.setrecursionlimit(10**6)
es = [[] for i in range(N)]

for i in range(N-1):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    es[a].append(b)
    es[b].append(a)


point = [0] * N

for i in range(Q):
    p,x = map(int, input().split())
    point[p-1] += x 

ans = [0] * N
ans[0] = point[0] # 一番上の根なのでこれだけ
visited = [False] * N
visit_cnt = 1
from collections import deque
nexts = deque([0])
while len(nexts) >= 1:
    now = nexts.popleft()
    visited[now] = True

    for next in es[now]:
        if visited[next] == True:
            continue
        nexts.append(next)
        ans[next] = ans[now] + point[next]


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

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

if k <= n:
    takahashi = 0
    for _ in range(k):
        takahashi = a[takahashi] - 1
    print(takahashi + 1)
else:
    start = 0
    takahashi = start
    trajectory = [takahashi]
    loop_start = -1
    loop_end = -1
    for i in range(n):
        takahashi = a[takahashi] - 1
        if takahashi in trajectory:
            loop_start = trajectory.index(takahashi)
            break
        trajectory.append(takahashi)
    print(trajectory[loop_start:][(k - loop_start) % (i + 1 - loop_start)] + 1)


### FIXED CODE ###

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

if k <= n:
    takahashi = 0
    for _ in range(k):
        takahashi = a[takahashi] - 1
    print(takahashi + 1)
else:
    start = 0
    takahashi = start
    trajectory = [takahashi]
    loop_start = -1
    loop_end = -1
    visited = [False] * n
    visited[0] = True
    for i in range(n):
        takahashi = a[takahashi] - 1
        if visited[takahashi]:
            loop_start = trajectory.index(takahashi)
            break
        visited[takahashi] = True
        trajectory.append(takahashi)
    print(trajectory[loop_start:][(k - loop_start) % (i + 1 - loop_start)] + 1)
### BUGGY CODE ###

flg=[False for i in range(1000001)]
a=int(input())
flg[a]=True
for i in range(2,10000000000000):
  if a%2==0:
    a//=2
  else:
    a=3*a+1
  if flg[a]:
    break
print(i)

### FIXED CODE ###

flg=[False for i in range(1000001)]
a=int(input())
flg[a]=True
for i in range(2,10000000000000):
  if a%2==0:
    a//=2
  else:
    a=3*a+1
  if flg[a]:
    break
  flg[a]=True
print(i)