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

import sys

sys.setrecursionlimit(100000000)


# p:parent
def bfs(g: {}, v: int, p: int, depth: int, dd: {}):
    d_v = dd.setdefault(v, (p, depth))
    if depth > d_v[1]:
        dd[v] = (p, depth)

    ls = g.setdefault(v, [])
    for next_v in ls:
        # next_v が親だったらスルー
        if next_v == p:
            continue
        # 再帰的に探索
        bfs(g, next_v, v, depth + 1, dd)


def main():
    n, m = map(int, input().split())

    children = set()
    g = {}
    # parent_g = {}
    for i in range(n - 1 + m):
        a, b = map(int, input().split())
        dic_a = g.setdefault(a - 1, [])
        dic_a.append(b - 1)
        children.add(b - 1)
        # dic_b = parent_g.setdefault(b - 1, [])
        # dic_b.append(a - 1)

    root = -1
    for i in range(n):
        if i not in children:
            root = i
            break
    parent = -1
    depth = 0
    dd = {}
    bfs(g, root, parent, depth, dd)

    for i in range(n):
        print(dd[i][0] + 1)
        # if len(v) == 1:
        #     print(v[0][0]+1)
        #     continue
        #
        # v.sort(key=lambda x: x[1], reverse=True)
        # print(v[0][0]+1)



main()


### FIXED CODE ###

import sys
import collections

sys.setrecursionlimit(100000000)


# p:parent
def bfs(g: {}, parent_g: {}, v: int, p: int, depth: int, dd: {}, dq):
    p_ls = parent_g.setdefault(v, [])
    if len(p_ls) > 1:
        p_ls.remove(p)
        return
    dd[v] = (p, depth)

    ls = g.setdefault(v, [])
    for next_v in ls:
        # next_v が親だったらスルー
        if next_v == p:
            continue
        # 探索キューに追加
        dq.append((next_v, v, depth+1))


def main():
    n, m = map(int, input().split())

    children = set()
    g = {}
    parent_g = {}
    for i in range(n - 1 + m):
        a, b = map(int, input().split())
        dic_a = g.setdefault(a - 1, [])
        dic_a.append(b - 1)
        children.add(b - 1)
        dic_b = parent_g.setdefault(b - 1, [])
        dic_b.append(a - 1)

    root = -1
    for i in range(n):
        if i not in children:
            root = i
            break
    parent = -1
    depth = 0
    dd = {}

    dq = collections.deque()
    dq.append((root, parent, depth))
    while len(dq) > 0:
        t, p, d = dq.popleft()
        bfs(g, parent_g, t, p, d, dd, dq)

    for i in range(n):
        print(dd[i][0] + 1)
        # if len(v) == 1:
        #     print(v[0][0]+1)
        #     continue
        #
        # v.sort(key=lambda x: x[1], reverse=True)
        # print(v[0][0]+1)



main()
### BUGGY CODE ###

import numpy as np

H, W, M = map(int, input().split())
row = np.zeros(W)
col = np.zeros(H)
memo = []
for _ in range(M):
    h, w = map(int, input().split())
    h -=1
    w -=1
    row[w] += 1
    col[h] += 1
    memo.append((h, w))

col_max = col.max()
row_max = row.max()

max_col_indexs = np.where(col == col_max)[0]
max_row_indexs = np.where(row == row_max)[0]

ans = col_max + row_max -1
for c in max_col_indexs:
    for r in max_row_indexs:
        if (c, r) not in memo:
            ans = ans = col_max + row_max
            break

print(int(ans))

### FIXED CODE ###

import numpy as np
def main():
    H, W, M = map(int, input().split())
    row = np.zeros(W)
    col = np.zeros(H)
    memo = []
    for _ in range(M):
        h, w = map(int, input().split())
        h -=1
        w -=1
        row[w] += 1
        col[h] += 1
        memo.append((h, w))

    col_max = col.max()
    row_max = row.max()

    max_col_indexs = np.where(col == col_max)[0]
    max_row_indexs = np.where(row == row_max)[0]

    ans = col_max + row_max -1
    memo = set(memo)
    for c in max_col_indexs:
        for r in max_row_indexs:
            if (c, r) not in memo:
                ans = ans = col_max + row_max
                print(int(ans))
                exit()

    print(int(ans))

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

A,B,C,X,Y=map(int,input().split())
if A>=2*C:
  if B>=2*C:
    print(2*C*max(X,Y))
    exit()
  else:
    print(2*C*X+B*max(0,(Y-X)))
    exit()
