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

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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



def f(ai, ki):
    if ai < ki: return 0
    elif ai % ki == 0 :return ai // ki
    d = ai // ki + 1
    return f(ai - max(ai % ki // d, 1) * d, ki)


n = I()
ret = 0
for i in range(n):
    a, k = LI()
    ret ^= f(a, k)

print("Takahashi" if ret else "Aoki")

### FIXED CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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



def solve(n, k):
    if n % k == 0:
        return n // k
    diff = (n // k) + 1
    target = n - n % k
    if (n - target) % diff == 0:
        return solve(target, k)
    n -= -((-(n - target)) // diff) * diff
    return solve(n, k)


n = I()
ret = 0
for i in range(n):
    a, k = LI()
    ret ^= solve(a, k)

print("Takahashi" if ret else "Aoki")
### BUGGY CODE ###

s=input()
q=int(input())
for qq in range(q):
  l=list(input().split())
  if l[0]=='1':
    s=s[::-1]
  else:
    if l[1]=='1':
      s=l[2]+s
    else:
      s+=l[2]
print(s)

### FIXED CODE ###

s=input()
q=int(input())
cnt=0
front=[]
rear=[]
for qq in range(q):
  l=list(input().split())
  if l[0]=='1':
    cnt+=1
  else:
    if (cnt+int(l[1]))%2==1:
      front.append(l[2])
    else:
      rear.append(l[2])
front=''.join(front[::-1])
rear=''.join(rear)
s=front+s+rear
print(s if cnt%2==0 else s[::-1])
### BUGGY CODE ###

a,b,c,d=map(int,input().split())
p=998244353
n=c-a+2
m=d-b+2
data=[[0]*(m)for i in range(n)]

data[1][1]=1

#print(data)

for i in range(1,n):
    gyou=a+i-1
    for j in range(1,m):
        retu=b+j-1
        if(i*j==1):
            continue
        data[i][j]=data[i-1][j]*retu+data[i][j-1]*gyou-data[i-1][j-1]*(gyou-1)*(retu-1)%p
        #print(gyou,retu,i,j,data[i][j])
#print(data)
print(data[n-1][m-1]%p)

### FIXED CODE ###

a,b,c,d=map(int,input().split())
p=998244353
n=c-a+2
m=d-b+2
data=[[0]*(m)for i in range(n)]

data[1][1]=1

#print(data)

for i in range(1,n):
    gyou=a+i-1
    for j in range(1,m):
        retu=b+j-1
        if(i*j==1):
            continue
        data[i][j]=(data[i-1][j]*retu%p)+(data[i][j-1]*gyou%p)-((data[i-1][j-1]*(gyou-1)%p)*(retu-1)%p)
        data[i][j]=data[i][j]%p
        #print(gyou,retu,i,j,data[i][j])
#print(data)
print(data[n-1][m-1]%p)
### BUGGY CODE ###

N,K=map(int,input().split())
if N%K==0:
    print(0)
    exit()
while N>abs(N-K):
    N=abs(N-K)
print(N)

### FIXED CODE ###

N,K=map(int,input().split())
if N%K==0:
    print(0)
    exit()
ans=N%K
if ans>abs(ans-K):
    print(abs(ans-K))
else:
    print(ans)
### BUGGY CODE ###

def solve():
    n, k = map(int, input().split())
    xs = list(map(int, input().split()))
    dists = []
    for i in range(n - k + 1):
        part = xs[i:i + k]
        dist = min(abs(part[0]) + abs(part[0] - part[-1]), abs(part[-1]) + abs(part[0] - part[-1]))
        dists.append(dist)
    return min(dists)


if __name__ == "__main__":
    print(solve())


### FIXED CODE ###

def solve():
    n, k = map(int, input().split())
    xs = list(map(int, input().split()))
    min_dist = 10 ** 9
    for i in range(n - k + 1):
        length = abs(xs[i] - xs[i + k - 1])
        dist = min(abs(xs[i]) + length, abs(xs[i + k - 1]) + length)
        if dist < min_dist:
            min_dist = dist
    return min_dist


if __name__ == "__main__":
    print(solve())
### BUGGY CODE ###

from fractions import gcd
from functools import reduce

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

L = reduce(lambda x, y: x * y // gcd(x, y), A)

ans = 0
for i in range(N):
    ans += L // A[i]
    ans %= MOD
print(ans)


### FIXED CODE ###

from fractions import gcd
from functools import reduce

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

L = reduce(lambda x, y: x * y // gcd(x, y), A)

ans = 0
for i in range(N):
    ans += L // A[i]
print(ans % MOD)
### BUGGY CODE ###

N = int(input())
a = [sorted(list(input())) for i in range(N)]
b = 0
for i in a:
 b = b + a.count(i) - 1
print(int(b / 2))


### FIXED CODE ###

from collections import Counter

N = int(input())
a = [''.join(sorted(input())) for i in range(N)]
count = Counter(a).values()
b = 0
for i in count:
    b = b + i * (i-1)
b=int(b/2)
print(b)
### BUGGY CODE ###

n, U, V = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
U -= 1
V -= 1

g = [[] for _ in range(n)]
for a, b in ab:
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

WHITE = 0
GRAY = 1
BLACK = 2


def dfs(s):
    color = [WHITE] * n
    d = [-1] * n
    f = [-1] * n
    p = [-1] * n
    t = 0
    stack = [s]
    color[s] = GRAY
    d[s] = t
    t += 1
    while stack:
        u = stack[-1]
        for v in g[u]:
            if color[v] == WHITE:
                color[v] = GRAY
                d[v] = t
                p[v] = u
                t += 1
                stack.append(v)
                break
        else:
            color[u] = BLACK
            f[u] = t
            t -= 1
            stack.pop()

    return d


dv = dfs(V)

du = dfs(U)

ans = 0
for due, dve in zip(du, dv):
    if dve > due:
        ans = max(ans, dve - 1)

print(ans)


### FIXED CODE ###

from collections import deque


def bfs(s):
    d = [-1] * n
    p = [-1] * n
    dq = deque([s])
    d[s] = 0

    while dq:
        u = dq.popleft()
        for v in adj[u]:
            if d[v] == -1:
                d[v] = d[u] + 1
                p[v] = u
                dq.append(v)

    return d, p


n, takahashi, aoki = map(int, input().split())
takahashi -= 1
aoki -= 1
ab = [list(map(int, input().split())) for _ in range(n - 1)]

adj = [[] for _ in range(n)]
for a, b in ab:
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)

depth, par = bfs(takahashi)
aoki_move = depth[aoki] // 2 + 1
root = aoki
for _ in range(aoki_move):
    child = root
    root = par[root]

adj[child].remove(root)
adj[root].remove(child)

depth2, par2 = bfs(root)

aoki_move += max(depth2) - 1
print(aoki_move)
### BUGGY CODE ###

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

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

for i in range(N):
	for j in range(M):
		if S[i]==T[j]:
			for k in range(i):
				for l in range(j):
					dp[i][j]+=dp[k][l]
			dp[i][j]+=1

ans=1
for i in range(N):
	for j in range(M):
		ans+=dp[i][j]
		ans%=mod

print(ans)

### FIXED CODE ###

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

dp=[[0 for j in range(M+1)] for i in range(N+1)]
Sum=[[0 for j in range(M+1)] for i in range(N+1)]

for i in range(1,N+1):
	for j in range(1,M+1):
		if S[i-1]==T[j-1]:
			dp[i][j]=Sum[i-1][j-1]
#			for k in range(1,i):
#				for l in range(1,j):
#					dp[i][j]+=dp[k][l]
			dp[i][j]+=1
		Sum[i][j]=(Sum[i-1][j]+Sum[i][j-1]-Sum[i-1][j-1]+dp[i][j])%mod

print(Sum[N][M]+1)
### BUGGY CODE ###

from collections import deque
N = int(input())
A = [int(input()) for _ in range(N)]

# d = deque()
R = deque(A)
R.append(0)
L = deque([0])

for i in A:
  R.popleft()
  print(max(max(L), max(R)))
  L.append(i)
  

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
B = A[:]
B.sort(reverse=True)
# print(A)
fmax = B[0]
smax = B[1]
for i in A:
  if i == fmax:
    print(smax)
  else:
    print(fmax)
### BUGGY CODE ###

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

l_=[int(n) for n in range(a,b+1)]

for i in range(M-1):
  c,d=map(int,input().split())
  l__=[n for n in range(c,d+1)]
  l_=list(set(l_)&set(l__))
  
print(len(l_))

### FIXED CODE ###

n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
L=[]
R=[]
for i in range(m):
  L.append(l[i][0])
  R.append(l[i][1])
print(max(min(R)-max(L)+1,0))
### BUGGY CODE ###

n, k = map(int, input().split())
L = []

for i in range(n):
  a, b = map(int, input().split())
  for j in range(b):
    L.append(a)

L.sort()
print(L[k-1])

### FIXED CODE ###

n, k = map(int, input().split())
L = [0]*(pow(10,5)+1)

for i in range(n):
  a, b = map(int, input().split())
  L[a] += b

s = 0
for i in range(pow(10,5)+1):
  s += L[i]
  if s >= k:
    print(i)
    break
### BUGGY CODE ###

N = int(input())
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

total =  0
for i in range(1,N+1):
    a = i * len(make_divisors(i))
    total += a
print(total)

### FIXED CODE ###

n=int(input())
ans=0
for i in range(1,n+1): #各iについて、i*(1～n//iまでの総和)を足し合わせればよい
 k=n//i
 ans+=i*(k*(k+1)//2)
print(ans)
### BUGGY CODE ###

# coding:utf-8
n = int(input())
a = list(map(int, input().split()))
ans = 1

for i in range(n):
    ans = ans * a[i]

if ans > 10**18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

# coding:utf-8
n = int(input())
a = list(map(int, input().split()))
ans = 1

if 0 in a:
    print(0)
    exit()

for i in range(n):
    ans = ans * a[i]
    if ans > 10**18:
        print(-1)
        exit()

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

h,w,m = map(int,input().split())
row = [0]*(h+1)
col = [0]*(w+1)
bombs = set([])
for i in range(m):
  a,b = map(int,input().split())
  row[a] += 1
  col[b] += 1
  bombs.add((a,b))
r,c = max(row),max(col)
for i in range(1,h+1):
  if row[i]!=r:
    continue
  for j in range(1,w+1):
    if col[j]!=c:
      continue
    if (i,j) not in bombs:
      print(r+c)
      exit()
else:
  print(r+c-1)

### FIXED CODE ###

h,w,m = map(int,input().split())
row = [0]*(h+1)
col = [0]*(w+1)
bombs = set([])
for i in range(m):
  a,b = map(int,input().split())
  row[a] += 1
  col[b] += 1
  bombs.add((a,b))
r,c = max(row),max(col)
rcnt,ccnt = 0,0
for v in row:
  if v==r:
    rcnt += 1
for v in col:
  if v==c:
    ccnt += 1
doubled = 0
for i,j in bombs:
  if row[i]==r and col[j]==c:
    doubled += 1
if doubled==rcnt*ccnt:
  print(r+c-1)
else:
  print(r+c)
### BUGGY CODE ###

import collections

s = input()
t = input()
s_index = {}
for pos, el in enumerate(s):
	if el in s_index:
		s_index[el].append(pos)
	else:
		s_index[el] = [pos]
check = all([i in s_index for i in t])
if not check:
	ans = -1
else:
	ans = 0
	t_size = len(t)
	s_size = len(s)
	for i in range(t_size):
		target = t[i]
		cursor = ans % s_size
		find = False
		for j in s_index[target]:
			if j >= cursor:
				find = True
				break
		diff = j - cursor + 1 if find else s_index[target][0] + s_size - cursor + 1
		ans += diff
		
print(ans)
	

### FIXED CODE ###

import collections
import bisect

s = input()
t = input()
s_index = {}
	
for pos, el in enumerate(s):
	if el in s_index:
		s_index[el].append(pos)
	else:
		s_index[el] = [pos]
check = all([i in s_index for i in t])
if not check:
	ans = -1
else:
	ans = 0
	t_size = len(t)
	s_size = len(s)
	for i in range(t_size):
		target = t[i]
		cursor = ans % s_size
		find = False
		if cursor > s_index[target][-1]:
			find = False
		else:
			j = bisect.bisect_left(s_index[target], cursor)
			find = True
		diff = s_index[target][j] - cursor + 1 if find else s_index[target][0] + s_size - cursor + 1
		ans += diff
		
print(ans)
### BUGGY CODE ###

mod = 10 ** 9 + 7

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

dp = [[0] * (M + 1) for _ in range(N + 1)]
dp[0][0] = 1

for i in range(N + 1):
    for j in range(M + 1):
        if 1 <= i and 1 <= j and S[i - 1] == T[j - 1]:
            dp[i][j] += dp[i - 1][j - 1]
        if 1 <= i:
            dp[i][j] += dp[i - 1][j]
        if 1 <= j:
            dp[i][j] += dp[i][j - 1]
        if 1 <= i and 1 <= j:
            dp[i][j] -= dp[i - 1][j - 1]
        dp[i][j] %= mod

print(dp[N][M])


### FIXED CODE ###

mod = 10 ** 9 + 7

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

dp = [[0] * (M + 1) for _ in range(N + 1)]
dp[0][0] = 1

for i in range(N + 1):
    for j in range(M + 1):
        if 1 <= i and 1 <= j and S[i - 1] == T[j - 1]:
            dp[i][j] += dp[i - 1][j - 1]
        if 1 <= i:
            dp[i][j] += dp[i - 1][j]
        if 1 <= j:
            dp[i][j] += dp[i][j - 1]
        if 1 <= i and 1 <= j:
            dp[i][j] -= dp[i - 1][j - 1]
        dp[i][j] %= mod

print(dp[N][M])
### BUGGY CODE ###

N = int(input())
C = list(input())
import copy
D = []
flag = 0
ans = 0

for p in range(N):
    if C[p] == "R":
        D += ["0"]
    else:
        D += ["1"]



def change(x,y):
    global ans
    hoge = copy.deepcopy(D[x])
    D[x] = D[y]
    D[y] = hoge
    ans += 1

def color(x):
    global ans
    ans += 1
    if D[x] == "0":
        D[x] = "1"
    elif D[x] == "1":
        D[x] = "0"

while flag == 0:
    for q in range(N):
        if D[q] == "1":
            for s in range(N):
                if D[N-s-1] =="0" and q < N-s-1:
                    change(q,N-s-1)
                    break
                
    for r in range(N):
        if int("".join(D),2) == 2**r-1:
            flag = 1

print(ans)


### FIXED CODE ###

N = int(input())
C = list(input())
import copy
D = []
flag = 0
ans = 0
keisan = 0

for p in range(N):
    if C[p] == "R":
        D += ["0"]
    else:
        D += ["1"]



def change(x,y):
    global ans
    hoge = copy.deepcopy(D[x])
    D[x] = D[y]
    D[y] = hoge
    ans += 1

def color(x):
    global ans
    ans += 1
    if D[x] == "0":
        D[x] = "1"
    elif D[x] == "1":
        D[x] = "0"

zero = D.count("0")
ichi = D.count("1")

for p in range(zero):
    if D[p] == "1":
        ans += 1


"""
while flag == 0:

    for r in range(N):
        if int("".join(D),2) == 2**r-1:
            flag = 1

    if flag == 0:
        for q in range(N):
            if D[q] == "1":
                for s in range(N):
                    keisan += 1
                    if D[N-s-1] =="0" :
                        if q < N-s-1:
                            change(q,N-s-1)
                        break
            else:
                continue
            break
"""
print(ans)
### BUGGY CODE ###

from collections import deque
import numpy as np

num = list(map(int,input().split()))
field = [list(input()) for i in range(num[0])]
q_r = deque([])
q_c = deque([])
seen = np.zeros((num[0],num[1]))
step_r = [1,0,-1,0]
step_c = [0,1,0,-1]

for i in range(num[0]):
  for j in range(num[1]):
    if field[i][j] == "#":
      q_r.append(i)
      q_c.append(j)
      g_r = 0
      g_c = 0

while q_r:
  r = q_r.popleft()
  c = q_c.popleft()

  for i in range(4):
    next_r = r + step_r[i]
    next_c = c + step_c[i]
    
    if (next_r<0) or (num[0]<=next_r) or (next_c<0) or (num[1]<=next_c) or (field[next_r][next_c] == "#"):
      continue
    
    field[next_r][next_c] = "#"
    q_r.append(next_r)
    q_c.append(next_c)
    seen[next_r][next_c] = seen[r][c] + 1
#    print(seen[next_r][next_c],next_r,next_c)
    g_r = next_r
    g_c = next_c

print(int(seen[g_r][g_c]))

### FIXED CODE ###

def main():
    h,w = map(int,input().split())
    a = []
    for i in range(h):
        a.append(input())

    used = [True]*(h*w)

    p = []
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                p.append(i*w+j)
                used[i*w+j] = False


    
    res = 0
    while p:
        tank = []
        for e in p:
            if e>w-1 and used[e-w]:
                tank.append(e-w)
                used[e-w] = False
            if e%w > 0 and used[e-1]:
                tank.append(e-1)
                used[e-1] = False
            if e<(h-1)*w and used[e+w]:
                tank.append(e+w)
                used[e+w] = False
            if e%w<w-1 and used[e+1]:
                tank.append(e+1)
                used[e+1] =  False
        p = tank
        res += 1
    print(res-1)

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

import numpy as np

N = int(input())
A = list(map(int, input().split(' ')))

modn = int(1e9 + 7)

A = np.mod(A, modn)

ruiseki = []
for i in range(len(A)-1):
    tmp_sum = sum(A[i+1:len(A)])
    ruiseki.append(tmp_sum)

ret = 0
for i in range(0, len(A)-1):
  ret += A[i] * ruiseki[i]

print(np.mod(ret, modn))

### FIXED CODE ###

import numpy as np

N = int(input())
A = list(map(int, input().split(' ')))

modn = int(1e9 + 7)

ruiseki = sum(A)

ret = 0
for i in range(0, len(A)-1):
  ruiseki -= A[i]
  ret += A[i] * ruiseki

print(np.mod(ret, modn))
### BUGGY CODE ###

N = int(input())
H = list(map(int, input().split()))
F = "Yes"

for i in range(0, N):
	for k in range(i+1, N):
		if H[i] > H[k] + 1:
			F = "No"

print(F)


### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
F = "Yes"
l = H[0]

for i in range(1, N):
	if l < H[i]:
		l = H[i]
	if l - 1 > H[i]:
		F = "No"
		break

print(F)
### BUGGY CODE ###

x,y,z,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

for l in [b,c]:
    p = []
    for i in a:
        for j in l:
            p.append(i+j)
    a = sorted(p, reverse=True)[:k]

for i in a:
    print(i)


### FIXED CODE ###

x,y,z,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

for l in [b,c]:
    p = []
    for i in a:
        for j in l:
            p.append(i+j)
    a = sorted(p, reverse=True)[:k]

for i in a:
    print(i)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

done_list = [1]
ans = 0
tmp = 1
for _ in range(N):
    if A[tmp-1] in done_list:
        print(-1)
        exit(0)
    done_list.append(A[tmp-1])
    tmp = A[tmp-1]
    ans += 1
    if tmp == 2:
        print(ans)
        exit(0)

### FIXED CODE ###

N = int(input())
A = [0] + [int(input()) for _ in range(N)]

done = {}
ans = 0
now = A[1]
while True:
    ans += 1
    if now == 2:
        print(ans)
        exit(0)
    if done.get(now) == None:
        done[now] = True
        now = A[now]
    else:
        break
print(-1)
### BUGGY CODE ###

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

dic = {"":1}
ans = 0

for c in S:
    dic_new = {}         
    for k in dic:    
        if not(c in k):    
            ans += dic[k]    
            ans %= 10**9 + 7    
            dic_new[k+c] = (dic_new.get(k+c,0)+dic[k]) % (10**9+7)
    for k in dic_new:    
        dic[k] = (dic.get(k,0)+dic_new[k])%(10**9+7)
print(ans)      

### FIXED CODE ###

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

tmp = []
for a in "abcdefghijklmnopqrstuvwxyz":      
    tmp.append(S.count(a)+1)
    
ans = 1 
for i in tmp:
    ans = ans * i % (10**9+7)
    
print(ans-1)
### BUGGY CODE ###

N,M = map(int,input().split())
para = []
for i in range(M):
    a,b = map(int,input().split())
    para.append([a,b,i])
para.sort(key = lambda x:(x[0],x[1]))
ans = []
memo = []
for i in range(M):
    if para[i][0] not in memo :
        cnt = 1
        a = format(para[i][0]).zfill(6) + format(cnt).zfill(6)
        ans.append([a,para[i][2]]) 
        memo.append(para[i][0])
    else : 
        cnt += 1
        a = format(para[i][0]).zfill(6) + format(cnt).zfill(6)
        ans.append([a,para[i][2]]) 
ans.sort(key=lambda x:x[1])
for i in range(M):
    print(ans[i][0])

### FIXED CODE ###

N,M = map(int,input().split())
para = []
for i in range(M):
    a,b = map(int,input().split())
    para.append([a,b,i])
para.sort(key = lambda x:(x[0],x[1]))
ans = []
memo = [-1 for i in range(N+1)]
for i in range(M):
    if memo[para[i][0]] == -1 :
        cnt = 1
        a = format(para[i][0]).zfill(6) + format(cnt).zfill(6)
        ans.append([a,para[i][2]]) 
        memo[para[i][0]] = 0
    else : 
        cnt += 1
        a = format(para[i][0]).zfill(6) + format(cnt).zfill(6)
        ans.append([a,para[i][2]]) 
ans.sort(key=lambda x:x[1])
for i in range(M):
    print(ans[i][0])
### BUGGY CODE ###

N = int(input())
A = sorted(list(map(int, input().split())))
memo = {}
ans = 0

for a in A:
    if not a in memo:
        flag = True
        for div in memo:
            if a % div == 0:
                flag = False
                break
        if flag:
            ans += 1
            memo[a] = 1
    else:
        if memo[a] == 1:
            ans -= 1
            memo[a] += 1
        else:
            continue
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
memo = [0]*(10**6+1)

for a in A:
    memo[a] += 1
    if memo[a] < 2:
        for i in range(2*a, 10**6+1, a):
            memo[i] += 1

ans = 0
for a in A:
    if memo[a] == 1:
        ans += 1

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

from bisect import bisect_left as bisect
N,Q = map(int,input().split())
event = [tuple(map(int,input().split())) for i in range(N)]
D = [int(input()) for i in range(Q)]

event.sort(key=lambda x:x[2])

ans = [-1]*Q
neg = [-1]*Q

for s,t,x in event:
    l = bisect(D,s-x)
    r = bisect(D,t-x)
    t = l
    while t < r:
        if neg[t] == -1:
            ans[t] = x
            neg[t] = r
            t += 1
        else:
            t = neg[t]

for i in range(Q):
    print(ans[i])

### FIXED CODE ###

from bisect import bisect_left as bisect
N,Q = map(int,input().split())
event = [tuple(map(int,input().split())) for i in range(N)]
D = [int(input()) for i in range(Q)]

event.sort(key=lambda x:x[2])

ans = [-1]*Q
neg = [-1]*Q

for s,t,x in event:
    l = bisect(D,s-x)
    r = bisect(D,t-x)
    t = l
    while t < r:
        if neg[t] == -1:
            ans[t] = x
            neg[t] = r
            t += 1
        else:
            t = neg[t]

for i in range(Q):
    print(ans[i])