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

import sys, re
from math import ceil, floor, sqrt, pi#, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_rpw_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 7)
INF = float('inf')
MOD = 10 ** 9 + 7

def dfs(current, parent, edges, ans_list):
    for child in edges[current]:
        if child == parent:
            continue
        ans_list[child] += ans_list[current]
        dfs(child, current, edges, ans_list)

def main():
    n, q = i_map()

    edges = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = i_map()
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)

    ans_list = [0] * n
    for i in range(q):
        p, x = i_map()
        ans_list[p-1] += x

    dfs(0, -1, edges, ans_list)

    print(*ans_list)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys, re
from math import ceil, floor, sqrt, pi#, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_rpw_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 7)
INF = float('inf')
MOD = 10 ** 9 + 7

def dfs(current, parent, edges, ans_list):
    for child in edges[current]:
        if child == parent:
            continue
        ans_list[child] += ans_list[current]
        dfs(child, current, edges, ans_list)

def main():
    n, q = i_map()

    edges = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = i_map()
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)

    ans_list = [0] * n
    for i in range(q):
        p, x = i_map()
        ans_list[p-1] += x

    dfs(0, -1, edges, ans_list)

    print(*ans_list)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

#!/usr/bin/env python3
#n,p = map(int,input().split())
s = input()
p = 2019
n = len(s)
u_i = []
ans = 0
for i in range(n):
    u_i.append(int(s[i:])%p)
u_i.append(0)
amari = [0]*p
for i in u_i:
    amari[i] += 1
for i in amari:
    ans+= i*(i-1)//2
print(ans)


### FIXED CODE ###

p = 2019
s = input()
n = len(s)
l = [0 for i in range(p)]
l[0] = 1
ten = 1
cnt = 0
 
ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i+1
else:
    for i in range(n):
        cnt = (cnt + int(s[-i-1]) * ten) % p
        l[cnt] += 1
        ten = (ten * 10) % p
    for i in l:
        if i > 1:
            ans += i * (i - 1) // 2
print(ans)
### BUGGY CODE ###

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

inf = float('INF')
road = [[inf for i in range(n)] for j in range(n)]
for i in range(n):
    road[i][i] = 0
for i in range(m):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    road[a][b] = road[b][a] = c

def warshall(d, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]

warshall(road, n)
# [print(cost) for cost in road]
# print()
costs = [[1 if road[i][j] <= l and i != j else inf for j in range(n)] for i in range(n)]
for i in range(n):
    costs[i][i] = 0
warshall(costs, n)

# [print(cost) for cost in costs]
q = int(input())
for i in range(q):
    s,t = map(int, input().split())
    
    print(costs[s-1][t-1]-1 if costs[s-1][t-1] < inf else -1)


### FIXED CODE ###

from scipy.sparse.csgraph import dijkstra as di

inf = float('INF')
n,m,l = map(int,input().split())