elif B>=2*C:
  print(2*C*Y+A*max(0,(X-Y)))
  exit()
else:
  ans=A*X+B*Y
  for p in range(X):
    for q in range(Y):
      r=max(2*(X-p),2*(Y-q))
      ans=min(ans,A*p+B*q+C*r)
  print(ans)

### FIXED CODE ###

A,B,C,X,Y=map(int,input().split())
if A>=2*C:
  if B>=2*C:
    print(2*C*max(X,Y))
    exit()
  else:
    print(2*C*X+B*max(0,(Y-X)))
    exit()
elif B>=2*C:
  print(2*C*Y+A*max(0,(X-Y)))
  exit()
else:
  ans=A*X+B*Y
  for i in range(1,min(X,Y)+1):
    p=A*(X-i)+B*(Y-i)+2*C*i
    ans=min(ans,p)
  print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
kv = {'R':[],'G':[],'B':[]}
for i in range(N):
    kv[S[i]].append(i)

ans = 0
for one in kv['R']:
    for t in kv['G']:
        tmp = len(kv['B'])
        if 2*t-one in kv['B']:
            tmp-=1
        if 2*one-t in kv['B']:
            tmp-=1
        if (t+one)/2 in kv['B']:
            tmp-=1
        ans+=tmp
print(ans)

### FIXED CODE ###

N = int(input())
S = input()

kv = {'R':[],'G':[],'B':[]}
for i in range(N):
    kv[S[i]].append(i)

a = sorted([[len(kv['R']),'R'],[len(kv['G']),'G'],[len(kv['B']),'B']], key=lambda x:-x[0])
a1, a2, a3 = a[0][1],a[1][1],a[2][1]

ans = a[0][0]*a[1][0]*a[2][0]
set_a3 = set(kv[a3])
for one in kv[a1]:
    for t in kv[a2]:
        ans-=3-len(set([2*t-one,2*one-t,(t+one)/2])-set_a3)
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
S = set()

MOD = 998244353
for _ in range(K):
    L, R = map(int, input().split())
    S |= set(range(L, R + 1))
# print(f'{S=}')

DP = [0] * (N + 5) * 2
DP[0] = 0
DP[1] = 1

# 配るDP
for i in range(1, N + 1):
    for s in S:
        DP[i + s] += DP[i]
    DP[i] %= MOD
# print(f'{DP=}')
print(DP[N])


### FIXED CODE ###

N, K = map(int, input().split())
MOD = 998244353
LR = []
for _ in range(K):
    L, R = map(int, input().split())
    LR.append((L, R))
# print(f'{LR=}')

DP = [0] * (N + 1)
DP[1] = 1
S = [0] * (N + 1)

for i in range(1, len(DP)):
    for L, R in LR:
        v = S[max(i - L, 0)] - S[max(i - R - 1, 0)]
        DP[i] += v
    DP[i] %= MOD
    S[i] = (S[i - 1] + DP[i]) % MOD

# print(f'{DP=}')
# print(f'{S=}')
print(DP[-1])
### BUGGY CODE ###

N = int(input())
A =list(map(int,input().split()))
def judge(l,r):
    xor = A[l]
    for i in range(l+1,r+1):
        xor ^= A[i]
    suma = sum(A[l:r+1])
    if xor == suma:
        return 1
    else:
        return 0
count = 0
for left in range(N):
    right = left
    while right < N:
        count += judge(left,right)
        right += 1
print(count)
    

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
suma = 0
left = 0
right = 0
count = 0
while left != N:
    if right == N:
        count += right-left
        suma -= A[left]
        left += 1
    elif suma+A[right] == suma^A[right]:
        suma += A[right]
        right += 1
    else:
        count += right - left
        suma -= A[left]
        left += 1
print(count)
### BUGGY CODE ###

import numpy as np
import math

global csA
MAXINT = 2 ** 63 - 1

def getsumanddiff(i, j, k):
    tmp = csA[j+1]
    p = tmp - csA[i]
    q = csA[k+1] - tmp
    return p, q, abs(p - q)

N = int(input())
A = np.array(list(map(int, input().split())))
# N = 1000000
# A = np.arange((N))
csA = np.cumsum(A)

# init
mid0 = 0
mid2 = 2

p, q, r, s = [0]*4
diff = MAXINT

