Harryxun/stf_run huggingface dataset:
import math
N, H = list(map(int, input().split()))
a = []
b = []
for _ in range(N):
    ta, tb = list(map(int, input().split()))
    a.append(ta)
    b.append(tb)

b = list(filter(lambda x: x > max(a), b))
b.sort()
b.reverse()
slashNum = math.ceil( (H - sum(b)) / max(a) )

dmg = slashNum * max(a)
for i in range(N):
    dmg += b[i]
    if dmg >= H:
        print(slashNum + i + 1)
        break

### FIXED CODE ###

N, H = list(map(int, input().split()))
maxA = 0
n = 0
b = []
for _ in range(N):
    ta, tb = list(map(int, input().split()))
    maxA = max(maxA, ta)
    b.append(tb)

b = list(filter(lambda x: x > maxA, b))
b.sort()

while H > 0 and b:
    H -= b.pop()
    n += 1

print(n + max(H-1, -1) // maxA + 1 )
#include <stdio.h>
int main(void){
    int a,b,c;
    scanf("%d %d %d",&a,&b,&c);
    if (a<b<c){
        printf("Yes\n");
    }
    else{
        printf("No\n");
    }

}


### FIXED CODE ###

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

if a<b<c:
  print("Yes")

else:
  print("No")
x**3

### FIXED CODE ###

x=input()
print(x**3
)
a = input()
b = input()
c = input()
 
print( (a + b + c) - max(a, b, c)) 

### FIXED CODE ###

a = [i for i in input().split()]
print(int(sorted(a)[0]) + int(sorted(a)[1]))
N,M=map(int,input().split())

s=[[0 for i in range(N)] for j in range(M)]

for i in range(M):
    tmp=list(map(int,input().split()))

    k=tmp[0]
    for j in range(k):
        s[i][tmp[j+1]-1]=1

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

out=0

for i in range(2**N):
    b=list(map(int,list(bin(i))[2:]))
    b=[0 * (N-len(b))]+b
    ss=1
    for j in range(M):
        t=0
        for k in range(N):
            if b[k]==s[j][k]:
                t+=1
        if t%2!=p[j]:
            ss=0
    if ss==1:
        out+=1

print(out)
       


### FIXED CODE ###

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

s=[[0 for i in range(N)] for j in range(M)]

for i in range(M):
    tmp=list(map(int,input().split()))

    k=tmp[0]
    for j in range(k):
        s[i][tmp[j+1]-1]=1

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

out=0

for i in range(2**N):
    b=list(map(int,list(bin(i))[2:]))
    b=[0 for j in range((N-len(b)))]+b
    ss=1
    for j in range(M):
        t=0
        for k in range(N):
            if b[k]==1 and s[j][k]==1:
                t+=1
        if t%2!=p[j]:
            ss=0
    if ss==1:
        out+=1

print(out)
import sys
input = sys.stdin.readline


def print_ans(X, K, D):
    """Test Case
    >>> print_ans(6, 2, 4)
    2
    >>> print_ans(7, 4, 3)
    1
    >>> print_ans(10, 1, 2)
    8
    >>> print_ans(1000000000000000,1000000000000000,1000000000000000)
    1000000000000000
    """
    # 移動しない
    if K % 2 == 0 and D >= abs(X):
        print(abs(X))
    elif K % 2 != 0 and D >= abs(X):
        print(min(abs(X-D), abs(X+D)))
    elif abs(X) - D * K >= 0:
        print(abs(abs(X) - D * K))
    else:
        # near 0
        tmp = abs(X) // D
        rest_K = K - tmp
        a = abs(abs(X) - tmp * D)
        b = abs(abs(X) - (tmp + 1) * D)
        if rest_K % 2 == 0:
            print(a)
        else:
            print(b)


if __name__ == '__main__':
    X, K, D = map(int, input().rstrip().split())
    print_ans(X, K, D)


### FIXED CODE ###

import collections
import itertools
import sys
input = sys.stdin.readline


def check_tri(a, b, c):
    if a + b > c and b + c > a and c + a > b:
        return True
    else:
        return False


def print_ans(lr):
    """Test Case
    >>> print_ans([4, 4, 9, 7, 5])
    5
    >>> print_ans([4, 5, 4, 3, 3, 5])
    8
    >>> print_ans([9, 4, 6, 1, 9, 6, 10, 6, 6, 8])
    39
    >>> print_ans([1,1])
    0
    """
    ans = 0
    c = collections.Counter(lr)
    target = itertools.combinations(list(c.keys()), 3)
    for t in target:
        if check_tri(t[0], t[1], t[2]):
            tmp = (c[t[0]] * c[t[1]] * c[t[2]])
            ans += tmp
    print(ans)


if __name__ == '__main__':
    N = int(input().rstrip())
    lr = list(map(int, input().rstrip().split()))
    print_ans(lr)
# coding: utf-8
# Your code here!
def kitai(num):
    return (1+float(num))/2 
import numpy as np
l ={}
N,K = map(int,input().split())
#P = list(map(int,input().split()))
P = np.asarray(list(map(kitai,input().split())))
#print(P)

#print(P_)


    

#print(type(P_))


#print(P)
for i in range(0,N-K+1):
    #print(P[i:i+K])
    l[sum(P[i:i+K])]=i
#print(l)
max = max(l.keys())
print(max)










### FIXED CODE ###

#########行列読み込み ##############################################
"""
from sys import stdin
n = int(stdin.readline().rstrip())
data = [stdin.readline().rstrip().split() for _ in range(n)]
print(data)
print(*data, sep='\n')
"""
##################################################################
#########入力系####################################################
"""
s =input()
s=list(input())
a=int(input())
x,y = map(int,input().split())	
li = input().split()	
li = list(map(int,input().split()))	
li = input().split('T')	
"""
##################################################################

N,K = map(int,input().split())
def kitai(num):
    return (1+int(num))/2
P = list(map(kitai,input().split()))	  

S = [0]*(N+1)
ans = 0
for i in range(N):
    S[i+1]=S[i]+P[i]
for i in range(N-K+1):
    ans = max(ans,S[i+K]-S[i])
print(ans)
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]

