Harryxun/stf_run huggingface dataset:
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    for i in range(min(K,100)):
        dm = [0]*N
        for x in range(N):
            dm[max(x - A[x],0)]+=1
            if x+A[i]+1<N:
                dm[x+A[x]+1]+=-1
        for j in range(1,N):
            dm[j]=dm[j-1]+dm[j]
        A[:] = dm[:]
    print(*A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    for i in range(min(K,50)):
        dm = [0]*N
        for x in range(N):
            dm[max(x - A[x],0)]+=1
            if x+A[x]+1<N:
                dm[x+A[x]+1]+=-1
        for j in range(1,N):
            dm[j]=dm[j-1]+dm[j]
        A[:] = dm[:]
    print(*A)

if __name__ == '__main__':
    main()
A,B,C,D,E,F=map(int,input().split())
maxx=0
s=1
t=0
for i in range(F//(100*B)+1):
    for j in range((F-i*100*B)//(100*A)+1):
        for k in range(((i*B+j*A)*E)//D+1):
            for l in range (((i*B+j*A)*E-k*D)//C+1):
                if i==0 and j==0 and k==0 and l==0:
                    continue
                if (100*(i*B+j*A)+k*D+l*C)>F:
                    break
                elif (k*D+l*C)/(k*D+l*C+100*(i*B+j*A))>maxx:
                    maxx=(k*D+l*C)/(k*D+l*C+100*(i*B+j*A))
                    s=(k*D+l*C+100*(i*B+j*A))
                    t=k*D+l*C

print(s,t)


### FIXED CODE ###

N=int(input())
A=int(input())
print(N*N-A)
ans = 1
    while True :
        if ans < 0 :
            print(abs(ans))
            break
        ans = N - K
        N = ans

### FIXED CODE ###

n, k = map(int, input().split())
if n==0 or k==1:
    print(0)
    exit()
elif n<k:
    print(min(n, abs(n-k)))
    exit()
elif n % k == 0:
    print(0)
    exit()
else:
    mx = n%k
print(min(abs(mx-k), mx))
N,X = map(int,input().split())
L = list(map(int,input().split()))
D,i,cnt = 0,0,0
while(D <= X):
  D = D + L[i]
  cnt +=1
  i += 1
print(cnt)

### FIXED CODE ###

N,X = map(int,input().split())
L = list(map(int,input().split()))
L.append(0)
D,i,cnt = 0,0,0
while(D <= X and cnt <= N):
  D = D + L[i]
  cnt +=1
  i += 1
print(cnt)
def divbin(s,res):
  if int(s,2)==0:
    v=res
    return v
  # ss=int(s)
  val=int(s,2)
  count=bin(val).count("1")
  val%=count
  # t_str=bin(str(count))
  t_str=bin(val)
  t_str=t_str.replace("0b","")
  res+=1
  return divbin(t_str,res)

from copy import deepcopy
n=int(input())
x=input()

# c=str(bin(n))
# c=c.replace("0b","")
s=x
vv=int(s,2)
p=int(x)
cnt=bin(p).count("1")
x=list(x)
# print(cnt)
for i in range(len(x)):
  tmp=cnt
  ts=""
  vv-=2**(i-1)
  if x[i]=="1":
    vv-=2**(i-1)
  else:
    vv+=2**(i-1)
  # ans=0
  # global ans
  ts=bin(vv)
  ts=ts.replace("0b","")
  ans=0
  ans=divbin(ts,ans)
  print(ans)



### FIXED CODE ###

n=int(input())
x=input()
val=int(x,2)

cnt=x.count("1")
p_cnt=cnt+1
m_cnt=cnt-1
p_amari,m_amari=0,0

p_amari=val%(cnt+1)
if cnt-1!=0:
  m_amari=val%(cnt-1)
else:
  m_amari=0

for i in range(n):
  ans=0
  if x[i]=="0":
    amari=p_amari+pow(2,n-i-1,p_cnt)
    amari%=p_cnt
  elif x[i]=="1":
    if cnt-1==0:
      print(0)
      continue
    amari=m_amari-pow(2,n-i-1,m_cnt)
    amari%=m_cnt
  ans+=1
  while amari!=0:
    amari%=bin(amari).count("1")
    ans+=1
  print(ans)
b=int(input())
a = [int(i) for i in input().split()]
a.insert(0,0)
c=0
for i in range(b):
  if a[i] > a[i+1]:
    a[i] -= 1
  elif a[i] == a[i+1]:
    for j in range(b):
      if a[i+j] > a[i+j+1]:
        for k in range(j+1):
          a[i+k] -= 1
        break
      elif a[i+j] == a[i+j+1]:
        continue
      else:
        break
    else:
      break
    break

for i in range(b):
  if a[i] > a[i+1]:
    print('No')
    exit()
print('Yes')    

### FIXED CODE ###

b=int(input())
a = [int(i) for i in input().split()]
a.insert(0,0)
for i in range(1,b+1):
  if a[i-1] == a[i]:
    continue
  else:
    a[i] -= 1

for i in range(b):
  if a[i] > a[i+1]:
    print('No')
    exit()
print('Yes')
#import collections
import sys
input = sys.stdin.readline

#n = int(input())
#l = list(map(int, input().split()))

'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''


n,m=map(int, input().split())
fibo = [1, 1]
for i in range(1, 10**5+1):
    fibo.append(fibo[i]+fibo[i-1])
#print(fibo)
a=[]
for i in range(m):
    a.append(int(input()))

flg=True
for i in range(m-1):
    if a[i]+1==a[i+1]:
        flg=False
        break
#print(a[0]==a[1],flg)
if not flg:
    print(0)
else:
    ans=1
    if m==1:
        #print(fibo[a[0]-1],fibo[n-a[0]-1])
        print(fibo[a[0]-1]*fibo[n-a[0]-1] % (10**9+7))
    else:
        for i in range(1,m):
            #print(a[i],a[i-1])
            #print(fibo[21])
            #print(fibo[a[i]-a[i-1]-1])
            ans*=fibo[a[i]-a[i-1]-2]
            print(ans % (10**9+7))

        #print(fibo[a[0]-1],fibo[n-a[m-1]-1],fibo[10])
        print(ans*fibo[a[0]-1]*fibo[n-a[m-1]-1]%(10**9+7))




### FIXED CODE ###

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

#n = int(input())
#l = list(map(int, input().split()))

'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

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

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

a=[]
for i in range(m):
    a.append(int(input()))

flg=True
for i in range(m-1):
    if a[i]+1==a[i+1]:
        flg=False
        break

if not flg:
    print(0)

else:
    ans=1
    if m==1:
        print(fibo[a[0]-1]*fibo[n-a[0]-1] % (10**9+7))

    elif m==0:
        print((fibo[n]) % (10**9+7))

    else:
        for i in range(1,m):
            ans*=fibo[a[i]-a[i-1]-2]   
        print(ans*fibo[a[0]-1]*fibo[n-a[m-1]-1]%(10**9+7))
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N = int(rl())
    ga, sa, ba = map(int, rl().split())
    gb, sb, bb = map(int, rl().split())
    
    dp1 = [0] * 10001
    dp1[0] = N
    M = N
    for i in range(N + 1):
        dp1[i + ga] = max(dp1[i + ga], dp1[i] - ga + gb)
        dp1[i + sa] = max(dp1[i + sa], dp1[i] - sa + sb)
        dp1[i + ba] = max(dp1[i + ba], dp1[i] - ba + bb)
        M = max(M, dp1[i])
    
    dp2 = [0] * 10001
    dp2[0] = M
    ans = M
    for i in range(M + 1):
        dp2[i + gb] = max(dp2[i + gb], dp2[i] - gb + ga)
        dp2[i + sb] = max(dp2[i + sb], dp2[i] - sb + sa)
        dp2[i + bb] = max(dp2[i + bb], dp2[i] - bb + ba)
        ans = max(ans, dp2[i])
    print(ans)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N = int(rl())
    ga, sa, ba = map(int, rl().split())
    gb, sb, bb = map(int, rl().split())
    
    dp1 = [0] * 30000000
    dp1[0] = N
    M = N
    for i in range(N + 1):
        dp1[i + ga] = max(dp1[i + ga], dp1[i] - ga + gb)
        dp1[i + sa] = max(dp1[i + sa], dp1[i] - sa + sb)
        dp1[i + ba] = max(dp1[i + ba], dp1[i] - ba + bb)
        M = max(M, dp1[i])
    
    dp2 = [0] * 30000000
    dp2[0] = M
    ans = M
    for i in range(M + 1):
        dp2[i + gb] = max(dp2[i + gb], dp2[i] - gb + ga)
        dp2[i + sb] = max(dp2[i + sb], dp2[i] - sb + sa)
        dp2[i + bb] = max(dp2[i + bb], dp2[i] - bb + ba)
        ans = max(ans, dp2[i])
    print(ans)


if __name__ == '__main__':
    solve()
X,K=input().split()
if 500*X >= K:
  print("Yes")
else*
  print("No")

### FIXED CODE ###

K,X=map(int,input().split())
if 500*K >= X:
  print("Yes")
else:
  print("No")
import sys
import time

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    import numpy as np
    l, a, b, m = list(map(int, readline().split()))
    d_min = len(str(a))
    d_max = len(str(a + (l - 1) * b))
    count_d = [-1] * 19

    prev = -1
    for i in range(d_min, d_max + 1):
        power = 10 ** i
        ok = 0
        ng = l + 1
        while abs(ng - ok) > 1:
            mid = (ok + ng) // 2
            x = a + mid * b
            if x < power:
                ok = mid
            else:
                ng = mid
        ok = min(ok, l - 1)
        count_d[i] = ok - prev
        prev = ok

    res = np.array([0, a, 1], dtype="int64")

    for i in range(19):
        count = count_d[i]
        if count == -1:
            continue
        mat = np.array([[10 ** i, 0, 0],
                        [1, 1, 0],
                        [0, b, 1]], dtype="int64")
        mat = np.mod(mat,m)
        cur = np.eye(3, dtype="int64")
        count_bit = format(count, "b")
        for bit in count_bit[::-1]:
            if bit == "1":
                cur = cur @ mat
                cur = np.mod(cur, m)
            mat = mat @ mat
            mat = np.mod(mat, m)
        res = res @ cur
        res = np.mod(res, m)

    print(res[0])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import time

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    import numpy as np
    l, a, b, m = list(map(int, readline().split()))
    d_min = len(str(a))
    d_max = len(str(a + (l - 1) * b))
    count_d = [-1] * 19

    prev = -1
    for i in range(d_min, d_max + 1):
        power = 10 ** i
        ok = 0
        ng = l + 1
        while abs(ng - ok) > 1:
            mid = (ok + ng) // 2
            x = a + mid * b
            if x < power:
                ok = mid
            else:
                ng = mid
        ok = min(ok, l - 1)
        count_d[i] = ok - prev
        prev = ok

    res = np.array([0, a, 1], dtype="int64")
    res = np.mod(res, m)

    for i in range(19):
        count = count_d[i]
        if count == -1:
            continue
        mat = np.array([[10 ** i, 0, 0],
                        [1, 1, 0],
                        [0, b, 1]], dtype="int64")
        mat = np.mod(mat, m)
        cur = np.eye(3, dtype="int64")
        count_bit = format(count, "b")
        for bit in count_bit[::-1]:
            if bit == "1":
                cur = np.dot(cur, mat)
                cur = np.mod(cur, m)
            mat = np.dot(mat, mat)
            mat = np.mod(mat, m)
        res = np.dot(res, cur)
        res = np.mod(res, m)

    print(res[0])


if __name__ == '__main__':
    main()
a,b,k = map(int, input().split())
l =[]
if a <= b:
    for i in range(1,a):
        if a % i == 0  and b % i == 0:
            l.append(i)
else:
    for i in range(1,b):
        if a % i == 0  and b % i == 0:
            l.append(i)
print(l[k-1])


### FIXED CODE ###

a,b,k = map(int, input().split())
l =[]
if a <= b:
    for i in range(1,a + 1):
        if a % i == 0  and b % i == 0:
            l.append(i)
else:
    for i in range(1,b + 1):
        if a % i == 0  and b % i == 0:
            l.append(i)
print(l[len(l)-k])
x, y = map(int, input().split())
ans = 10 ** 9 + 3
if y >= x:
    ans = min(ans, abs(y - x))
if - y >= x:
    ans = min(ans, abs(-y - x) + 1)
if y >= -x:
    ans = min(ans, abs(y + x) + 1)
if - y >= -x:
    ans(min(ans, abs(-y + x) + 2))
print(ans)

### FIXED CODE ###

x, y = map(int, input().split())
if abs(y) > abs(x):
    if (x >= 0 and y > 0):
        print(abs(y - x))
    elif x * y <= 0:
        print(abs(y) - abs(x) + 1)
    else:
        print(abs(y) - abs(x) + 2)
else:
    if x > 0 and y > 0:
        print(x - y + 2)
    elif x * y < 0 or (y == 0 and x > 0):
        print(abs(x) - abs(y) + 1)
    else:
        print(abs(x - y))
N = int(input())                                                                                                                                                                                                  
for i in range(N):
    W.append(input())

prev = W[0]

answer = "Yes"

for w in W[1:]:
    if prev[-1] != w[0]:
        answer = "No"

print(answer)                                                           

### FIXED CODE ###

N = int(input())
words = [input().strip() for _ in range(N)]

def solve(words):
  s = {words[0]}
  for p, w in zip(words, words[1:]):
    if p[-1] != w[0]:
      return "No"
    if w in s:
      return "No"
    s.add(w)
  return "Yes"

print(solve(words))
N = int(input())
P = 1
for n in range(1,N + 1):
    P = P * n
print(P %% ((10**9) + 7))

### FIXED CODE ###

N = int(input())
P = 1
for n in range(1,N + 1):
    P = (P * n) % ((10**9)+7)
print(P)
import numpy as np

N, Q=map(int, input().split())
matrix=np.zeros((N, N))
point=np.zeros(N)

for i in range(N-1):
  a, b=map(int, input().split())
  matrix[a-1, b-1]=1
  
for i in range(Q):
  p, x=map(int, input().split())
  point[p-1]+=x
  
for i in range(N-1):
  point+=matrix[i, :]*point[i]
  
print(' '.join(map(str, map(int, point.tolist()))))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

def input():
  return sys.stdin.readline()[:-1]

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

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

px=[list(map(int, input().split())) for i in range(Q)]

counter=[0]*(N+1)
for i in range(Q):
  counter[px[i][0]]+=px[i][1]
  
def f(num, prenum=-1, p=0):
  counter[num]+=p
  for postnum in link[num]:
    if postnum==prenum:
      continue
    f(postnum, num, counter[num])
    
f(1)

print(*counter[1:])
N = int(input())
if N % 2 ==0:
  print(0.5)
else:
  print((N+1)/2N)

### FIXED CODE ###

N = int(input())
if N % 2 ==0:
  ans = 0.5
else:
  ans = (N+1)/(2*N)
print(ans)
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
s=0
for i in range(0,N):
  s+=B[A[i]-1]
  if i>=1 and A[i]==A[i-1}+1:
    s+=C[i-1]
print(s)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
s=0
temp=""
for i in A:
  s+=B[i-1]
  if temp==i-1:
    s+=C[temp-1]
  temp=i
print(s)
import sys

def main():
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    n, q = map(int, input().split())
    #n, q = map(int, "4 3".split())
    g = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        #a, b = map(int, ["1 2", "2 3", "2 4"][i].split())
        g[a-1].append(b-1)
        g[b-1].append(a-1)


    add = [0] * n
    for i in range(q):
        p, v = map(int, input().split())
        #p, v = map(int, ["2 10", "1 100", "3 1"][i].split())
        #dfs(p-1, v)
        add[p-1] += v

    ans = [0] * n
    def dfs()
    def dfs(v,p,value): #p: parent of v
        value += add[v]
        ans[v] = value
        for c in g[v]:
            if c == p: continue
            dfs(c,v,value)
    dfs(0, -1, 0)
    """
    def dfs(start, point):
        stack = [start]
        while stack:
            x = stack.pop()
            ans[x] += point
            stack += g[x]
    """

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

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

def main():
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    n, q = map(int, input().split())
    #n, q = map(int, "4 3".split())
    g = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        #a, b = map(int, ["1 2", "2 3", "2 4"][i].split())
        g[a-1].append(b-1)
        g[b-1].append(a-1)


    add = [0] * n
    for i in range(q):
        p, v = map(int, input().split())
        #p, v = map(int, ["2 10", "1 100", "3 1"][i].split())
        #dfs(p-1, v)
        add[p-1] += v

    ans = [0] * n
    def dfs(v,p,value): #p: parent of v
        value += add[v]
        ans[v] = value
        for c in g[v]:
            if c == p: continue
            dfs(c,v,value)
    dfs(0, -1, 0)
    """
    def dfs(start, point):
        stack = [start]
        while stack:
            x = stack.pop()
            ans[x] += point
            stack += g[x]
    """

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

if __name__ == '__main__':
    main()
# D - XOR World
# https://atcoder.jp/contests/abc121/tasks/abc121_d

def two2ten(two):
    base = 1
    ten = 0
    for i in two:
        ten += i*base
        base *= 2
    return ten

def ten2two(ten):
    two = list()
    while ten > 0:
        two.append(ten%2)
        ten /= 2
    return two

def find_first_1(two):
    for two_id in range(len(two)):
        if two[two_id] == 1:
            return two_id

A, B = map(int, raw_input().split())
b = ten2two(B)
pos1 = find_first_1(b)
ret = [0]*len(b)
t = B - A + 1

while t > 0:
    for b_id in range(len(b)):
        ret[b_id] += b[b_id]

    b[pos1] = 0
    for b_id in range(0, pos1):
        b[b_id] = 1

    pos1 = find_first_1(b)
    t -= 1

for ret_id in range(len(ret)):
    ret[ret_id] %= 2

print '{}'.format(two2ten(ret))


### FIXED CODE ###

# D - XOR World
# https://atcoder.jp/contests/abc121/tasks/abc121_d


def xor_from0(n):
    if n % 4 == 0:
        return n
    elif n % 4 == 1:
        return 1
    elif n % 4 == 2:
        return n+1
    else: # n % 4 == 3
        return 0

A, B = map(int, raw_input().split())
print '{}'.format(xor_from0(A-1) ^ xor_from0(B))
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    if a[i] % 2 == 0:
        if a[i] % 3 == 0 or a[i] % 5 == 0:
            pass
        else:
            print("DENIED")
            exit()
print("APPROVED")

### FIXED CODE ###

abc = list(map(int, input().split()))
a = len(set(abc))
if len(set(abc)) == 2:
    print("Yes")
    exit()
print("No")
class Dice:
    def __init__(self, f):
        self.f = f
        # f = face := (top, sud, est, west, nord, botm)

    
    dict = {'S' : (4, 0, 2, 3, 5, 1), \
            'E' : (3, 1, 0, 5, 4, 2), \
            'W' : (3, 1, 2, 3, 4, 5), \
            'N' : (1, 5, 2, 3, 0, 4) }
    
    def turn(self, c):
                 # c = command := 'NSEWs'
        for i in range(len(c)):
            f = [f[j] for j in dict[c[i]]]


face = list(map(int, input().strip().split()))
Dice(face).turn(input())
print(face[0])

### FIXED CODE ###

op = {'N':(1,5,2,3,0,4), 'S':(4,0,2,3,5,1), 'E':(3,1,0,5,4,2), 'W':(2,1,5,0,4,3)}
f = input().split()
for i in input():
    f = [f[j] for j in op[i]]
print(f[0])
import sys
input = sys.stdin.readline
# 昇順ソートされた配列の挿入位置indexを返す O(logN)
from bisect import bisect_left

def isOver(A,x):
	cnt = 0
	for a in A:
		cnt += n-bisect_left(A,x-a)
	return cnt

def calOut(A,s,x):
	for a in A:
		idx = bisect_left(A,x-a)
		out += s[n]-s[idx]+a*(n-idx)
	return out - (isOver(A,n,x)-m)*x

def calX(A,m,l,r):
	while r-l>1:
		# x: 握手で得たい最低パワー値
		x = (l+r)//2
		if isOver(A,x) >= m:
			l = x
		else: #握手する限界回数すら満たせないほど大きいxなら
			r = x 
	return l

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

#累積和の下準備
a.sort()
s = [0]*(n+1)
for i in range(n):
	s[i+1] = s[i]+a[i]

x = calX(a,m,a[0]*2,a[n-1]*2)

print(calOut(a,s,x))

### FIXED CODE ###

import sys
input = sys.stdin.readline
# 昇順ソートされた配列の挿入位置indexを返す O(logN)
from bisect import bisect_left

def isOver(a,n,x):
	cnt = 0
	for i in range(n):
		cnt += n-bisect_left(a,x-a[i])
	return cnt

def calX(a,n,m,l,r):
	while r-l>1:
		# x: 握手で得たい最低パワー値
		x = (l+r)//2
		if isOver(a,n,x) >= m:
			l = x
		else: #握手する限界回数すら満たせないほど大きいxなら
			r = x 
	return l

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

#累積和の下準備
a.sort()
s = [0]*(n+1)
for i in range(n):
	s[i+1] = s[i]+a[i]

x = calX(a,n,m,a[0]*2,a[n-1]*2)

out = 0
for i in range(n):
	idx = bisect_left(a,x-a[i])
	out += s[n]-s[idx]+a[i]*(n-idx)

out -= (isOver(a,n,x)-m)*x

print(out)
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from copy import deepcopy

INF = 10 ** 20


def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n=I()
G=[[]for _ in range(n)]
for _ in range(n-1):
    a,b=LI()
    G[a]+=[b]
    G[b]+=[a]

visited=[0]*n
visited[0]=1
def f(x):
    ret=0
    cnt=0
    for v in G[x]:
        if visited[v]:
            continue
        visited[v] = 1
        r=f(v)
        ret+=r
        if r==0:
            cnt+=1
    if cnt>1:
        ret+=cnt-1
    return ret

ans=f(0)
if len(G[0]) == 1:
    ans+=1

print(ans)


### FIXED CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from copy import deepcopy

INF = 10 ** 20
sys.setrecursionlimit(2147483647)

def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n=I()
G=[[]for _ in range(n)]
r=-1
for _ in range(n-1):
    a,b=LI()
    G[a]+=[b]
    G[b]+=[a]
    if len(G[a])>2:
        r=a
    if len(G[b]) > 2:
        r=b

visited=[0]*n
visited[r]=1
def f(x):
    ret=0
    cnt=0
    for v in G[x]:
        if visited[v]:
            continue
        visited[v] = 1
        r=f(v)
        ret+=r
        if r==0:
            cnt+=1
    if cnt>1:
        ret+=cnt-1
    return ret

print(1 if r == -1 else f(r))
A,B,Q=map(int,input().split())
INF=10**18
S=[-INF]+[int(input()) for _ in range(A)]+[INF]
T=[-INF]+[int(input()) for _ in range(B)]+[INF]
X=[int(input()) for _ in range(Q)]

def binary_serch(a,x,st=0,end=len(a)):
  while st<end:
    i=len(a)//2
    if x<a[i]:
      end=i
    elif a[i]<x:
      st=i+1
  return st

for x in X:
  s,t=binary_serch(S,x),binary_serch(T,x)
  ans=INF
  for j in [S[i],S[i+1]]:
    for k in [T[i],T[i+1]]:
      cnd1,cnd2=abs(j-x)+abs(k-j),abs(k-x),abs(j-k)
      ans(min(ans,cnd1,cnd2))
  print(ans)

### FIXED CODE ###

import bisect
A, B, Q = map(int, input().split())
INF=10**18
s=[-INF] + [int(input()) for i in range(A)] + [INF]
t=[-INF] + [int(input()) for i in range(B)] + [INF]
for q in range(Q):
  x = int(input())
  b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
  res = INF
  for S in [s[b - 1], s[b]]:
    for T in [t[d - 1], t[d]]:
      d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
      res = min(res, d1, d2)
  print(res)
#copy code.
import math

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

n = int(input())
t_lst, a_lst = [], []
for i in range(n):
    ti, ai = map(int, input().split())
    t_lst.append(ti)
    a_lst.append(ai)

t, a = 1, 1
for i in range(n):
    ti, ai = t_lst[i], a_lst[i]
    if ti>=t and ai>=a:
        t, a = ti, ai
    elif ti<t and ai>=a:
        t = ti * math.ceil(t/ti)
        a = ai * math.ceil(t/ti)
    elif ti>=t and ai<a:
        t = ti * math.ceil(a/ai)
        a = ai * math.ceil(a/ai)
    else:
        t_lcm = lcm_base(ti, t)
        a_lcm = lcm_base(ai, a)
        new1 = [t_lcm*math.ceil(a/(t_lcm//ti*ai)), t_lcm//ti*ai*math.ceil(a/(t_lcm//ti*ai))]
        new2 = [a_lcm//ai*ti*math.ceil(t/(a_lcm//ai*ti)), a_lcm*math.ceil(t/(a_lcm//ai*ti))]
        if sum(new1) < sum(new2):
            t, a = new1[0], new1[1]
        else:
            t, a = new2[0], new2[1]
print(t+a)

### FIXED CODE ###

n = int(input())
t_lst, a_lst = [], []
for i in range(n):
    ti, ai = map(int, input().split())
    t_lst.append(ti)
    a_lst.append(ai)

t, a = 1, 1
for i in range(n):
    ti, ai = t_lst[i], a_lst[i]
    n = max((t+ti-1)//ti, (a+ai-1)//ai)
    t = n*ti
    a = n*ai
print(t+a)