Harryxun/stf_run huggingface dataset:
n,q=map(int,input().split())
edges=[[] for i in range(n)]
for i in range(n-1):
    a,s=map(int,input().split());a-=1;s-=1
    edges[a].append(s)
    edges[s].append(a)
cnt=[-1]*n
add=[0]*n
for _ in range(q):
    a,s=map(int,input().split())
    add[a-1]+=s

def f(x):
    if cnt[x]!=-1:return cnt[x]
    ret=add[x]
    after=[]
    for to in edges[x]:
        if cnt[to]==-1:after.append(to)
        else:ret+=cnt[to]
    cnt[x]=ret
    for i in after:
        f(i)
    return 0
f(0)
print(*cnt,sep=" ")

### FIXED CODE ###

import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
n,q=map(int,input().split())
cnt=[0]*(n)
edges=[0]*n
for i in range(n):
    edges[i]=[]
for i in range(n-1):
    a,s=map(int,input().split())
    edges[a-1].append(s-1);edges[s-1].append(a-1)

from collections import deque
dq=deque([])
#pop/append/(append,pop)_left/in/len/count/[]/index/rotate()(右へnずらす)
for i in range(q):
    p,x=map(int,input().split())
    cnt[p-1]+=x

for i in edges[0]:
    dq.append((0,i))
while dq:
    f,t=dq.popleft()
    cnt[t]+=cnt[f]
    for to in edges[t]:
        if to!=f:dq.append((t,to))
    
print(*cnt)
A, B = map(int, input().split())

import fraction

print(int(A * B / fraction.gcd(A, B)))


### FIXED CODE ###

A = int(input())
B = int(input())

r = list(filter(lambda x: x != A and x != B, [1, 2, 3]))
print(r[0])
import sympy
N = int(input.())
list(map(sympy.divisor_count,list(range(1,N + 1))[:: 2])).count(8)

### FIXED CODE ###

import math

N = int(input())

def make_prime_list(num):
    if num < 2:
        return []

    prime_list = [i for i in range(num + 1)]
    prime_list[1] = 0 
    num_sqrt = math.sqrt(num)

    for prime in prime_list:
        if prime == 0:
            continue
        if prime > num_sqrt:
            break

        for non_prime in range(2 * prime, num, prime):
            prime_list[non_prime] = 0

    return [prime for prime in prime_list if prime != 0]

def search_divisor_num(num):
    if num < 0:
        return None
    elif num == 1:
        return 1
    else:
        num_sqrt = math.floor(math.sqrt(num))
        prime_list = make_prime_list(num_sqrt)

        divisor_num = 1
        for prime in prime_list:
            count = 1
            while num % prime == 0:
                num //= prime
                count += 1
            divisor_num *= count

        if num != 1:
            divisor_num *= 2

        return divisor_num


print(int(list(map(search_divisor_num,list(range(1,N + 1))[:: 2])).count(8)))
import sys
from collections import deque

def main():
    N, M = map(int, input().split())
    a = deque([int(sys.stdin.readline().strip()) for _ in range(M)])

    if len(a) != 0:
        atmp = a.popleft()

    dp=[0] * (N+1)
    for i in range(0, N+1):
        if i == atmp:
            if len(a) != 0:
                atmp = a.popleft()
            continue

        if i == 0 or i == 1:
            dp[i] = 1
            continue

        if dp[i-1] == 0 and dp[i-2] == 0:
            break


        dp[i] = dp[i-1] + dp[i-2]

    print(dp[N] % 1000000007)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque

def main():
    N, M = map(int, input().split())
    a = deque([int(sys.stdin.readline().strip()) for _ in range(M)])

    atmp = -1
    if len(a) != 0:
        atmp = a.popleft()

    dp=[0] * (N+1)
    for i in range(0, N+1):
        if i == atmp:
            if len(a) != 0:
                atmp = a.popleft()
            continue

        if i == 0 or i == 1:
            dp[i] = 1
            continue

        if dp[i-1] == 0 and dp[i-2] == 0:
            break


        dp[i] = dp[i-1] + dp[i-2]

    print(dp[N] % 1000000007)

if __name__ == '__main__':
    main()
x = int(input())
div = make_divisors(x)

if x == 1: print("0 -1")

