Harryxun/stf_run huggingface dataset:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

S = sys.stdin.readline().rstrip()
K = int(sys.stdin.readline())


def prune(it):
    print(list(it))
    hist = set()
    ret = []
    for s, l in it:
        if s not in hist:
            hist.add(s)
        if len(hist) > K:
            break
        ret.append((s, l))
    return ret


collections = prune(sorted([(c, L) for L, c in enumerate(S)]))
for size in range(1, len(S)):
    threshold, _ = collections[-1]
    for s, left in collections:
        r = left + size + 1
        if len(s) == size and r <= len(S):
            t = S[left:r]
            if t <= threshold:
                collections.append((t, left))
    collections = prune(sorted(collections))

strings = list(set([s for s, _ in collections]))
strings.sort()
print(strings[K - 1])


### FIXED CODE ###

import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

S = sys.stdin.readline().rstrip()
K = int(sys.stdin.readline())

s = set()
for k in range(1, K + 1):
    for i in range(len(S)):
        s.add(S[i:i + k])

s = list(sorted(list(s)))
print(s[K - 1])
import sys
x = int(sys.stdin.readline())
a = 0.1
b = 0
while not a.is_integer():
  a = x-b**5
  a = a**0.2
  b += 1
print(int(a), b-1)

### FIXED CODE ###

import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7


x = ri()
for a in range(150):
    for b in range(-150, a):
        if a**5 - b**5 == x:
            print(a, b)
            exit()