dp = [[0 for _ in range(101)] for _ in range(10**5+10)]

for w in range(1, W+1):
    for n in range(N):
        Wi = wv[n][0]
        Vi = wv[n][1]
        if Vi <= w:
            dp[n+1][w] = max(dp[n][w], dp[n][w-Wi] + Vi)

print(dp[N][W+1])

### FIXED CODE ###

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

dp = [[0 for _ in range(W+10)] for _ in range(N+5)]

for w in range(1, W+1):
    for n in range(N):
        Wi = wv[n][0]
        Vi = wv[n][1]
        if Wi <= w:
            dp[n+1][w] = max(dp[n][w], dp[n][w-Wi] + Vi)
        dp[n+1][w] = max(dp[n][w], dp[n+1][w])

print(dp[N][W])
import itertools
A,B,C,n=map(int,input(),split())
l=[int(input()) for i in range(n)]
ll=[]
for p in itertools.product(['A','B','C','Z'].repeat=n):
  ans=0
  a=0
  b=0
  c=0
  for i in range(n):
    if p[i]=='A':
      a+=l[i]
    elif p[i]=='B':
      b+=l[i]
    elif p[i]=='C':
      c+=l[i]
  ans+=(abs(a-A)+abs(B-b)+abs(C-c))
  ll.append(ans)
print(min(ans))


### FIXED CODE ###

import itertools
n,A,B,C=map(int,input().split())
l=[int(input()) for i in range(n)]
ll=[]
for p in itertools.product(['A','B','C','Z'],repeat=n):
  ans=0
  a=0
  b=0
  c=0
  numa=0
  numb=0
  numc=0
  for i in range(n):
    if p[i]=='A':
      a+=l[i]
      numa+=1
    elif p[i]=='B':
      b+=l[i]
      numb+=1
    elif p[i]=='C':
      c+=l[i]
      numc+=1
  ans+=(abs(a-A)+abs(B-b)+abs(C-c)+(numa+numb+numc-3)*10)
  if all(nn!=0 for nn in [numa,numb,numc]):
    ll.append(ans)
print(min(ll))
a=input()

if a == ABC:
    print("ARC")
else:
    print("ABC")

### FIXED CODE ###

a=input()
 
if a == "ABC":
    print("ARC")