csAN = csA[N-1]
for mid1 in range(1, N - 2):
    diff0 = MAXINT
    diff2 = MAXINT
    csAmid1 = csA[mid1]

    # mid0 search
    for i in range(mid0, mid1):
        # tmpp, tmpq, tmpdiff0 = getsumanddiff(0, i, mid1)
        tmpp = csA[i]
        tmpq = csAmid1 - tmpp
        tmpdiff0 = abs(tmpp - tmpq)
        if diff0 > tmpdiff0:
            mid0 = i
            diff0 = tmpdiff0
            p = tmpp
            q = tmpq
        else:
            break

    # mid2 search
    start = mid1 if mid2 < mid1 else mid2
    for i in range(start, N - 1):
        # tmpr, tmps, tmpdiff2 = getsumanddiff(mid1+1, i, N - 1)
        csAi = csA[i]
        tmpr = csAi - csAmid1
        tmps = csAN - csAi
        tmpdiff2 = abs(tmpr - tmps)
        if diff2 > tmpdiff2:
            mid2 = i
            diff2 = tmpdiff2
            r = tmpr
            s = tmps
        else:
            break

    tmpdiff = max(p, q, r, s) - min(p, q, r, s)
    if diff > tmpdiff:
        diff = tmpdiff

print(diff)


### FIXED CODE ###

import numpy as np
import math

global csA
MAXINT = 2 ** 63 - 1

def getsumanddiff(i, j, k):
    tmp = csA[j+1]
    p = tmp - csA[i]
    q = csA[k+1] - tmp
    return p, q, abs(p - q)

N = int(input())
# A = np.array(list(map(int, input().split())))
# csA = np.cumsum(A)

csA = [0] * (N+1)
for i, v in enumerate(input().split()):
    csA[i+1] = csA[i] + int(v)

# init
mid0 = 0
mid2 = 2

p, q, r, s = [0]*4
diff = MAXINT

csAN = csA[N]
for mid1 in range(1, N - 2):
    diff0 = MAXINT
    diff2 = MAXINT
    csAmid1 = csA[mid1+1]

    # mid0 search
    for i in range(mid0, mid1):
        # tmpp, tmpq, tmpdiff0 = getsumanddiff(0, i, mid1)
        tmpp = csA[i+1]
        tmpq = csAmid1 - tmpp
        tmpdiff0 = abs(tmpp - tmpq)
        if diff0 > tmpdiff0:
            mid0 = i
            diff0 = tmpdiff0
            p = tmpp
            q = tmpq
        else:
            break

    # mid2 search
    start = mid1 if mid2 < mid1 else mid2
    for i in range(start, N - 1):
        # tmpr, tmps, tmpdiff2 = getsumanddiff(mid1+1, i, N - 1)
        csAi = csA[i+1]
        tmpr = csAi - csAmid1
        tmps = csAN - csAi
        tmpdiff2 = abs(tmpr - tmps)
        if diff2 > tmpdiff2:
            mid2 = i
            diff2 = tmpdiff2
            r = tmpr
            s = tmps
        else:
            break

    tmpdiff = max(p, q, r, s) - min(p, q, r, s)
    if diff > tmpdiff:
        diff = tmpdiff

print(diff)
### BUGGY CODE ###

N = int(input())
W = []
G = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    W.append((a,b))
    G[a].append(b)
    G[b].append(a)
K = 0
for i in range(1,N+1):
    n = len(G[i])
    K = max(K,n)
print(K)
C = [[i for i in range(1,K+1)] for j in range(N+1)]
import copy 
w = copy.deepcopy(W)
d = {}
w.sort()
for i in range(N-1):
    a,b = w[i]
    x = C[a].pop(0)
    C[b].remove(x)
    d[a+b*N] = x
for i in range(N-1):
    a,b = W[i]
    print(d[a+b*N])

### FIXED CODE ###

N = int(input())
W = []
G = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    W.append((a,b))
    G[a].append(b)
    G[b].append(a)
K = 0
for i in range(1,N+1):
    n = len(G[i])
    K = max(K,n)
print(K)
d = {}
D = {}
D[1] = 1
k = 1
H = []
list = [1]
sumi = []
while list:
    x = list.pop(0)
    sumi.append(x)
    Y = G[x]
    k = D[x] + 1
    while Y:
        y = Y.pop(0)
        if x in G[y]:
            G[y].remove(x)
        if k > K:
            k -= K
        list.append(y)
        d[(x,y)] = k
        D[y] = k 
        k += 1
        if k > K:
            k -= K
                