A,B = map(int, input().split()

x = max([A + B, A - B, A * B])

print(x)



### FIXED CODE ###

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

x = a[0] + a[1]
y = a[0] - a[1]
z = a[0] * a[1]

if x >= y and x >= z:
  print(x)
elif y >= x and y >= z:
  print(y)
else:
  print(z)
a = [1, 3, 5, 7, 8, 10, 12]
b = [4, 6, 9, 11]
c = [2]

x, y = map(int, input().split())

if (x in a and y in a) or (x in b and y in b) or (x in c and y in c):
    print(Yes)
else:
    print(No)  

### FIXED CODE ###

a = [1, 3, 5, 7, 8, 10, 12]
b = [4, 6, 9, 11]
c = [2]

x, y = map(int, input().split())

if (x in a and y in a) or (x in b and y in b) or (x in c and y in c):
    print('Yes')
else:
    print('No')
li= list(map(int, input().split()))
li.insert(1) = li.pop(0)
li.insert(2) = li.pop(0)
print(li)

### FIXED CODE ###

li= list(map(int, input().split()))
li.insert(1, li.pop(0))
li.insert(2, li.pop(0))
li.insert(0, li.pop(1))
print(li[0], li[1], li[2])
from collections import Counter
import numpy as np

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

count = Counter(a)
# 1; Counter 同士を比較
# 2; 2step loopで2個であることを確認する。

# > linspace で2個ずつ２ステップのリストを比較して、リストが同じであるかIFチェックする。

# 偶数
if (n % 2 == 0):
    check = [0] * n
    for i in range(1, n, 2):
        check[i - 1] = i
        check[i] = i

    checkC = Counter(check)

    if (checkC == count):
        ans = 2 ** (n / 2)
    else:
        ans = 0
# n = 1
elif (n == 1):
    if (a[0] == 0):
        ans = 1
    else:
        ans = 0


# 奇数
else:
    check = [0] * n
    for i in range(2, n, 2):
        check[i - 1] = i
        check[i] = i

    checkC = Counter(check)
    if (checkC == count):
        ans = 2 ** ((n - 1) / 2)
    else:
        ans = 0

print(int(ans))


### FIXED CODE ###

from collections import Counter
import numpy as np

MOD = 10 ** 9 + 7

n = int(input())
a = list(map(int, input().split()))
count = Counter(a)
# 0の個数は、count[0]
num = len(a)
ans = 1


if (num % 2 == 0):
    # 偶数パターン
    temp = 1
    loop = int(num / 2)
    for i in range(loop):
        tar = count[temp]
        if (tar == 2):
            ans *= 2
            temp += 2
        else:
            print(0)
            exit()

else:

    tar0 = count[0]
    if (tar0 == 1):
        pass
    else:
        print(0)
        exit()

    temp = 2

    for i in range(num // 2):
        if (count[temp] == 2):
            ans *= 2
            temp += 2
        else:
            print(0)
            exit()

ans %= MOD
print(ans)
N = int(input())

ALL = 800 * N

TIMES = (N // 15) * 200

print(All - TIMES)

### FIXED CODE ###

N = int(input())
sum = 800 * N
otsuri = (N // 15) * 200

print(sum - otsuri)
n = int(input())
for i in range(n):
	li  = sorted(input().split())
	if(li[0] ** 2 + li[1] ** 2 == li[3] ** 2):
		print('YES')
	elif:
		print('NO')


### FIXED CODE ###

n = int(input())
for i in range(n):
	li  = sorted(map(int, input().split()))
	if(pow(li[0], 2) + pow (li[1], 2) == pow(li[2], 2)):
		print('YES')
	else:
		print('NO')
import math
import decimal
a, b, c = map(int, input().split())
print('Yes' if ( 2 * Decimal(a*b).sqrt() + a + b - c < 0 ) else 'No')

### FIXED CODE ###

import math
from decimal import *
a, b, c = map(int, input().split())
print('Yes' if ( 2 * Decimal(a*b).sqrt() + a + b - c < 0 ) else 'No')
#%%
N = int(input())
S = list(input())

T = S.copy()

flag = False

#print(S)


for i in range(N):
    flag = False
    i = 0
    while True:
        if i > len(S) - 1:
            break
        if S[i] == '(':
            tmp = i
            flag = True
        if flag and S[i] == ')':
            S.pop(tmp)
            S.pop(i)
            flag = False
        i += 1

#print(S)
#print(T)

a = S.count('(')
b = S.count(')')

ans = '('*b + ''.join(T) + ')'*a
print(ans)

### FIXED CODE ###

#%%
N = int(input())
S = list(input())

T = S.copy()

flag = False

#print(S)


for i in range(N):
    flag = False
    i = 0
    while True:
        if i > len(S) - 1:
            break
        if S[i] == '(':
            tmp = i
            flag = True
        if flag and S[i] == ')':
            S.pop(i)
            S.pop(tmp)
            flag = False
        i += 1

#print(S)
#print(T)

a = S.count('(')
b = S.count(')')

ans = '('*b + ''.join(T) + ')'*a
print(ans)
n,q=map(int,input().split())
s=input()
ind=[]
z=0
for i,j in zip(s[:-1],s[1:]):
    if i+j=="AC":
        ind.append(z)
    z+=1

aa=len(ind)
for i in range(q):
    l,r=map(int,input().split())
    l-=1
    r-=1
    for ii,jj in enumerate(ind):
        if jj>=l:
            start=ii
            break
    for ii,jj in enumerate(ind[::-1]):
        if jj<r:
            end=ii
            break
    print(max(0,aa-(start+end)))

### FIXED CODE ###

n,q=map(int,input().split())
S=input()
cnt=[0]*n

for i in range(1, n):
    s=S[i-1]+S[i]
    if s=="AC":
        cnt[i]+=1

for i in range(1, n):
    cnt[i]+=cnt[i-1]

for _ in range(q):
    l, r=map(int,input().split())
    ans=cnt[r-1]-cnt[l-1]
    print(ans)
n = int(input())
blu_list = [str(input()) for _ in range(n)]
m = int(input())
red_list = [str(input()) for _ in range(m)]

blu_set_list = list(set(blu_list))
red_set_list = list(set(red_list))
set_list = blu_set_list + red_set_list

blu_cnt = []
red_cnt = []
ans = []

for i in set_list:
    blu_cnt.append(blu_list.count(i))
    red_cnt.append(red_list.count(i))

for i in range(len(blu_list)):
    ans.append(blu_cnt[i] - red_cnt[i])

print(max(ans) if max(ans) > 0 else 0)

### FIXED CODE ###

n = int(input())
blu_list = [str(input()) for _ in range(n)]
m = int(input())
red_list = [str(input()) for _ in range(m)]

blu_set_list = list(set(blu_list))
red_set_list = list(set(red_list))
set_list = blu_set_list + red_set_list

blu_cnt = []
red_cnt = []
ans = []

for i in set_list:
    blu_cnt.append(blu_list.count(i))
    red_cnt.append(red_list.count(i))

for i in range(len(set_list)):
    ans.append(blu_cnt[i] - red_cnt[i])

print(max(ans) if max(ans) > 0 else 0)
X,N=map(int, input().split())
p=list(map(int,input().split()))
p.sort()    
for k in range(0,51):
    if not X-k in p:
        print(X-k)
        break 
    elif not X+k in p_list:
        print(X+k)
        break

### FIXED CODE ###

X, N = map(int, input().split())
p_list = list(map(int, input().split()))

if N == 0: 
   print(X)
else:
   for i in range(0,100):
       if not X-i in p_list:
           print(X-i)
           break
       elif not X+i in p_list:
           print(X+i)
           break
N = int(input())

def ask(n):
    print(n, flush=True)
    resp = input().rstrip()[0]
    if resp == 'V':
        exit()
    return resp

resp = ask(0)

def condition(L,R,resp_L,resp_R):
    if (R-L)&1:
        return resp_L == resp_R
    else:
        return resp_L != resp_R

L = 0
R = 0
resp_L = resp
resp_R = resp
for _ in range(19):
    M = (L + R) // 2
    resp_M = ask(M)
    if condition(L,M,resp_L,resp_M):
        R,resp_R = M,resp_M
    else:
        L,resp_L = M,resp_M

### FIXED CODE ###

x,y = map(int,input().split())
answer = x if x%y else -1
print(answer)
tmp = []
for i in range(4):
  tmp.append(int(input()))
  
ptint(min(tmp[0], tmp[1])+min(tmp[2], tmp[3]))

### FIXED CODE ###

tmp = []
for i in range(4):
  tmp.append(int(input()))
  
print(min(tmp[0], tmp[1])+min(tmp[2], tmp[3]))
[N,L] = [int(x) for x in input().split()]
A = {10**9+1:1}
ANS = [10**9+1]*N
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    try : A[x] += [i]
    except KeyError : A[x] =  [i]
for i in set(A) :
    for j in A[i] :
        for k in range(L) :
            try :
                if ANS[j+k] == 10**9+1 : 
                    ANS[j+k] = i
                    count += 1
            except IndexError : continue
    if count == N : break
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])
from collections import Counter
 
a = map(int, input())
b = Counter([input() for _ in range(a)])
for k,v in b.items():
  print(f"{k} x {v}")

### FIXED CODE ###

from collections import Counter
 
a = int(input())
b = [input() for _ in range(a)]
for v in ["AC", "WA", "TLE", "RE"]:
  print(f"{v} x {b.count(v)}")
import numpy as np
N,M= list(map(int, input().split()))
K = []
S=[]
state_S = np.zeros(N)
for m  in range(M):
    _input = list(map(int, input().split()))
    K.append(_input[0])
    S.append(np.array(_input[1:]))
P = list(map(int, input().split()))
ans=0
for i in range(N ** 2):
    pattern= np.array([i >> bit & 1 for bit in range(N)])
    if all(sum(pattern[K[j] -1 ]) % 2 == P[j] for j in range(M)):
        ans += 1
print(ans)





### FIXED CODE ###

import numpy as np
N,M= list(map(int, input().split()))
K = []
S=[]
state_S = np.zeros(N)
for m  in range(M):
    _input = list(map(int, input().split()))
    K.append(_input[0])
    S.append(np.array(_input[1:]))
P = list(map(int, input().split()))
ans=0
for i in range(2 ** N):
    pattern= np.array([i >> bit & 1 for bit in range(N)])
    if all(np.sum(pattern[S[j] -1 ]) % 2 == P[j] for j in range(M)):
        ans += 1
print(ans)
s = input()
s1 = sorted(s)
s2 = input()


ans = 0
ans2 = 0



for i in s2:
    if s == s2:
        break
    if s1[0] <= i:
        ans = ans + 1
        for k in range(0,len(s1)):
            if s1[k] <= i:
                ans2 = ans2 + 1
    
if ans != 0 and ans2 != 0:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

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

adivb =((a+b)//2) 
addition = ((a+b)%2)

print((adivb)+(addition))
N=int(input())
name=[]
for i in range(N):
  name.append(input())
M=0
A=0
R=0
C=0
H=0
letters=['M','A','R','C','H']
for i in range(N):
  for j in letters:
    if name[i][0]==j:
      if j=='M':
        M+=1
      elif j=='A':
        A+=1
      elif j=='R':
        R+=1
      elif j=='C':
        C+=1
      elif j=='H':
        H+=1
kazu=!
if M==0:
  M+=1
if A==0:
  A+=1
if C==0:
  C+=1
if R==0:
  R+=1
if H==0:
  H+=1
print(M*A*C*R*H)

### FIXED CODE ###

N=int(input())
print(N//3)
N = int(input())
a = [int(input()) for i in range(N)]
c = 0
dai = a.index(2)
for i in range (1,N):
  ti = a.index(i)
  dai = a.index(i+1)
  if  ti <  dai:
      c += 1
  else:
     break
d = 0
for  i  in range (N,1,-1):
  dai  =  a.index(i)
  ti =  a.index(i-1)
  if   ti < dai:
    d += 1
  else:
    break
jo =  max(c,d)
ans = N - jo - 1
print(ans)

### FIXED CODE ###

n = int(input())
t = [0]*n
for i in range(n):
    p = int(input())-1
    t[p] = i
maxi = 1
c = 1
for i in range(n-1):
  a = t[i]
  b = t[1+i]
  if a < b:
    c += 1
  else:
    maxi = max(c,maxi)
    c = 1
maxi = max(c,maxi)
print(n - maxi)
A,B=map(int,input().split())
S=set(range(25*A//2,25*(A+1)//2))&set(range(10*B,10*(B+1)))
print(S.pop() if len(S)>0 else -1)


### FIXED CODE ###

c=input().count('A')
print('No' if c==3 or c==0 else 'Yes')
f = open("C:/Users/naoki/Desktop/Atcoder/input.txt")


N, T = map(int, f.readline().split())
ab = [list(map(int, f.readline().split())) for _ in range(N)]

Dp = [0 for _ in range(T+1)]

ab = sorted(ab, key = lambda x: x[0])

for i in range(N-1):
    for j in range(T-1,-1, -1):
        if j+ab[i][0] <= T-1:
            kari2 = Dp[j] + ab[i][1]
            if  Dp[j+ab[i][0]] < kari2:
                Dp[j+ab[i][0]] = kari2
print(Dp[T-1]+ab[-1][1])

### FIXED CODE ###

N, T = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N)]

Dp = [0 for _ in range(T+1)]

ab = sorted(ab, key = lambda x: x[0])

for i in range(N):
    for j in range(T-1,-1, -1):
        if j+ab[i][0] <= T-1:
            kari2 = Dp[j] + ab[i][1]
            if  Dp[j+ab[i][0]] < kari2:
                Dp[j+ab[i][0]] = kari2
        else:
            kari2 = Dp[j] +ab[i][1]
            if Dp[T] < kari2:
                Dp[T] = kari2
                
print(max(Dp))
N = int(input())

s = []
a = 26
tmp = 1
for i in range(20):
    s.append(tmp)
    tmp += a
    a *= 26
    if tmp > 1000000000000001:
        break

for i in range(len(s)):
    if N >= s[i]:
        continue
    else:
        size = i 
        break

b = N - s[size-1]

n2a = lambda c: chr(c+64)
a = 26 ** (size-1)

ans = []
while(a >= 1):
    ans.append(n2a(b // a + 1).lower())
    b %= a
    a //= 26

print(*ans, sep="")

### FIXED CODE ###

N = int(input())

s = []
a = 26
tmp = 1
for i in range(20):
    s.append(tmp)
    tmp += a
    a *= 26
    if tmp > 100000000000000000:
        break

for i in range(len(s)):
    if N >= s[i]:
        continue
    else:
        size = i 
        break

b = N - s[size-1]

n2a = lambda c: chr(c+64)
a = 26 ** (size-1)

ans = []
while(a >= 1):
    ans.append(n2a(b // a + 1).lower())
    b %= a
    a //= 26

print(*ans, sep="")
#input_f = "3 4 5\n2 1 2\n6 3 4\n1 1 1\n1 2 3"
def t_check(a,b,c):
    if a + b > c:
        if b + c > a:
            if a + c > b: return True
    return False



def f_check(a_, b_, c_):
    tmp = []
    tmp.append(a_)
    tmp.append(b_)
    tmp.append(c_)
    sqrts = []
    for i in range(3):
        sqrts.append(tmp[i]**2)
    m = max(sqrts)
    s = sum(sqrts)

    print(m,s)

    if m == (s - m): return(0)
    if m > (s - m): return(2)
    if m < (s - m): return(1)
    
    
counter=[0,0,0]
    
    
while(1):
    input_f = input()


    t = input_f.split("\n")[i].split()
    fn, sn, tn = int(t[0]),int(t[1]),int(t[2])
    if t_check(fn,sn,tn):
        counter[f_check(fn,sn,tn)] += 1
    else: break
    

print(sum(counter),counter[0], counter[1], counter[2])

        



### FIXED CODE ###

def t_check(a,b,c):
    if a + b > c:
        if b + c > a:
            if a + c > b: return True
    return False

def f_check(a_, b_, c_):
    tmp = []
    tmp.append(a_)
    tmp.append(b_)
    tmp.append(c_)
    sqrts = []
    for i in range(3):
        sqrts.append(tmp[i]**2)
    m = max(sqrts)
    s = sum(sqrts)

    if m == (s - m): return(0)
    if m > (s - m): return(2)
    if m < (s - m): return(1)
    
counter=[0,0,0]
    
while(1):
    input_f = input()

    t = input_f.split()
    fn, sn, tn = int(t[0]),int(t[1]),int(t[2])
    if t_check(fn,sn,tn):
        counter[f_check(fn,sn,tn)] += 1
    else: break
    
print(sum(counter),counter[0], counter[1], counter[2])
date = map(int, input().split("/"))
if date[0] > 2019:
	if date[1] > 5:
		print("Heisei")
else:
	print("TBD")


### FIXED CODE ###

date = list(map(int, input().split("/")))
if date[0] >= 2019 and date[1] >= 5:
	print("TBD")
else:
  print("Heisei")
k=int(input())

a=[]
i=1
d=0
while True:
    if len(str(i))==1:
        a.append(i)
    elif len(str(i))==2:
        I=str(i)
        c=abs(int(I[0])-int(I[1]))
        if c<=1:
            a.append(i)   
            
    elif len(str(i))==3:
        I=str(i)
        for j in range(2):
            c=abs(int(I[j])-int(I[j+1]))
            if c<=1:
                d=d+1
        if d==2:
            a.append(i)
        d=0
        
    elif len(str(i))==4:
        I=str(i)
        for j in range(3):
            c=abs(int(I[j])-int(I[j+1]))
            if c<=1:
                d=d+1
        if d==3:
            a.append(i) 
        d=0
        
    elif len(str(i))==5:
        I=str(i)
        for j in range(4):
            c=abs(int(I[j])-int(I[j+1]))
            if c<=1:
                d=d+1
        if d==4:
            a.append(i)   
        d=0
        
    elif len(str(i))==6:
        I=str(i)
        for j in range(5):
            c=abs(int(I[j])-int(I[j+1]))
            if c<=1:
                d=d+1
        if d==5:
            a.append(i)
        d=0
    
    elif len(str(i))==7:
        I=str(i)
        for j in range(6):
            c=abs(int(I[j])-int(I[j+1]))
            if c<=1:
                d=d+1
        if d==6:
            a.append(i)
            
        d=0    
        
    elif len(str(i))==8:
        I=str(i)
        for j in range(7):
            c=abs(int(I[j])-int(I[j+1]))
            if c<=1:
                d=d+1
        if d==7:
            a.append(i)
            
        d=0    
        
    i=i+1
    if i==10000000:
        break

print(a[k-1])

### FIXED CODE ###

n,k=map(int,input().split())
n=n%k
a=min(n,abs(n-k))
print(a)
n = int(input())
lis = []
for i in range(n):
    s,p = list(input().split())
    lis.append([i+1,s,int(p)])
t = sorted(lis, key=lambda x: -x[2])
s = sorted(t, key=lambda x: x[1])


for i in s:
    print(i[0])

### FIXED CODE ###

s = list(input())

res = 0
for i in range(len(s)):
    if s[i] == "x":
        res += 1
if res < 8:
    print("YES")
else:
    print("NO")
# -*- coding: utf-8 -*-


def main():
    from collections import defaultdict
    from collections import deque

    n = int(input())
    graph = [defaultdict(int) for _ in range(n)]
    visited = [False for _ in range(n)]
    dist = [float('inf') for _ in range(n)]

    for i in range(n - 1):
        ai, bi, ci = map(int, input().split())
        ai -= 1
        bi -= 1
        graph[ai][bi] = ci
        graph[bi][ai] = ci

    q, k = map(int, input().split())
    k -= 1
    dist[k] = 0
    d = deque()
    d.append(k)

    while d:
        di = d.popleft()
        visited[di] = True

        for bi, ci in graph[di].items():
            if visited[bi]:
                continue

            dist[bi] = dist[di] + ci
            d.append(bi)

    ans = [0 for _ in range(q)]

    for j in range(q):
        xi, yi = map(int, input().split())
        xi -= 1
        yi -= 1
        ans[j] = dist[xi] + dist[yi]

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


if __name__ == '__main__':
    main()


### FIXED CODE ###

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

# AtCoder Beginner Contest
# Problem A

if __name__ == '__main__':
    number = input()

    if number[0] == number[2]:
        print('Yes')
    else:
        print('No')
print((int(input())-1)*(int(input()-1))

### FIXED CODE ###

a,b = map(int,input().split())
print((a-1)*(b-1))
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
L = int(input())
k = 0
while a[-1] // (L * pow(2, k)): k += 1
e = [[0] * k for _ in range(N)]
for i in range(N):
  t = L + a[i]
  ok = i
  ng = N
  while ng - ok > 1:
    m = (ok + ng) // 2
    if a[m] <= t: ok = m
    else: ng = m
  e[i][0] = ok
for j in range(len(e[i]) - 1):
  for i in range(N):
    x = e[i][j]
    e[i][j + 1] = e[x][j]
#print(e)

def doubling(u, v):
  if u == v: return 0
  x = min(len(e[u]) - 1, bl(e[u], v))
  if x == 0: return 1
  x -= e[u][x] > v
  x = max(0, x)
  return doubling(e[u][x], v) + pow(2, x)

Q = int(input())
for _ in range(Q):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  if x > y: x, y = y, x
  print(doubling(x, y))

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
L = int(input())
k = 1
while a[-1] // (L * pow(2, k)): k += 1
e = [[0] * k for _ in range(N)]
for i in range(N):
  t = L + a[i]
  ok = i
  ng = N
  while ng - ok > 1:
    m = (ok + ng) // 2
    if a[m] <= t: ok = m
    else: ng = m
  e[i][0] = ok
for j in range(len(e[i]) - 1):
  for i in range(N):
    x = e[i][j]
    e[i][j + 1] = e[x][j]
#print(e)

def doubling(u, v):
  if u == v: return 0
  ok = -1
  ng = len(e[u])
  while ng - ok > 1:
    m = (ok + ng) // 2
    if e[u][m] < v: ok = m
    else: ng = m
  if ok < 0: return 1
  return doubling(e[u][ok], v) + pow(2, ok)

Q = int(input())
for _ in range(Q):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  if x > y: x, y = y, x
  print(doubling(x, y))
import numpy as np
N, M, C = list(map(int, input().split()))
B = np.asarray(input().split(), dtype=np.int)
A = []
for i in range(N):
  A.append(list(map(int, input().split())))
A = np.asarray(A, dtype=np.int)

np.sum(A @ B.T > (-1*C))

### FIXED CODE ###

import numpy as np
N, M, C = list(map(int, input().split()))
B = np.asarray(input().split(), dtype=np.int)
A = []
for i in range(N):
  A.append(list(map(int, input().split())))
A = np.asarray(A, dtype=np.int)
 
print(np.sum(np.dot(A, B.T) > (-1*C)))
n,q=map(int,input().split())
l=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)
ans=[0 for i in range(n)]
for i in range(q):
  p,x=map(int,input().split())
  ans[p-1]+=x
def dsf(index,u):
  for i in l[index]:
    if i==u:continue
    ans[i]+=ans[index]
    dsf(i,index)
dsf(0,-1)
print(' '.join(str(j) for j in ans))

### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)
input = sys.stdin.readline
n,q=map(int,input().split())
l=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)
px=[0]*n
for i in range(q):
  p,x=map(int,input().split())
  px[p-1]+=x
ans=[0]*n
def dsf(index,u):
  ans[index]=ans[u]+px[index]
  for i in l[index]:
    if i==u:continue
    dsf(i,index)
dsf(0,-1)
print(*ans)