else:
    print("ABC")
n,m = map(int,input().split())


def judge():
    ans="-"*n
    for i in range(m):
        s,c = map(int,input().split())
        if ans[s-1]!="-" and int(ans[s-1])!=c:
            return -1
        else:
            a = list(ans)
            a[s-1] = str(c)
            ans = "".join(a)
    ans=ans.replace("-","0")
    if ans[s-1]==str(0):
        if n==1:
            return 0
        else:
            return -1
    return ans

print(judge())

### FIXED CODE ###

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


def judge():
    ans="-"*n
    if m==0:
        if n==1:
            return 0
    for i in range(m):
        s,c = map(int,input().split())
        if ans[s-1]!="-" and int(ans[s-1])!=c:
            return -1
        else:
            a = list(ans)
            a[s-1] = str(c)
            ans = "".join(a)
    if ans[0]=="-":
        a=list(ans)
        a[0]="1"
        ans="".join(a)
    ans=ans.replace("-","0")
    # print(ans[0])
    if ans[0]==str(0):
        if n==1:
            return 0
        else:
            return -1
    return ans

print(judge())
n,m,r=map(int,input().split());
a=n+r-n*m-1,b=r-n*m;
s=1;
if a<b||a<0||b<0:s=0;
else:
    if b>a-b:b=a-b;
	for i in range(b):s=s*(a-i)/(i+1);
print(s)


### FIXED CODE ###

n,m,r=map(int,input().split());
a=n+r-n*m-1;b=r-n*m;
s=1;
if a<b or a<0 or b<0:s=0;
else:
    if b>a-b:b=a-b;
    for i in range(b):s=s*(a-i)//(i+1);