for i in range(N-1):
    a,b = W[i]
    print(d[(a,b)])
### BUGGY CODE ###

def ri(): return int(input())
def rli(): return list(map(int, input().split()))
def rls(): return list(map(str, input().split()))
def pl(a): print(" ".join(list(map(str, a))))
def ma():return map(int,input().split())
def nli(x):return [input for _ in range(x)]
def hukusuu(): 
  listA=[] #appendのために宣言が必要
  while True:
    try:listA.append(list(map(int,input().split())))
    except:break #または、quit(),os.exit()をして止める。
  return listA
from itertools import accumulate as acc 
import operator as op
import copy as cp
import math
from bisect import bisect_left as bisl
from bisect import bisect_right as bisr
def ifif(s):
  if s:print("Yes")
  else:print("No")
def primes(x):
      if x < 2: return []
      primes = [i for i in range(x)]
      primes[1] = 0 # 1は素数ではない
      for prime in primes:
          if prime > math.sqrt(x): break
          if prime == 0: continue
          for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0
      return [prime for prime in primes if prime != 0]
def euclid(x,y):
  if x%y==0:
    return y
  else:
    return euclid(y,x%y)

a,b=ma()
a,b=min(a,b),max(a,b)
gcdab=euclid(b,a)

#print(gcdab)
#print(primes(gcdab+1))
b=[]
hoshii=[aru for aru in primes(gcdab+1) if gcdab%aru==0]
#print(hoshii)
print(len(hoshii)+1)

### FIXED CODE ###

from fractions import *;g=gcd(*map(int,input().split()));c=i=1
while i*i<=g and g>1:
  i+=1;c+=g%i<1
  while g%i<1:g/=i
print(c+(g>1))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, M: int, A: "List[int]"):
    cs = [0, 2 , 5 , 5 , 4 , 5 , 6 , 3 , 7 , 6 ]
    dp = [[-float('inf')] * (N + 1) for _ in range(N // 2 + 1)]
    for i in range(len(dp)):
        dp[i][0] = 0

    for i in range(len(dp) - 1):
        for j in range(len(dp[i])):
            for a in A:
                c = cs[a]
                if j + c <= N:
                    dp[i+1][j + c] = max(dp[i+1][j + c], 10 * dp[i][j] + a)
    return dp[-1][N]


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(M) ]  # type: "List[int]"
    result = solve(N, M, A)
    print(result)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, M: int, A: "List[int]"):
    A.sort(reverse=True)
    cs = [0, 2 , 5 , 5 , 4 , 5 , 6 , 3 , 7 , 6 ]
    dp = [-float('inf')] * (N + 1)

    dp[0] = 0
    for i in range(1, len(dp)):
        for a in A:
            c = cs[a]
            if 0 <= i - c:
                dp[i] = max(dp[i], dp[i-c] + 1)
    i = N
    ret = 0
    while 0 < dp[i]:
        for a in A:
            c = cs[a]
            if (0 <= i - c) and (dp[i] == (dp[i - c] + 1)):
                i -= c
                ret = 10 * ret + a
                break
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(M) ]  # type: "List[int]"
    result = solve(N, M, A)
    print(result)

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

# https://atcoder.jp/contests/abc162/tasks/abc162_d

N = int(input())
S = input()

ans = 0
for i in range(N):
    for j in range(i, N):
        for k in range(j, N):
            if j - i == k - j:
                continue

            if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
                ans += 1

print(ans)


### FIXED CODE ###

# https://atcoder.jp/contests/abc162/tasks/abc162_d

N = int(input())
S = input()


def colors(target, a, b):
    for i in range(N):
        for j in range(i + 1, N):
            if S[i] == a and S[j] == b:
                target[i] += 1


rg = [0 for _ in range(N)]
colors(rg, 'R', 'G')
gr = [0 for _ in range(N)]
colors(gr, 'G', 'R')

gb = [0 for _ in range(N)]
colors(gb, 'G', 'B')
bg = [0 for _ in range(N)]
colors(bg, 'B', 'G')

rb = [0 for _ in range(N)]
colors(rb, 'R', 'B')
br = [0 for _ in range(N)]
colors(br, 'B', 'R')