for i in range(len(div)//2):
    u = div[i*2]
    if len(div)%2 == 1: v = div[i*2]
    else: v = div[i*2+1]
    t = int(v**(1/2))
    for j in range(t):
        a = j
        b = j-u
        if a**4 + (a**3)*b +(a**2)*(b**2) + a*(b**3) + b**4 == v:
            print(a, b)
            break

### FIXED CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

x = int(input())
div = make_divisors(x)

if x == 1: print("0 -1")

for i in range(len(div)//2):
    u = div[i*2]
    if len(div)%2 == 1: v = div[i*2]
    else: v = div[i*2+1]
    t = int(v**(1/2))
    for j in range(t):
        a = j
        b = j-u
        if a**4 + (a**3)*b +(a**2)*(b**2) + a*(b**3) + b**4 == v:
            print(a, b)
            break
int a = input()
print((1000-(a%1000))%1000)

### FIXED CODE ###

n = int(input())
ans = (1000-(n%1000))%1000
print(ans)
def cal(a, op, b):

  if op == '+':
    r = a + b
  elif op == '-':
    r = a + b
  elif op == '*':
    r = a * b
  else:
    r = a / b
    return r

while 1:
  a,op,b = raw_input().split()
  if op == '?':
    break
  else:
    cal(int(a), op, int(b))
    print r

### FIXED CODE ###

def cal(a, op, b):

  if op == '+':
    r = a + b
  elif op == '-':
    r = a - b
  elif op == '*':
    r = a * b
  elif op == '/':
    r = a / b
  return r

while 1:
  a,op,b = raw_input().split()
  if op == '?':
    break
  else:
    print(cal(int(a), op, int(b)))
k,t=map(int,input().split())
l=[int(i) for i in input().split()]
x=[int(i) for i in l]
nin=min(x)
nen=t

while 1:
    w=[]
    for i in x:
        if i-nin!=0:
            w.append(i-nin)
    x=[i for i in w]
    nin=min(x)
    if len(x)<=1:
        print(x-nin)
    nen=len(x)


### FIXED CODE ###

k,t=map(int,input().split())
l=[int(i) for i in input().split()]
if t==1:
    print(l[0]-1)
    exit()
while 1:
    l.sort(reverse=True)
    if l[1]==0: break
    l[0]-=l[1]
    l[1]=0

print(max(0,l[0]-1))
D,N = list(map(int,input().split(' ')))
#ar = [ar.append(100**D*i) for i in range(1,N+1)

for i in range(1,N+1):
  ar.append(100**D*i)
 
  
print(ar[-1])

### FIXED CODE ###

D,N = list(map(int,input().split(' ')))
#ar = [ar.append(100**D*i) for i in range(1,N+1)
ar = []
if N <100:
  for i in range(1,N+1):
    ar.append(100**D*i)
else:
  for i in range(1,N+2):
    ar.append(100**D*i)
    
  
print(ar[-1])
a, b, c = map(int, input().split())
x = a + b + c
print(x)

### FIXED CODE ###

s = input()
print(s.count("1"))
n = int(input())
a = list(map(int, input().split()))

if not 1 in a:
    print(-1)
else:
    cnt = 1
    for i in range(n):
        if a[i] == cnt:
            cnt += 1

	print(n - cnt + 1)

### FIXED CODE ###

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

if not 1 in a:
    print(-1)
else:
    cnt = 1
    for i in range(n):
        if a[i] == cnt:
            cnt += 1

    print(n - cnt + 1)
n=input()
if(n&1):
    print(0)
else:
    ans=0
    n /= 2
    while(n>=5):
        ans += n//5
        n //= 5
    print(ans)

### FIXED CODE ###

n=int(input())
if(n&1):
    print(0)
else:
    ans=0
    n /= 2
    while(n>=5):
        ans += n//5
        n //= 5
    print(ans)
a,b = map(int,input().split())
print("Alice" if (a>b and b!=1) or (a==1 and b!=1) else "Bob" (if a<b and a!=1) or(a!=1 and b==1) else "Draw")

### FIXED CODE ###

a,b = map(int,input().split())
print("Alice" if (a>b and b!=1) or (a==1 and b!=1) else "Bob" if (a<b and a!=1) or(a!=1 and b==1) else "Draw")
n = input()
a = list(map(int,input().split()))
a.insert(0.5)
alen = len(a)
a.append(0.5)

ans = 0
 
med = [0 for x in range(alen +1)]
 
for i in range(alen):
    if a[i] == i:
        med[i+1] = 1
 
for i in range(len(med)):
    if med[i] == 1:
      if med[i+1] == 1:
          med[i+1] = 0
          ans += 1
      else:
        ans += 1
        
print(ans)

### FIXED CODE ###

n = input()
a = list(map(int,input().split()))
a.insert(0,0.5)
alen = len(a)
a.append(0.5)
a.append(0.5)

ans = 0
 
med = [0 for x in range(alen +2)]
 
for i in range(alen):
    if a[i] == i:
        med[i+1] = 1

for i in range(len(med)):
    if med[i] == 1:
        if med[i+1] == 1:
            med[i+1] = 0
            ans += 1
        else:
            ans += 1
        
print(ans)
a,b = map(int,input().split())
if a > 9 or b > 9:
  print(":(")
else:
  print(""Yay!")

### FIXED CODE ###

a,b = map(int,input().split())
if a <= 8 and b <= 8:
  print("Yay!")
else:
  print(":(")
print(max(int(input())-int(input())),0)

### FIXED CODE ###

a,b=map(int,input().split());print(a-b if a>=b else 0)
x = int(input())
a =[]
c = 1
n = 2
while c <= 33:
	n = 2
    c += 1
    while c**n<=1000:
        a.append(c*n)
        n +=1
a.sort()
for i in range(len(a)):
    if a[i] > x:
        a[i] = -1000
    else:
        a[i] -= x
print(a[a.index(max(a))])

### FIXED CODE ###

x = int(input())
a =[1]
c = 1
n = 2
while c <= 33:
    n = 2
    c += 1
    while c**n<=1000:
        a.append(c**n)
        n += 1
for i in range(len(a)):
    if a[i] > x:
        a[i] = -1000
    else:
        a[i] -= x
print(a[a.index(max(a))]+x)
#coding: utf-8
from math import gcd
from functools import reduce
N, X = map(int, input().split())
x = list(map(int, input().split()))
x = [abs(X - x[i]) for i in range(N)]
l = reduce(gcd, x)
print(l)

### FIXED CODE ###

#coding: utf-8
from functools import reduce
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)
N, X = map(int, input().split())
x = list(map(int, input().split()))
x = [abs(X - x[i]) for i in range(N)]
l = reduce(gcd, x)
print(l)
N = int(input())
xy = []
A = []
for i in range(N):
    Ai = int(input())
    xyi = []
    for j in range(Ai):
        xyi.append(list(map(int, input().split())))
    A.append(Ai)
    xy.append(xyi)

ans = 0

for i in range(2**N):
    bin_i = format(i, '4b')
    flag = True
    for n, c in enumerate(bin_i):
        if c == '1':
            for j in range(N):
                for k in range(A[j]):
                    if xy[j][k][0] == n:
                        if xy[j][k][1] == 0:
                            flag = False
                            break
                if not flag:V
                    break
            if not flag:
                break
    if flag is True:
        honest = bin_i.count('1')
        if honest > ans:
            ans = honest

print(ans)


### FIXED CODE ###

N = int(input())
xy = []
A = []
for i in range(N):
    Ai = int(input())
    xyi = []
    for j in range(Ai):
        xyi.append(list(map(int, input().split())))
    A.append(Ai)
    xy.append(xyi)

ans = 0

for i in range(2**N):
    bin_i = format(i, '0' + str(N) + 'b')
    flag = True
    for j in range(N):
        for k in range(A[j]):
            if bin_i[j] == '1' and xy[j][k][1] != int(bin_i[xy[j][k][0]-1]):
                flag = False
                break
        if not flag:
            break

    if flag is True:
        honest = bin_i.count('1')
        if honest > ans:
            ans = honest

print(ans)
# -*- coding: utf-8 -*-
S=str(input())
if(S="Sunny"):
    print('Cloudy')
elif(S="Cloudy"):
    print('Rainy')
else: print('Sunny')


### FIXED CODE ###

# -*- coding: utf-8 -*-
S=str(input())
if(S=="Sunny"):
    print('Cloudy')
elif(S=="Cloudy"):
    print('Rainy')
else: print('Sunny')
import math

input = str(input()).split(" ")
for index in range(len(input)):
    input[index] = int(input[index])
x = input[0]
y = input[1]

def canBeDone(x,y):
    thingo = True
    while thingo:
        div = math.gcd(x,y)
        x = int(x/div)
        y = int(y/div)
        if (div == 1):
            thingo = False
    if (x == 1 and y == 1):
        return -1
    else:
        return 1

def test(x, y):
    if (canBeDone(x,y) == -1):
        return -1
    for index in range(math.floor(y/x)-1, abs(y)):
        if (x * index % y != 0 and abs(x * index) <= 10**(18)):
            return x * index
    return -1
print(test(x,y))


### FIXED CODE ###

x,y=map(int,input().split())
if x>=y and x%y==0:
  print(-1)
elif x<y:
  print(x)
else:
  print(x*y-x)
N = int(input())
A = list(map(int, input().split()))
dict1 = {}
for i in range(N):
  if A[i] not in dict1.keys():
    dict1[A[i]] = 0
  else:
    dict1[A[i]] += 1
value1 = []
for value in dict1.values():
  value1.append(value)
value2 = sorted(value1, reverse = True)
if value2[0] - value2[1] >= sum(value2[1:]):
  print(N - (value2[0] * 2))
else:
  if(sum(value2[0:]) % 2 == 0):
    print(len(value2))
  else:
    if len(value2) != 0:
      print(len(value2) - 1)
    else:
      print(1)


### FIXED CODE ###

x = int(input())
if x < 1200:
  print('ABC')
if x >= 1200:
  print('ARC')
L = [2, 1]
for i in range(84):
  L.append(L[i]+L[i+1])
A = int(input())
print(L[A+1])

### FIXED CODE ###

L = [2, 1]
for i in range(85):
  L.append(L[i]+L[i+1])
A = int(input())
print(L[A])
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
from enum import Enum, auto
#======================================================#
class State(Enum):
    UP = auto()
    DOWN = auto()
    HORI = auto()

def main():
    n = II()
    prev, *aa = MII()
    state = State.HORI
    cnt = 1
    for a in aa:
        if prev < a:
            if state == State.HORI:
                state = State.UP
            elif state == State.DOWN:
                cnt += 1
                state = State.HORI
        elif prev > a:
            if state == State.HORI:
                state = State.DOWN
            elif state == State.UP:
                cnt += 1
                state = State.HORI
        prev = a
    print(cnt)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
from enum import Enum
#======================================================#
class State(Enum):
    UP = 1
    DOWN = 2
    HORI = 3

def main():
    n = II()
    prev, *aa = MII()
    state = State.HORI
    cnt = 1
    for a in aa:
        if prev < a:
            if state == State.HORI:
                state = State.UP
            elif state == State.DOWN:
                cnt += 1
                state = State.HORI
        elif prev > a:
            if state == State.HORI:
                state = State.DOWN
            elif state == State.UP:
                cnt += 1
                state = State.HORI
        prev = a
    print(cnt)

if __name__ == '__main__':
    main()
a,b=input().split()
list1={1:1,2:3,3:1,4:0,5:1,6:0,7:1,8:1,9:0,10:1,11:0,12:1}
c=list1(a)
d=list1(b)
if c==d:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a,b=input().split()
list1={"1":1,"2":3,"3":1,"4":0,"5":1,"6":0,"7":1,"8":1,"9":0,"10":1,"11":0,"12":1}
c=list1[a]
d=list1[b]
if str(c)==str(d):
  print("Yes")
else:
  print("No")
hoge = input().strip()
int i = 0
while i < range(len(hoge)):
  if i%2==0 and hoge[i] == 'L' or 'D' or 'U':
    pass
  elif i%2==1 and hoge[i] == 'R' or 'D' or 'U':
    pass
  else:
    break
  i+=1
if i == len(hoge):
  print('Yes')
else:
  print('No')

### FIXED CODE ###

import re
hoge = list(input())
i = 0
while i < len(hoge):
    if i%2==0 and re.findall(r'[RDU]',hoge[i]):
        pass
    elif i%2==1 and re.findall(r'[LDU]',hoge[i]):
        pass
    else:
        break
    i+=1
if i == len(hoge):
  print('Yes')
else:
  print('No')
a, b, c = map(int, input().split())

if sum(a, b, c) == max(a, b, c) * 2:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

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

if a + b + c == max(a, b, c) * 2:
    print('Yes')
else:
    print('No')
n, k = map(int, input().split())
a = list(map(int, input().split()))
l = 1
m = []

for i in range(10000):
    if a[l - 1] in m: #ループが始まったかどうか
        for j in range(len(m)):
            if m[j] == a[l - 1]:
                cnt = j #ループ開始までの端数
                loop = len(m) - cnt #ループの長さ
                break
    else:
        m.append(a[l - 1])
        l = a[l - 1]
        continue
    break


if (k - cnt)%loop == 0:
    l = loop + cnt
else:
    l = (k - cnt)%loop - 1 + cnt

print(m[l])

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    l = [-1]*n
    now = 0
    order = 0
    l[0] = 0
    s = {}
    ans = -100

    for i in range(n):
        a[i] -= 1

    while k > 0:
        k -= 1
        now = a[now]
        order += 1
        if l[now] != -1: #既に訪問済の場合
            loop = order - l[now]
            k %= loop
        if k == 0:
            ans = now + 1
            break
        l[now] = order #転送順で何番目の町かを記録

    print(max(ans, -1))

main()
N,X = map(int,input().split())
m = list(int,input().split())
count = 0
A = sum(m)
X = X - A
count = len(m)
B = min(m)
while(X >= B):
  count += 1
  X = X - B
print(str(count))

### FIXED CODE ###

N,X = map(int,input().split())
m = [int(input()) for i in range(N)]
count = 0
A = sum(m)
X = X - A
count = N
B = min(m)
while(X >= B):
  count += 1
  X = X - B
print(str(count))
N = int(input())

N//1.08 = X
M = X * 1.08

if M == N:
    print(X)
else:
    print(":(")



### FIXED CODE ###

# Input the amount of money Takahashi paid
N = int(input())

# Check if the price before tax is X, for X = 1, 2, 3, ..., N
ans = -1
for i in range(1, N + 1):
	if int(i * 1.08) == N:
		ans = i

# Print answer
if ans != -1:
	print(ans)
else:
	print(":(")
import numpy as np
# dp[i][j]: i+1日目に活動jをしたときのi+1日目までの幸福度の最大値
N = int(input())
abc = []
for i in range(N):
    abc.append(list(map(int, input().split())))
dp = np.zeros(shape=(N, 3), dtype=int)
dp[0, :] = abc[0]
for i in range(N-1):
    dp[i+1, 0] = max(dp[i+1, 0], dp[i, 1] + abc[i+1][0], dp[i, 2] + abc[i+1][0])
    dp[i+1, 1] = max(dp[i+1, 1], dp[i, 0] + abc[i+1][1], dp[i, 2] + abc[i+1][1])
    dp[i+1, 2] = max(dp[i+1, 2], dp[i, 0] + abc[i+1][2], dp[i, 1] + abc[i+1][2])
print(max(dp[N-1, :]))

### FIXED CODE ###

import numpy as np
N = int(input())
abc = []
for i in range(N):
    abc.append(list(map(int, input().split())))
    
dp = np.zeros(shape=(N, 3), dtype=int)
dp[0, :] = abc[0]
for i in range(N-1):
    dp[i+1, 0] = max(dp[i+1, 0], dp[i, 1] + abc[i+1][0], dp[i, 2] + abc[i+1][0])
    dp[i+1, 1] = max(dp[i+1, 1], dp[i, 0] + abc[i+1][1], dp[i, 2] + abc[i+1][1])
    dp[i+1, 2] = max(dp[i+1, 2], dp[i, 0] + abc[i+1][2], dp[i, 1] + abc[i+1][2])
print(max(dp[N-1, :]))
DN = list(map(int,input().split()))
D=DN[0]
N=DN[1]

if D=0:
    print(N)

if D=1:
    print(100*N)

if D=2:
    print(1000*N)


### FIXED CODE ###

DN = list(map(int,input().split()))
D=DN[0]
N=DN[1]

if D==0 and N==100:
    print(101)
elif D==0:
    print(N)
elif D==1 and N==100:
    print(10100)
elif D==1:
    print(100*N)
elif D==2 and N==100:
    print(1010000)
else :
    print(10000*N)
from functools import lru_cache
N = int(input())
S = input()
X = int(S, 2)

P = S.count('1')
Rp = X % (P+1)
Rn = X % (P-1)


@lru_cache(None)
def popcnt(x):
    return bin(x).count('1')

mask = 1 << N
for i in range(N-1, -1, -1):
    mask >>= 1
    
    x = X ^ mask
    if x == 0:
        print(0)
        continue

    if X & mask:
        p = P-1
        x = (Rn - pow(2, i, p)) % p
    else:
        p = P+1
        x = (Rp + pow(2, i, p)) % p

    cnt = 1
    while x:
        x %= popcnt(x)
        cnt += 1
    print(cnt)


### FIXED CODE ###

from functools import lru_cache
N = int(input())
S = input()
X = int(S, 2)

P = S.count('1')
if P == 0:
    for i in range(N):
        print(1)
    exit()

Rp = X % (P+1)
if P != 1:
    Rn = X % (P-1)

@lru_cache(None)
def popcnt(x):
    return bin(x).count('1')

for i in range(N):
    if S[i] == '1':
        if P == 1:
            print(0)
            continue
        p = P-1
        x = (Rn - pow(2, N-1-i, p)) % p
    else:
        p = P+1
        x = (Rp + pow(2, N-1-i, p)) % p

    cnt = 1
    while x:
        x %= popcnt(x)
        cnt += 1
    print(cnt)
a = int(input())
count = 0
for i in range(a):
    a,b = map(int,input().split())
    
    if (a==b):
        count += 1
        break
    else : 
        count = 0

if (count >= 3):
        
    print("Yes")
else :
    print("No")


### FIXED CODE ###

a = input()

if (a[-1] != "s"):
    a += "s"

else :
    a += "es"

print(a)
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    x, y = LI()
    print(x+y//2)
    return

#B
def B():
    return

#C
def C():
    n, m = LI()
    py = LIR(m)
    pya = py[::1]
    py.sort(key=lambda x: x[1])
    city = [1 for i in range(n)]
    dicity = {}
    for p, y in py:
        dicity[(p,y)] = city[p-1]
        city[p-1] += 1    
    for p, y in pya:
        a = "00000" + str(p)
        a = a[-6:]
        b = "00000" + str(dicity[(p, y)])
        b = b[-6:]
        print(a+b)

    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    C()


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    x, y = LI()
    print(x+y//2)
    return

#B
def B():
    return

#C
def C():
    n, m = LI()
    py = LIR(m)
    pya = py[::1]
    py.sort(key=lambda x: x[1])
    city = [1 for i in range(n)]
    dicity = {}
    for p, y in py:
        dicity[(p,y)] = city[p-1]
        city[p-1] += 1    
    for p, y in pya:
        a = "00000" + str(p)
        a = a[-6:]
        b = "00000" + str(dicity[(p, y)])
        b = b[-6:]
        print(a+b)

    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    A()
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
ans = 0
for i in range(n):
    town_a = a[i]
    town_b = b[i+1]
    power = b[i]
    if power > town_a:
        ans += town_a
        power -= town_a
    else:
        ans += power
        continue
    if power > town_b:
        ans += town_b
        a[i+1] = 0
    else:
        ans += power
        a[i+1] -= power
print(ans)

### FIXED CODE ###

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

ans = 0
for i in range(n):
    town_a = a[i]
    town_b = a[i+1]
    power = b[i]
    if power > town_a:
        ans += town_a
        power -= town_a
    else:
        ans += power
        continue
    if power > town_b:
        ans += town_b
        a[i+1] = 0
    else:
        ans += power
        a[i+1] -= power
print(ans)
l = int(input())
print((l/3)***3)

### FIXED CODE ###

l = int(input())
print((l/3)**3)
n=[int(i) for i in input().split]
n.sort()
print(n[0]+n[1])

### FIXED CODE ###

n=[int(i) for i in input().split()]
n.sort()
print(n[0]+n[1])