print(s)
def gcd(a,b):
    if a>b:
        return gcd(b,a)
    if a==0:
        return b
    return gcd(b-a*(b//a),a)
def lcm(x,y):
    return (x*y)//gcd(x,y)
N=int(input())
A=list(map(input().split()))
s=1
for a in A:
    s=lcm(s,i)
ans=0
for a in A:
    ans+=s//i
print(ans%(10**9+7))

### FIXED CODE ###

def gcd(a,b):
    if a>b:
        return gcd(b,a)
    if a==0:
        return b
    return gcd(b-a*(b//a),a)
def lcm(x,y):
    return (x*y)//gcd(x,y)
N=int(input())
A=list(map(int,input().split()))
s=1
for a in A:
    s=lcm(s,a)
ans=0
for a in A:
    ans+=s//a
print(ans%(10**9+7))
k,x=map(int,input(),split())
print("Yes" if 500*k>=x else "No")

### FIXED CODE ###

k,x=map(int,input().split())
print("Yes" if 500*k>=x else "No")
import math

def make_plist(n):
	sqrt = int(math.sqrt(n))
	plist = [1]*(n/2+1)
	for i in range(2,int(math.sqrt(sqrt))+3):
		if plist[i]:
			plist[2*i::i] = [0 for x in range(2*i,n/2+1,i)]
	return plist

def get_pfact(plist,n):
	pfact = []
	sqrt = int(math.sqrt(n))
	for i in range(2,sqrt+3):
		if plist[i] and n%i == 0:
			pfact.append(i)
			if plist[n/i]:
				pfact.append(n/i)
	else:
		if len(pfact) == 0: pfact.append(n)
	return pfact

def get_phai(n,pfacts):
	phai = n
	for pfact in pfacts:
		phai *= (1-1/float(pfact))
	return int(phai)

# main	
n = int(raw_input())
plist = make_plist(n)
pfacts = get_pfact(plist,n)
print get_phai(n,pfacts)

### FIXED CODE ###

def phi(n):
	r = n
	i = 2
	while i*i <= n:
		if n%i==0:
			r -= r/i
			while n%i==0:
				n /= i
		i += 1
	if n>1: r-= r/n
	return r

n = int(raw_input())
print phi(n)
from math import gcd
N = 1000001
sieve = [-1] * (N + 1)
sieve[0] = sieve[1] = 0
for i in range(N + 1):
    if sieve[i] != -1:
        continue
    else:
        index = i * i
        while True:
            if index > N:
                break
            sieve[index] = i
            index += i

isCounted = [0] * 1000001
isPairwiseCoprime = True
M = int(input())
A = map(int,input().split())
for i in range(M):
    elem = A[i]
    if elem == 1:
        continue
    primeList = []
    while sieve[elem] != -1:
        primeList.append(sieve[elem])
        elem //= sieve[elem]
    primeList.append(elem)
    for elem1 in primeList:
        if isCounted[elem1] != 0:
            isPairwiseCoprime = False
            break
    if not isPairwiseCoprime:
        break
    for elem1 in primeList:
        isCounted[elem1] += 1
if isPairwiseCoprime:
    print("pairwise coprime")
else:
    curGcd = A[0]
    for elem in A:
        curGcd = gcd(elem,curGcd)
    if curGcd == 1:
        print("setwise coprime")
    else:
        print("not coprime")


### FIXED CODE ###

from math import gcd
N = 1000001
sieve = [-1] * (N + 1)
sieve[0] = sieve[1] = 0
for i in range(N + 1):
    if sieve[i] != -1:
        continue
    else:
        index = i * i
        while True:
            if index > N:
                break
            sieve[index] = i
            index += i

isCounted = [0] * 1000001
isPairwiseCoprime = True
M = int(input())
A = list(map(int,input().split()))
for i in range(M):
    elem = A[i]
    if elem == 1:
        continue
    primeList = []
    while sieve[elem] != -1:
        primeList.append(sieve[elem])
        elem //= sieve[elem]
    primeList.append(elem)
    for elem1 in primeList:
        if isCounted[elem1] != 0:
            isPairwiseCoprime = False
            break
    if not isPairwiseCoprime:
        break
    for elem1 in primeList:
        isCounted[elem1] += 1
if isPairwiseCoprime:
    print("pairwise coprime")
else:
    curGcd = A[0]
    for elem in A:
        curGcd = gcd(elem,curGcd)
    if curGcd == 1:
        print("setwise coprime")
    else:
        print("not coprime")
n = int(input())
t = list(map(int, input().split())
t = [0] + t
maxRed = 0
for _ in range(int(input())):
    p, x = map(int, input().split())
	maxRed = max(maxRed, t[p]-x)
print(sum(t)-maxRed)

### FIXED CODE ###

n = int(input())
t = [0] + list(map(int, input().split()))

summ = sum(t)

for _ in range(int(input())):
    p, x = map(int, input().split())
    print(summ + x-t[p])
a, b, x = map(int, input().split())

def cal(n):
    return a*n + b*len(str(n))

l = 0
r = 10**9+1

while r-l > 1:
    n = (l+r) // 2
    if cal(n) >= x:
        r = n
    else:
        l = n

print(n)

### FIXED CODE ###

s = input()
if s == "SUN":
  print(7)
elif s == "MON":
  print(6) 
elif s == "TUE":
  print(5)
elif s == "WED":
  print(4)
elif s == "THU":
  print(3)
elif s == "FRI":
  print(2)
else:
  print(1)
n=int(input())
p=list(map(int,input().split()))
#print(n)
#print(p)
i=1
l=[]
while i<n-1:
  if p[i-1]<p[i]<p[i+1] or p[i-1]>p[i]>p[i+1]:
    l.append(i)
  else:
    pass
  i+=1
print(len(l))


### FIXED CODE ###

s=input()
a=s[0]
b=s[1]
c=s[2]
d=s[3]
if a==b and c==d and a!=c:
  print("Yes")
elif a==c and b==d and a!=b:
  print("Yes")
elif a==d and b==c and a!=b:
  print("Yes")
else:
  print("No")
N,K,Q=map(int,input().split())
point=[K]*n
for i in range(Q):
  A=int(input())
  A=A-1
  point[A]+=1
for j in range(N):
  if point[j]>Q:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

N,K,Q=map(int,input().split())
point=[K]*N
for i in range(Q):
  A=int(input())
  A=A-1
  point[A]+=1
for j in range(N):
  if point[j]>Q:
    print("Yes")
  else:
    print("No")
import numpy as np
def solve(N, K, A):
    numbers = {}
    for a in A:
        numbers[a] = numbers.get(a, 0) + 1
    M = len(numbers)
    if M <= K:
        return 0
    dp = np.full((M+1, M+1), N)
    dp[0,:] = 0
    for i, n in enumerate(numbers.values()):
        for j in range(M+1):
            if j > 0:
                dp[i+1,j] = min(dp[i+1,j], dp[i,j-1], dp[i,j] + n)
            else:
                dp[i+1,j] = min(dp[i+1,j], dp[i,j] + n)
    return min(dp[M,:K+1])

if __name__ == "__main__":
    N, K = map(int, raw_input().split())
    A = map(int, raw_input().split())
    print solve(N, K, A)

### FIXED CODE ###

def solve(N, K, A):
    numbers = {}
    for a in A:
        numbers[a] = numbers.get(a, 0) + 1
    if len(numbers) <= K:
        return 0
    return N - sum(sorted(numbers.values(), key=lambda x: -x)[:K])
N, K = map(int, raw_input().split())
A = map(int, raw_input().split())
print solve(N, K, A)
import math
          
def koch(n, h, i, j, k):
 if n == 0:
  return
           
 s.x = (h*2+j)/3
 s.y = (i*2+k)/3
 t.x = (h+j*2)/3
 t.y = (i+k*2)/3
 u.x = (t.x-s.x)*math.cos(math.pi/3) - (t.y-s.y)*math.sin(math.pi/3) + s.x
 u.y = (t.x-s.x)*math.sin(math.pi/3) + (t.y-s.y)*math.cos(math.pi/3) + s.y
   
n = input()
          
px = float(0)
py = float(0)
qx = float(100)
qy = float(0)
          
print px, py
koch(n, px, py, qx, qy)
print qx, qy

### FIXED CODE ###

import math
          
def koch(n, h, i, j, k):
 if n == 0:
  return
           
 sx = (h*2+j)/3
 sy = (i*2+k)/3
 tx = (h+j*2)/3
 ty = (i+k*2)/3
 ux = (tx-sx)*math.cos(math.pi/3) - (ty-sy)*math.sin(math.pi/3) + sx
 uy = (tx-sx)*math.sin(math.pi/3) + (ty-sy)*math.cos(math.pi/3) + sy
          
 koch(n-1, h, i, sx, sy)
 print sx, sy
 koch(n-1, sx, sy, ux, uy)
 print ux, uy
 koch(n-1, ux, uy, tx, ty)
 print tx, ty
 koch(n-1, tx, ty, j, k)
   
n = input()
          
px = float(0)
py = float(0)
qx = float(100)
qy = float(0)
          
print px, py
koch(n, px, py, qx, qy)
print qx, qy
n,m=map(int,input().split())
a=[]
for i in range(n):
  a.append(input())
ans=[0]*(n+1)
for i in range(n):
  for j in range(m):
    if a[i][j]==".":
      ans[j+1]+=ans[j]
    else :
      ans[j+1]=0
print(ans[m])

### FIXED CODE ###

n,m=map(int,input().split())
a=[]
for i in range(n):
  a.append(input())
ans=[0]*(m+1)
ans[1]=1
for i in range(n):
  for j in range(m):
    if a[i][j]==".":
      ans[j+1]+=ans[j]
      ans[j+1]%=1000000007
    else :
      ans[j+1]=0
print(ans[m])
import collections

N = int(input())
vote_list = [input() for i in range(N)]
vote_list.sort()

count = collections.Counter(vote_list)
max_count = count.most_common()[0][1]

if max_count == 1:
    for i in vote_list:
        print(i)
else:
    i = 0
    while count.most_common()[i][1] == max_count:
        print(count.most_common()[i][0])
        i = i + 1


### FIXED CODE ###

import collections

N = int(input())
vote_list = [input() for i in range(N)]
vote_list.sort()

count = collections.Counter(vote_list)
max_count = count.most_common()[0][1]
ans = []

for alpha, beta in count.items():
    if beta == max_count:
        ans.append(alpha)
ans.sort()
print("\n".join(ans))
A, B, C = map(int, input().split())

if A + B + C >= 22
    print("bust")
else:
    print(win)

### FIXED CODE ###

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

if A + B + C >= 22:
    print("bust")
else:
    print("win")
n=int(input())
dat=list(map(int, input().split()))

for e in dat:
       e = bin(e)[2:]
       e = list(e).reverse()

re=[]

for e in dat:
      try:
          w=e.index('1')
          re.append(w)
       except ValueError:
          re.append(0)

print(min(re))

### FIXED CODE ###

import sys

def main():
    N = int(input())
    A = [int(_) for _ in input().split()]

    t = 0
    while True:
        for i in range(N):
            if A[i] % 2 == 0:
                A[i] //= 2
            else:
                print(t)
                sys.exit()
        t += 1

main()
mat = []

for i in range(3):
  a = list(map(int, input().split()))

ans = False
if mat[1][0] - mat[0][0] == mat[1][1] - mat[0][1] == mat[1][2] - mat[0][2]:
  if mat[2][0] - mat[0][0] == mat[2][1] - mat[0][1] == mat[2][2] - mat[0][2]:
    ans = True

if ans:
  print("Yes")
else:
  print("No")
  


### FIXED CODE ###

mat = []
 
for i in range(3):
  a = list(map(int, input().split()))
  mat.append(a)
  
ans = False
if mat[1][0] - mat[0][0] == mat[1][1] - mat[0][1] == mat[1][2] - mat[0][2]:
  if mat[2][0] - mat[0][0] == mat[2][1] - mat[0][1] and mat[2][1] - mat[0][1] == mat[2][2] - mat[0][2]:
    ans = True
 
if ans:
  print("Yes")
else:
  print("No")
N = int(input())
D = list(map(int, input().split()))

for x in range(N):
  for y in range(x+1,N):
    ans += D[x] * D[y]

print(ans)



### FIXED CODE ###

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

ans = 0
for x in range(N):
  for y in range(x+1,N):
    ans += D[x] * D[y]

print(ans)
N=int(input())
a_list=[]
a_list = list(map(int, input().split())) # "1 2 3"と入力
min_num=min(a_list)
nokori_list=[i%min_num for i in a_list if i%min_num!=0]

if len(nokori_list)==0:
    print(min_num)
else:
    can_min=min(nokori_list)
    futuer_min=min_num%can_min
    while futuer_min>0:
        big=max(can_min,futuer_min)
        small=min(can_min,futuer_min)
        futuer_min=big%small
        if futuer_min==0:
            answer=small
            break
        answer=small
    print(answer)

### FIXED CODE ###

N=int(input())
a_list=[]
a_list = list(map(int, input().split())) # "1 2 3"と入力
min_num=min(a_list)
nokori_list=[i%min_num for i in a_list if i%min_num!=0]
if len(nokori_list)==0:
    print(min_num)
else:    
    while len(nokori_list)!=0:
        if len(nokori_list)==0:
            answer=min_num
            break
        else:
            nokori_list.append(min_num)
            min_num=min(nokori_list)
            new_list=[i%min_num for i in nokori_list if i%min_num!=0]
            nokori_list=new_list
        answer=min_num
    print(answer)
N, K = [int(c) for c in input().split()]
S = [int(c) for c in input()]

longest=0

for bgn_flip in range(len(S)):

    S_copy=S[:]
    zero=False
    icluster=-1
    for i,s in enumerate(S):
        if s==0 and zero==False:
            zero=True
            icluster+=1
        if s==1:
            zero=False

        if s==0 and icluster>=bgn_flip and icluster < bgn_flip+K:
       	    S_copy[i]=1

    seq=0
    for sc in S_copy:
        if sc==1: seq+=1
        if sc==0: seq=0
        if seq>longest:longest=seq

print(longest)

### FIXED CODE ###

A,B = [int(c) for c in input().split()]
if A>B:
    print(A*2-1)
elif A==B:
    print(A*2)
else:
    print(B*2-1)
raw_input()
 print((x) * 3)

### FIXED CODE ###

x = input()
print(int(x) ** 3)
def comb(a, b, mod):
    if a // 2 < b:
        b = a - b
    t = 1
    for i in range(b):
        t *= (a - i) % mod
    s = 1
    for i in range(1, b + 1):
        s *= i % mod
    return (t // s) % mod



N, K = map(int, input().split())
r = N - K
mod = 1000000007

if K > N // 2:
    

for i in range(1, K + 1):
    print(comb(r + 1, i, mod) * comb(K - 1, i - 1, mod) % mod)
    
    




### FIXED CODE ###

def comb(a, b, mod):
    if a < b :
        return 0
    if (a // 2) < b:
        x = a - b
        # print(f'{b}　→ {x}')
        b = x
    t = 1
    for i in range(b):
        t *= (a - i) % mod
    s = 1
    for i in range(1, b + 1):
        s *= i % mod
    return (t // s) % mod

N, K = map(int, input().split())
r = N - K
mod = 1000000007

for i in range(1, K + 1):
        first = comb(r + 1, i, mod)
        if first == 0:
            second = 0
        else:
            second = comb(K - 1, i - 1, mod)
        print(first * second % mod)
from collections import Counter
n=int(input())
A=list(map(int,input().split()))
q=int(input())
BC=[list(map(int,input().split())) for _ in range(q)]

num=sum(A)
N={i+1:0 for i in range(9)}
for i in A:
    N[i] +=1

for b,c in BC:
    dig=c-b
    num +=dig*N[b]
    print(num)
    if c not in N:N[c]=0
    N[c] +=N[b]
    N[b]=0

### FIXED CODE ###

from collections import Counter
n=int(input())
A=list(map(int,input().split()))
q=int(input())
BC=[list(map(int,input().split())) for _ in range(q)]

num=sum(A)
N={}
for i in A:
   if i not in N:N[i]=0
   N[i] +=1

for b,c in BC:
    if b not in N:
        print(num)
        continue
    dig=c-b
    num +=dig*N[b]
    print(num)
    if c not in N:N[c]=0
    N[c] +=N[b]
    N[b]=0
import os

def qcount(s,t,count):
    if s=="?" or s==t:
        count += 1
        return count
    else:
        return 0

S = list(input())
T = list(input())
count = 0
i = 0
result =False

if len(S)>=len(T):
    while len(S)-i:
        count = qcount(S[i],T[count],count)
        if count == len(T):
            i = len(S)-1
            result = True
            for j in range(len(T)):
                S[i-count+j+1] = T[j]
            for k in range(len(S)):
                if S[k]=="?":
                    S[k] = "a"
    i += 1
if result:
    print("".join(S))
else:
    print("UNRESTORABLE")


### FIXED CODE ###

import os

s = list(map(str,input()))
t = list(map(str,input()))

m = len(s)
n = len(t)
ans = 0

if m<n:
    print("UNRESTORABLE")
    exit()
for i in range(m-n+1):
    s2 = s.copy()
    s1 = s2[i:i+n]
    flag = True
    for j in range(n):
        if s1[j]!="?" and s1[j]!=t[j]:
            flag = False
            break
        else:
            s1[j] = t[j]
    if flag:
        s2[i:i+n] = s1
        s2 = "".join(s2)
        a = s2.replace("?","a")
        if ans==0:
            ans = a
        elif ans > a:
            ans = a
if ans==0:
    print("UNRESTORABLE")
else:
    print(ans)
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict


## input
N,Q = map(int, input().split())
cnt = [0 for _ in range(N)]
route = defaultdict(lambda:set([]))
for _ in range(N-1):
  a,b = map(int, input().split())
  route[a-1].add(b-1)
  route[b-1].add(a-1)
for _ in range(Q):
  p,x = map(int, input().split())
  cnt[p-1] += x

## solve
def dfs(p,q):
  for r in route[q]:
    if p != r:
      cnt[r] += cnt[q]
      dfs(q,r)

dfs(-1,0)
print(" ".join([str(c) for c in cnt]))

### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict,deque


## input
N,Q = map(int, input().split())
cnt = [0 for _ in range(N)]
route = defaultdict(lambda:set([]))
for _ in range(N-1):
  a,b = map(int, input().split())
  route[a-1].add(b-1)
  route[b-1].add(a-1)
for _ in range(Q):
  p,x = map(int, input().split())
  cnt[p-1] += x

## solve
stk = deque([0])
cost = [-1 for _ in range(N)]
cost[0] = cnt[0]
while len(stk) > 0:
  p = stk.pop()
  for q in route[p]:
    if cost[q] >= 0:
      continue
    cost[q] = cost[p] + cnt[q]
    stk.append(q)

print(*cost)