route = [[0 for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a,b,c = map(int, input().split())
    route[a-1][b-1] = route[b-1][a-1] = c

p_route = di(route)
p_route[p_route == 0] = inf
p_route[l >= p_route] = 1
p_route[l < p_route] = 0
p_route = di(p_route)

# print(p_route)
query = []
q = int(input())
ans = []
for _ in range(q):
    s,t = map(int, input().split())
    print(-1 if p_route[s-1][t-1] == inf else int(p_route[s-1][t-1]) - 1)
### BUGGY CODE ###

import sys
def fastio():
    from io import StringIO
    from atexit import register
    global input
    sys.stdin = StringIO(sys.stdin.read())
    input = lambda : sys.stdin.readline().rstrip('\r\n')
    sys.stdout = StringIO()
    register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()

def debug(*var, sep = ' ', end = '\n'):
    print(*var, file=sys.stderr, end = end, sep = sep)

INF = 10**20
MOD = 10**9 + 7
I = lambda:list(map(int,input().split()))
# from math import gcd
from math import ceil
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br

n, m = I()
a = [0] * (n + 10)
for i in range(m):
    x, y = I()
    a[x] += 1
    a[y + 1] -= 1
ans = 0
for i in range(1, n + 10):
    a[i] = a[i] + a[i - 1]
    if a[i] == m:
        ans += 1
print(ans)


### FIXED CODE ###

n,m=map(int,input().split())
lmax=0
rmin=10**20
for i in range(m):
    l,r=map(int,input().split())
    lmax=max(lmax,l)
    rmin=min(rmin,r)
if lmax>rmin:
    print(0)
else:
    print(rmin-lmax+1)
### BUGGY CODE ###

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

result = 1

if 0 in a:
  print(0)
  exit()
elif max(a) > 10 **18:
  print(-1)
  exit()
else:
  for i in range(N):
    result *= a[i]
  if result > 10**18:
    print(-1)
  else:
    print(result)

### FIXED CODE ###

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

result = 1

if 0 in a:
  print(0)
  exit()
else:
  for i in range(N):
    result *= a[i]
    if result > 10**18:
      print(-1)
      exit()
  print(result)
### BUGGY CODE ###

while True:
    n = int(input())
    if not n:
        break
    stars = list(map(int, input().split()))
    half_n = n // 2
    for s in set(stars):
        if stars.count(s) > half_n:
            print(s)
            break
    else:
        print('NO COLOR')

### FIXED CODE ###

from collections import defaultdict

while True:
    n = int(input())
    if not n:
        break
    stars = defaultdict(int)
    for s in map(int, input().split()):
        stars[s] += 1
    half_n = n // 2
    for i, s in stars.items():
        if s > half_n:
            print(i)
            break
    else:
        print('NO COLOR')
### BUGGY CODE ###


k,s = map(int, input().split())
ans = 0
x = range(k + 1)
y = range(k + 1)
z = range(k + 1)

for i in x:
	for j in y:
		for k in z:
			if i + j + k == s:
				ans += 1

print(ans)





### FIXED CODE ###

k,s = map(int, input().split())
ans = 0
x = range(k + 1)
y = range(k + 1)
z = range(k + 1)


for i in x:
	for j in y:
			if 0 <= s - i - j <= k:
				ans += 1

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

s=input()

p=[0]*len(s)

for i in range(len(s)):
    if s[i]=="R":
        index = i + s[i:].index("L") - (s[i:].index("L"))%2
        p[index] +=1


    if s[i]=="L":
        index = i - s[i::-1].index("R") + (s[i::-1].index("R"))%2
        p[index] +=1

for i in p:
    print(i,end=" ")


### FIXED CODE ###

s=input()+"R"


p=[0]*(len(s)-1)
key=s[0]
strt=0
for i in range(len(s)):

    if key!=s[i]:
        if key=="R":
            p[i]  += (i-strt)//2
            p[i-1] += (i-strt)//2 + (i-strt)%2
            key="L"
        else:
            p[strt] += (i-strt)//2 + (i-strt)%2
            p[strt-1] += (i-strt)//2
            key="R"
        strt=i

for i in p:
    print(i,end=" ")
### BUGGY CODE ###

from math import factorial

def comb(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

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

C = comb(N*M-2, K-2)
#print(int(C))

A = int(0)
for d in range(N):
    a = (N-d)*(M**2)

    A += int(d*a)

B = int(0)
for d in range(M):
    b = (M-d)*(N**2)
    B += int(d*b)

ans = int((A+B)*C)
ans = ans%(1000000007)
print(ans)


### FIXED CODE ###

def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

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

C = comb(N*M-2, K-2)
#print(int(C))

A = int(0)
for d in range(N):
    a = (N-d)*(M**2)

    A += int(d*a)

B = int(0)
for d in range(M):
    b = (M-d)*(N**2)
    B += int(d*b)

ans = int((A+B)*C)
ans = ans%(1000000007)
print(ans)
### BUGGY CODE ###

#c
import sys
n = int(input())
import math

ans = 0
for i in range(1,n):
    before = n
    for j in range(1,n):
        if (n-i)%j==0 :
            
            if before <= j:
                break
            if j==(n-i)/j:
                ans+=1
            else:
                ans+=2
                

        before = (n-i)/j
print(ans)
        

### FIXED CODE ###

#c
import sys
n = int(input())
import math

ans = 0

for i in range(1,n):
    ans += (n-1)//i
print(ans)
### BUGGY CODE ###


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

def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)
 
def lcm(x, y):
    return (x * y) // gcd(x, y)

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

success = False
ans = 0

_lcm = lcm(len(S), len(T))
for k in range(1, (len(S) * len(T))//_lcm + 1):
    ans = k * _lcm
    s = [(i * ans)//len(S) + 1 for i in range(len(S))]
    t = [(i * ans)//len(T) + 1 for i in range(len(T))]
    pool = s + t

    double_st = []
    
    for i in range(len(S)):
        if (len(T)*i)%len(S) == 0 and (len(T) * i)//len(S) <len(T):
            double_st += [(i * ans)//len(S) + 1]
    isImpossible = False

    for st in double_st:
        s_i = my_index(s, st, -1)
        t_i = my_index(t, st, -1)
        if s_i == -1 or t_i == -1:
            continue
        if S[s_i] != T[t_i]:
            isImpossible = True
            break

            
    if not isImpossible:
        success = True
        break

if not success:
    print(-1)
else:
    print(ans)

### FIXED CODE ###


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

def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)
 
def lcm(x, y):
    return (x * y) // gcd(x, y)

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

success = False
fans = 0

_lcm = lcm(len(S), len(T))

def isImpble(k, _lcm):
    global success
    global S
    global T
    global fans
    
    ans = k * _lcm
    double_st = []
    
    for i in range(len(S)):
        if (len(T)*i)%len(S) == 0 and (len(T) * i)//len(S) <len(T):
            double_st += [(i * ans)//len(S) + 1]
    isImpossible = False

    for st in double_st:
        s_i = ((st-1) * len(S))//ans
        t_i = ((st-1) * len(T))//ans
        if S[s_i] != T[t_i]:
            isImpossible = True
            break

            
    if isImpossible:
        return True
    else:
        success = True
        fans = k*_lcm
        return False
        

imp = isImpble((len(S) * len(T))//_lcm, _lcm)

if not imp:
    for k in range(1, (len(S) * len(T))//_lcm ):
        imp = isImpble(k, _lcm)
        if success:
            break
    

if not success:
    print(-1)
else:
    print(fans)
### BUGGY CODE ###

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

if n % 2 == 0:
    for i in range(n):
        if i % 2 == 0:
            b.append(a[i])
        else:
            b.insert(0,a[i])
else:
    for i in range(n):
        if i % 2 == 0:
            b.insert(0,a[i])
        else:
            b.append(a[i])

print(*b)

### FIXED CODE ###

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

if n % 2 == 0:
    b = a[n-1::-2] + a[::2]
else:
    b = a[n-1::-2] + a[1::2]

print(*b)
### BUGGY CODE ###

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    for i in range(N):
        print(A.count(i+1))
resolve()

### FIXED CODE ###

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    ans = [0]*N
    for i in A:
        ans[i-1] += 1
    for j in ans:
        print(j)
resolve()
### BUGGY CODE ###

try:
    inp = list(input().split())
    #listA<-[1,2,2,3,1]
    #print(listA)
    #ここに逐次処理を書けばいいと思う。
except:
    quit();
    #または、quit(),os.exit()をして止める。

try:
    h = list(input().split())
    #listA<-[1,2,2,3,1]
    #print(listA)
    #ここに逐次処理を書けばいいと思う。
except:
    quit();
    #または、quit(),os.exit()をして止める。

N=int(inp[0])
K=int(inp[1])

dp=[]

for i in range(N):
    dp.append(0)



for j in range(1,N):
    min=float('inf')

    if j-K>=0:
        bnum=j-K
    else:
        bnum=0

    for i in range(bnum,j):
        num=abs(int(h[i])-int(h[j])) + dp[i]
        if num < min:
            min=num
    dp[j]=min

print(dp[N-1])



### FIXED CODE ###

import sys
import numpy as np
input = sys.stdin.readline

try:
    inp = list(input().split())
    #listA<-[1,2,2,3,1]
    #print(listA)
    #ここに逐次処理を書けばいいと思う。
except:
    quit();
    #または、quit(),os.exit()をして止める。

try:
    h = list(map(int, input().split()))
    #listA<-[1,2,2,3,1]
    #print(listA)
    #ここに逐次処理を書けばいいと思う。
except:
    quit();
    #または、quit(),os.exit()をして止める。

N=int(inp[0])
K=int(inp[1])

dp=[0]*N

dp=np.array(dp)
h=np.array(h)

for j in range(1,N):
    bnum=max(0,j-K)
    dp[j]=np.min(np.abs(h[bnum:j]-h[j]) + dp[bnum:j])

print(dp[N-1])
### BUGGY CODE ###

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

l = [""] * m

for i in range(m):
    l[i] = list(map(int,input().split()))

ans2 = set()
ans3 = set()

for i in range(1,n+1):
    ans3.add(i)

tmp = set()

for i in range(m):
    for j in range(1,n+1):
        if l[i][0] <= j <= l[i][1]:
            ans2.add(j)
    ans3 = ans3 & ans2
    ans2.clear()
    
    
print(len(ans3))


    

### FIXED CODE ###

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

left_max = -1
right_min = n+1

for i in range(m):
    s,t = map(int,input().split())
    left_max = max(left_max,s)
    right_min = min(right_min, t)
    
print(max(0, right_min - left_max +1))
### BUGGY CODE ###


n = int(input())
a = list(map(int, input().split()))
x = 1
for i in range(n):
    print(a.count(x))
    x += 1

### FIXED CODE ###

from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
cnt = defaultdict(int)
for i in range(n - 1):
    cnt[a[i]] += 1
for i in range(1, n + 1): 
    print(cnt[i])
### BUGGY CODE ###

N, M = map(int, input().split())
MOD = 10 ** 9 + 7


# 逆元の前計算
factorial = [1, 1]
inverse = [1, 1]
invere_base = [0, 1]
for i in range(2, N + M + 1):
    factorial.append((factorial[-1] * i) % MOD)
    invere_base.append((-invere_base[MOD % i] * (MOD // i)) % MOD)
    inverse.append((inverse[-1] * invere_base[-1]) % MOD)


def nCr(n, r):
    if not 0 <= r <= n:
        return 0
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


def nPr(n, r):
    if not 0 <= r <= n:
        return 0
    return nCr(n, r) * factorial[r] % MOD


ans = pow(nPr(M, N), 2, MOD)
for k in range(1, N + 1):
    x = nCr(M, k) * nPr(N, k) * pow(nPr(M - k, N - k), 2, MOD) % MOD
    if k % 2 == 1:
        x = -x
    ans += x
    ans %= MOD

print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
MOD = 10 ** 9 + 7


factorial = [1, 1]
inverse = [1, 1]
invere_base = [0, 1]
for i in range(2, N + M + 1):
    factorial.append((factorial[-1] * i) % MOD)
    invere_base.append((-invere_base[MOD % i] * (MOD // i)) % MOD)
    inverse.append((inverse[-1] * invere_base[-1]) % MOD)


def nCr(n, r):
    if not (0 <= r <= n):
        return 0
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


def nPr(n, r):
    if not (0 <= r <= n):
        return 0
    return nCr(n, r) * factorial[r] % MOD


ans = pow(nCr(M, N) * factorial[N], 2, MOD)
for r in range(1, N + 1):
    p = nCr(M, r) * pow(nCr(M - r, N - r), 2, MOD) * nCr(N, r) * factorial[r] * factorial[N - r] * factorial[N - r] % MOD
    p *= ((-1) ** ((r % 2) ^ 1))
    ans -= p
    ans %= MOD

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

n = int(input())
tmp = []

for i in range(n):
    a = int(input())
    tmp = list(set(tmp))
    if not (a in tmp):
        tmp.append(a)
    else:
        tmp.remove(a)

print(len(tmp))


### FIXED CODE ###

n=int(input())
a=set()
for i in range(n):
    b=int(input())
    if b in a:
        a.remove(b)
    else:
        a.add(b)
print(len(a))
### BUGGY CODE ###

from collections import deque
s,q=deque([*input()]),int(input())
for i in range(q):
  t=input().split()
  if len(t)==1:
    s.reverse()
  else:
    t,f,c=t
    if f=='1': s.appendleft(c)
    else: s.append(c)
print(*s,sep='')

### FIXED CODE ###

from collections import deque
s,q=deque([*input()]),int(input())
judge=False
for i in range(q):
  t=input().split()
  if len(t)==1:
    judge = not judge
  else:
    t,f,c=t
    if not judge and f=='1': s.appendleft(c)
    elif not judge and f=='2': s.append(c)
    elif judge and f=='1': s.append(c)
    else: s.appendleft(c)
if judge: s.reverse()
print(*s,sep='')
### BUGGY CODE ###

k, s = map(int, input().split())
count = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x + y + z == s:
                count += 1
print(count)

### FIXED CODE ###

k, s = map(int, input().split())
count = 0
for x in range(k+1):
    for y in range(k+1):
        if s-k <= x + y <= s:
            count += 1
print(count)
### BUGGY CODE ###

from collections import defaultdict

def count_substring(s):
    found_remainder = defaultdict(int)
    current_mod = 0
    found_remainder[0] = 1

    output = 0
    for i in range(len(s)-1,-1,-1):
        digit = s[i]
        current_mod =  (int(digit)*10**(len(s)-1-i) % 2019 + current_mod) % 2019
        output += found_remainder[current_mod]
        found_remainder[current_mod] += 1

    return output

s = input()
print(count_substring(s))


### FIXED CODE ###

from collections import defaultdict

def get_modulos():
    modulos = []
    for i in range(224):
        modulos.append(10**i%2019)
    return modulos

def count_substring(s):
    found_remainder = defaultdict(int)
    current_mod = 0
    found_remainder[0] = 1

    output = 0

    modulos = get_modulos()
    for i in range(len(s)-1,-1,-1):
        digit = s[i]
        current_mod =  (int(digit)*modulos[(len(s)-1-i)%224] % 2019 + current_mod) % 2019
        # print(i, current_mod)
        output += found_remainder[current_mod]
        found_remainder[current_mod] += 1
    #print(dict(found_remainder))

    return output

s = input()
print(count_substring(s))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2000000)
n,u,v=map(int,input().split())
u=u-1
v=v-1
root=[[] for i in range(n)]

for i in range(n-1):
    a,b=map(int,input().split())
    root[a-1].append(b-1)
    root[b-1].append(a-1)
dp1=[-1]*n
dp1[u]=0
dp2=[-1]*n
dp2[v]=0

def dfs(node,depth,par,dp):
    for vertex in root[node]:
        if vertex == par or dp[vertex]!=-1:
            continue
        dp[vertex]=depth+1
        dfs(vertex,depth+1,node,dp)
dfs(u,0,u,dp1)
dfs(v,0,v,dp2)
buf=-1
buf1=0
#print(dp1,dp2,root)
for i in range(n):
    if dp1[i]<dp2[i] and dp2[i]>buf:
        buf=dp2[i]
        buf1=dp1[i]
print(buf-1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)
n,u,v=map(int,input().split())
u=u-1
v=v-1
root=[[] for i in range(n)]

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

dp=[[-1]*n for i in range(2)]
dp[0][u]=0
dp[1][v]=0
def dfs(node,depth,par,flag):
    for vertex in root[node]:
        if vertex == par or dp[flag][vertex]!=-1:
            continue
        dp[flag][vertex]=depth+1
        dfs(vertex,depth+1,node,flag)
    return
dfs(u,0,u,0)
dfs(v,0,v,1)
buf=-1
buf1=0
#print(dp1,dp2,root)
for i in range(n):
    if dp[0][i]<dp[1][i] and dp[1][i]>buf:
        buf=dp[1][i]
        buf1=dp[0][i]
print(buf-1)
### BUGGY CODE ###

n, m = map(int, input().split())
pys = [list(map(int, input().split())) for _ in range(m)]
map_ = {}
for i, (p, y) in enumerate(pys):
    map_.setdefault(p, [])
    for j in range(len(map_[p])):
        if y < pys[map_[p][j]][1]:
            map_[p].insert(j, i)
            break
    else:
        map_[p].append(i)
ans = [None] * m
for key, val in map_.items():
    for num, i in enumerate(val):
        ans[i] = '{:06d}'.format(key) + '{:06d}'.format(num + 1)
for a in ans:
    print(a)


### FIXED CODE ###

n, m = map(int, input().split())
pys = [list(map(int, input().split())) for _ in range(m)]
map_ = {}
for i, (p, y) in enumerate(pys):
    map_.setdefault(p, [])
    map_[p].append(i)

for val in map_.values():
    val.sort(key=lambda i: pys[i][1])

ans = [None] * m
for key, val in map_.items():
    for num, i in enumerate(val):
        ans[i] = '{:06d}'.format(key) + '{:06d}'.format(num + 1)
for a in ans:
    print(a)
### BUGGY CODE ###

#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys

EMPTY = (0, 0, frozenset())


def solve(values, _nb, max_capacity):
    dp = [0] * (max_capacity + 1)
    for w, v in values:
        for j in range(max_capacity, w - 1, -1):
            dp[j] = max(dp[j - w] + v, dp[j])
    return dp[max_capacity]


def solve_better(values, _nb, max_capacity):
    dp = [0] * (max_capacity + 1)
    for w, v in values:
        # dp = dp[:w] + [max(dp[j], dp[j - w] + v) for j in range(w, max_capacity + 1)]
        dp[w:] = [max(dpj, dpjw + v) for dpj, dpjw in zip(dp[w:], dp[:-w])]
    return dp[max_capacity]


def solve_slow(values, nb, max_capacity):
    dp = [[0 for _ in range(max_capacity + 1)] for _ in range(nb + 1)]
    for i in range(1, nb + 1):
        w, v = values[i - 1]
        for j in range(1, max_capacity + 1):
            if w <= j:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
            else:
                dp[i][j] = dp[i - 1][j]
    # print("\n".join(map(str, dp)))
    return dp[nb][max_capacity]


def do_job():
    "Do the work"
    # first line is number of test cases
    N, W = map(int, input().split())
    values = []
    for _ in range(N):
        values.append(list(map(int, input().split())))
    result = solve(values, N, W)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


### FIXED CODE ###

# DP
def main():
    N, W = map(int, input().split())

    dp = [-1] * (W + 1)
    dp[0] = 0
    for _ in range(N):
        w, v = map(int, input().split())
        for i in range(W - w, -1, -1):
            if dp[i] == -1:
                continue
            if dp[i + w] < dp[i] + v:
                dp[i + w] = dp[i] + v
    print(max(dp))


main()