ans = 0
for i in range(N):
    if S[i] == 'B':
        for j in range(i + 1, N):
            ans += rg[j]
            ans += gr[j]

            k = j + j - i
            if k >= N:
                continue
            if S[i] == 'B' and S[j] == 'R' and S[k] == 'G':
                ans -= 1
            if S[i] == 'B' and S[j] == 'G' and S[k] == 'R':
                ans -= 1

    if S[i] == 'R':
        for j in range(i + 1, N):
            ans += gb[j]
            ans += bg[j]

            k = j + j - i
            if k >= N:
                continue
            if S[i] == 'R' and S[j] == 'G' and S[k] == 'B':
                ans -= 1
            if S[i] == 'R' and S[j] == 'B' and S[k] == 'G':
                ans -= 1

    if S[i] == 'G':
        for j in range(i + 1, N):
            ans += rb[j]
            ans += br[j]

            k = j + j - i
            if k >= N:
                continue
            if S[i] == 'G' and S[j] == 'R' and S[k] == 'B':
                ans -= 1
            if S[i] == 'G' and S[j] == 'B' and S[k] == 'R':
                ans -= 1

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

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

max = -1
for x in range(N+1):
  tmp = int(A*x/B) - A*int(x/B)
  if tmp >= max:
    max = tmp

print(max)


### FIXED CODE ###

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

if N <= B-1:
  max = int(A*N/B) - A*int(N/B)
else:
  max = int(A*(B-1)/B) - A*int((B-1)/B)

print(max)
### BUGGY CODE ###

N, M = map(int, input().split())
A = sorted([int(i) for i in input().split()])

min_A = A[0]

BC = [[int(i) for i in input().split()] for _ in range(M)]

for B, C in BC :
    if C > min_A :
        A += [C] * B
        A = sorted(A)[B:]
        min_A = A[0]

print(sum(A))


### FIXED CODE ###

N, M = map(int, input().split())
A = [[1, int(i)] for i in input().split()]
BC = A + [[int(i) for i in input().split()] for _ in range(M)]

BC.sort(key=lambda x: x[1], reverse=True)

i = 0
res = 0

for B, C in BC :
    if i + B <= N :
        res += C * B
        i += B
    else :
        res += C * (N - i)
        break

print(res)
### BUGGY CODE ###

N = int(input())
S = input()
R = 0
G = 0
B = 0
notToAllow = 0


for i in range(0,N):
    if S[i] == "R":
        R = R + 1
    elif S[i] == "G":
        G = G + 1
    else:
        B = B + 1

total = R*G*B

for i in range(0,N):
    for j in range(0,(N//2)+1):
        if(j+j+i < N):
            if ((S[i] != S[i+j])):
                if(S[i] != S[i+j+j]):
                    if(S[i+j] != S[i+j+j]):
                        notToAllow = notToAllow + 1

print(R*G*B - notToAllow)


### FIXED CODE ###

N = int(input())
S = input()
R = 0
G = 0
B = 0
notToAllow = 0


for i in range(0,N):
    if S[i] == "R":
        R = R + 1
    elif S[i] == "G":
        G = G + 1
    else:
        B = B + 1

total = R*G*B

for i in range(0,N):
    for j in range(0,(N//2)+1):
        if(j+j+i < N):
            if ((S[i] != S[i+j])):
                if(S[i] != S[i+j+j]):
                    if(S[i+j] != S[i+j+j]):
                        notToAllow = notToAllow + 1

print(R*G*B - notToAllow)
### BUGGY CODE ###

from sys import stdin, stdout # only need for big input

MOD = int(1e9+7)

def pow_mod(a , p , m):
    if p < 2:
        ans = 1
        for _ in range(p):
            ans *= a
            if ans >= m:
                ans = ans % m
        return ans
    ans = pow_mod(a , p //2 , m)
    ans = ans * ans

    if ans >= m :
        ans = ans % m
    if p % 2 :
        ans = ans * a 
        if ans >= m :
            ans = ans % m 
    return ans

    

def solve():
    n = int(input())
    A = [int(inp) for inp in input().split()]
    count_1 = [0] * 61 
    pow_2 = [pow_mod(2, i, MOD) for i in range(61)]
    for a in A :
        x = a
        while x :
           for i in range(61):
               if x & 1 :
                   count_1[i] += 1
               x = x >> 1
    # print(count_1)
    # print(pow_2)
    sum = 0
    # print(len(pow_2))
    # print(len(count_1))
    # for a in A:
    #     x = a
    #     while x :
    #         for i in range(61):
    #             # print(i)
    #             if x & 1:
    #                 sum += pow_2[i] * (n - count_1[i])
    #             else:
    #                 sum += pow_2[i] * (count_1[i])

    #             if sum >= MOD:
    #                 sum = sum % MOD
    #             x = x >> 1 
    for i in range(61):
        sum += pow_2[i] * count_1[i] * ( n - count_1[i])
        if sum >= MOD:
            sum = sum % MOD
    # print(sum)
    #sum = (sum * pow_mod(2, MOD - 2, MOD) ) % MOD
    print(sum)


def main():
    solve()


if __name__ == "__main__":
    main()

### FIXED CODE ###

from sys import stdin, stdout # only need for big input

MOD = int(1e9+7)

def pow_mod(a , p , m):
    if p < 2:
        ans = 1
        for _ in range(p):
            ans *= a
            if ans >= m:
                ans = ans % m
        return ans
    ans = pow_mod(a , p //2 , m)
    ans = ans * ans

    if ans >= m :
        ans = ans % m
    if p % 2 :
        ans = ans * a 
        if ans >= m :
            ans = ans % m 
    return ans

    

def solve():
    n = int(input())
    A = [int(inp) for inp in input().split()]
    count_1 = [0] * 61 
    pow_2 = [pow_mod(2, i, MOD) for i in range(61)]
    for a in A :
        x = a
        while x :
           for i in range(61):
               if x & 1 :
                   count_1[i] += 1
               x = x >> 1
    # print(count_1)
    # print(pow_2)
    sum = 0
    # print(len(pow_2))
    # print(len(count_1))
    # for a in A:
    #     x = a
    #     while x :
    #         for i in range(61):
    #             # print(i)
    #             if x & 1:
    #                 sum += pow_2[i] * (n - count_1[i])
    #             else:
    #                 sum += pow_2[i] * (count_1[i])

    #             if sum >= MOD:
    #                 sum = sum % MOD
    #             x = x >> 1 
    for i in range(61):
        sum += pow_2[i] * count_1[i] * ( n - count_1[i])
        if sum >= MOD:
            sum = sum % MOD
    # print(sum)
    #sum = (sum * pow_mod(2, MOD - 2, MOD) ) % MOD
    print(sum)


def main():
    solve()


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

L = raw_input()
L = L.split()
count = 0
for i, val in enumerate(L):
    L[i] = int(val)
while (L[0] > 0) | (L[1] > 0):
    if L[2] > 0:
        if L[0] > 0:
            L[0] -= 1
            count += 1
        else:
            L[1] -= 1
            count += 2
        L[2] -= 1
    else:
        L[1] -= 1
        count += 1
if L[2] > 0:
    count += 1
print(count)




### FIXED CODE ###

L = raw_input()
L = L.split()
count = 0
for i, val in enumerate(L):
    L[i] = int(val)
sum = L[0] + L[1]
if sum < L[2]-1:
    count = L[0] + 2*L[1] + 1
else:
    count = L[2] + L[1]
print(count)
### BUGGY CODE ###

n,m = map(int,input().split())
all_li = []
ma = {}
for _ in range(m):
    p,y = map(int,input().split())
    all_li.append((p,y))
    if p in ma:
        ma[p].append(y)
    else:
        ma[p] = [y]
#print(all_li)
#[[1, 32], [2, 63], [1, 12]]
#print(ma)
# {1: [32, 12], 2: [63]}
sorted_li = [[] for _ in range(n)]
for k,v in ma.items():
    sorted_li[k-1] = list(sorted(v))
#print(ma)
for a in all_li:
    count = sorted_li[a[0]-1].index(a[1]) + 1
    print(str(a[0]).zfill(6)+str(count).zfill(6))


### FIXED CODE ###

from bisect import bisect_right
n,m = map(int,input().split())
all_li = []
ma = {}
for _ in range(m):
    p,y = map(int,input().split())
    all_li.append((p,y))
    if p in ma:
        ma[p].append(y)
    else:
        ma[p] = [y]
#print(all_li)
#[[1, 32], [2, 63], [1, 12]]
#print(ma)
# {1: [32, 12], 2: [63]}
sorted_li = [[] for _ in range(n)]
for k,v in ma.items():
    sorted_li[k-1] = list(sorted(v))
#print(ma)
for a in all_li:
    #print(a[1],sorted_li[a[0]-1])
    count = bisect_right(sorted_li[a[0]-1],a[1],)
    #count = sorted_li[a[0]-1].index(a[1]) + 1
    print(str(a[0]).zfill(6)+str(count).zfill(6))