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

def main():
    s = input()
    t = input()

    if is_match_swith_rotation(s, t):
        print('Yes')
    else:
        print('No')

def is_match_swith_rotation(s, t):
    end = len(t)
    while end != 0:
        try:
            pos = s.rfind(t[0], 0, end)
        except ValueError:
            return False
        if s[pos:] + s[:pos] == t:
            return True
        end = pos

    return False

main()

### FIXED CODE ###

def main():
    s = input()
    t = input()

    if is_match_swith_rotation(s, t):
        print('Yes')
    else:
        print('No')

def is_match_swith_rotation(s, t):
    if t in s + s:
        return True
    else:
        return False

main()
### BUGGY CODE ###

h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch -= 1
cw -= 1
dh,dw = map(int,input().split())
dh -= 1
dw -= 1
s = [input() for i in range(h)]

reach = [[False]*w for i in range(h)]
reach[ch][cw] = True

import heapq
q = [[0,ch,cw]]
heapq.heapify(q)

ans = -1
while q:
    cnt,cx,cy = heapq.heappop(q)
    reach[cx][cy] = True
    if cx==dh and cy==dw:
        ans = cnt
        break

    for dx,dy in [[0,1],[0,-1],[1,0],[-1,0]]:
        if not(0<=cx+dx<h and 0<=cy+dy<w):continue
        if s[cx+dx][cy+dy]=='.':
            if not reach[cx+dx][cy+dy]:
                heapq.heappush(q,[cnt,cx+dx,cy+dy])

    for dx in range(-2,3):
        for dy in range(-2,3):
            if [dx,dy] in [[0,0],[0,1],[0,-1],[1,0],[-1,0]]:continue
            if not(0<=cx+dx<h and 0<=cy+dy<w):continue
            if not reach[cx+dx][cy+dy] and s[cx+dx][cy+dy]=='.':
                heapq.heappush(q,[cnt+1,cx+dx,cy+dy])

    

print(ans)



### FIXED CODE ###

h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch -= 1
cw -= 1
dh,dw = map(int,input().split())
dh -= 1
dw -= 1
s = [input() for i in range(h)]

cost = [[-1]*w for i in range(h)]

from collections import deque
q = [[0,ch,cw]]
q = deque(q)

ans = -1
while q:
    cnt,cx,cy = q.popleft()
    if cost[cx][cy]<0:
        cost[cx][cy]=cnt
        for dx in range(-2,3):
            for dy in range(-2,3):
                if 0<=cx+dx<h and 0<=cy+dy<w and s[cx+dx][cy+dy]=='.':
                    if cost[cx+dx][cy+dy]<0:
                        if [dx,dy] in [[1,0],[-1,0],[0,1],[0,-1]]:
                            q.appendleft([cnt,cx+dx,cy+dy])
                        else:
                            q.append([cnt+1,cx+dx,cy+dy])

print(cost[dh][dw])
### BUGGY CODE ###

from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

ans = float('inf')
for n in range(2**N):
    n = bin(n)[2:]
    n = '0'*(N-len(n))+n
    l = []
    for i in range(N):
        if n[i]=='0':
            l.append([A[i],i,0])
        else:
            l.append([B[i],i,1])
    inversion = 0
    for i in range(N):
        for j in range(i+1,N):
            if l[i][0]>l[j][0]:
                inversion += 1
    l.sort()
    d = defaultdict(list)
    for i in range(N):
        v,j,k = l[i]
        if (i-j+k)%2==1:
            d[v].append(i)
    possible = True
    for v in d:
        if len(d[v])%2==1:
            possible = False
        else:
            for i in range(len(d[v])//2):
                if (d[v][2*i+1]-d[v][2*i])%2==1:
                    inversion += d[v][2*i+1]-d[v][2*i]
                else:
                    possible = False
                    break
        if not possible:
            break
    if possible:
        ans = min(ans,inversion)

if ans == float('inf'):
    ans = -1
print(ans)

### FIXED CODE ###

from collections import defaultdict
from operator import itemgetter
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

ans = 1000
for n in range(2**N):
    n = bin(n)[2:]
    if n.count('1')%2!=0:
        continue
    n = '0'*(N-len(n))+n
    l = []
    for i in range(N):
        if n[i]=='0':
            l.append([A[i],i])
        else:
            l.append([B[i],i+1])
    inversion = 0
    for i in range(N):
        if inversion>=ans:
            break
        for j in range(i+1,N):
            if l[i][0]>l[j][0]:
                inversion += 1
    if inversion>=ans:
        continue
    l.sort(key=itemgetter(0))
    d = defaultdict(list)
    for i in range(N):
        v,j = l[i]
        if (i-j)%2==1:
            d[v].append(i)
    possible = True
    for v in d:
        if len(d[v])%2==1:
            possible = False
        else:
            for i in range(len(d[v])//2):
                if (d[v][2*i+1]-d[v][2*i])%2==1:
                    inversion += d[v][2*i+1]-d[v][2*i]
                else:
                    possible = False
                    break
        if not possible:
            break
    if possible:
        ans = min(ans,inversion)

if ans == 1000:
    ans = -1
print(ans)
### BUGGY CODE ###

def main(): 
    s=list(input())
    q=int(input())
    query = [input().split() for i in range(q)]

    for query_list in query:
        if query_list[0] == '1':
            s = s[::-1]
        else:
            if query_list[1] == '1':
                s = s[::-1]
                s.append(query_list[2])
                s = s[::-1]
            else:
                s.append(query_list[2])

    print(''.join(s))

main()

### FIXED CODE ###

s=input()
q=int(input())
query = [input().split() for i in range(q)]

Inv = False #反転しているか
front_str = [] #末尾側
back_str = [] #先頭側

for query_list in query:
    if query_list[0] == '1':
        Inv = not Inv
    else:
        if query_list[1] == '1': #先頭に追加
            if Inv:
                front_str.append(query_list[2])
            else:
                back_str.append(query_list[2])
        else:
            if Inv:
                back_str.append(query_list[2])
            else:
                front_str.append(query_list[2])

answer = "".join(back_str[::-1] + [s] + front_str)

if Inv:
    answer = answer[::-1]

print(answer)
### BUGGY CODE ###

n=int(input())

i=1

for j in range(1,n+1):
  i*=j
  
print(i%(10**9+7))

### FIXED CODE ###

n=int(input())

i=1

for j in range(1,n+1):
  i*=j
  i%=10**9+7
  
print(i)
### BUGGY CODE ###

import numpy as np

mod = 998244353
n, k = map(int, input().split())
left = []
right = []
for _ in range(k):
  l, r = map(int, input().split())
  left.append(l)
  right.append(r)
dp = np.zeros(n+1, dtype=np.int)
dp[1] = 1
for i in range(2, n+1):
  for j in range(k):
    dp[i] += dp[max(0, i - left[j])] - dp[max(0, i - right[j] - 1)]
    dp[i] %= mod
  dp[i] = (dp[i-1] + dp[i]) % mod
print((dp[n] - dp[n-1]) % mod)

### FIXED CODE ###

mod = 998244353
n, k = map(int, input().split())
left = []
right = []
for _ in range(k):
  l, r = map(int, input().split())
  left.append(l)
  right.append(r)
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n+1):
  for j in range(k):
    dp[i] += dp[max(0, i - left[j])] - dp[max(0, i - right[j] - 1)]
    dp[i] %= mod
  dp[i] = (dp[i-1] + dp[i]) % mod
print((dp[n] - dp[n-1]) % mod)
### BUGGY CODE ###

n,y = map(int,input().split())
for i in range(0,n+1):
  for j in range(0,n+1):
    for k in range(0,n+1):
      sum_y = 10000*i + 5000*j + 1000*k
      sum_n = i + j + k
      if sum_y == y and sum_n == n:
        print(i, j ,k)
        break
    else:
      continue
    break
  else:
    continue
  break
if sum_y !=y and sum_n != n:
  print(-1,-1,-1)


### FIXED CODE ###

import itertools
n,y = map(int,input().split())
for i,j in itertools.product(range(0,n+1),range(0,n+1)):
  c = n-i-j
  sum_y = 10000*i + 5000*j + 1000*c
  if sum_y == y and c>=0:     
    print(i,j,c)
    break
else:
  print(-1,-1,-1)
### BUGGY CODE ###

import queue 
N = int(input())
tree = [[]for _ in range(N+1)]
for i in range(1,N):
    a,b = map(int,input().split())
    tree[a].append( [b,i])
    tree[b].append([a,i])

que = queue.Queue()
node = [-1]*(N+1)
edge = [-1]*N
que.put(1)
node[1] = 1
maxi = max([len(i) for i in tree])
color = [[i for i in range(1,maxi+1)] for _ in range(N+1)]
while(True):
    if que.empty():
        break
    start = que.get()
    for i in tree[start]:
        
        if node[i[0]] == -1 :
            que.put(i[0])
            node[i[0]] = 1
        if edge[i[1]] == -1:
            col = max(color[i[0]][0],color[start][0])
            edge[i[1]] = col
            color[i[0]].remove(col)
            color[start].remove(col)
print(maxi)
for i in edge[1:]:
    print(i)

### FIXED CODE ###

import queue 
N = int(input())
tree = [[]for _ in range(N+1)]
for i in range(1,N):
    a,b = map(int,input().split())
    tree[a].append( [b,i])
    tree[b].append([a,i])
 
que = queue.Queue()
node = [-1]*(N+1)
edge = [-1]*N
que.put(1)
node[1] = 1
maxi = 1
start = 0
color = [[] for _ in range(N+1)]
node[1] = 0
while(True):
    if que.empty():
        break
    before = start
    start = que.get()
    col =1
    for i in tree[start]:
        
        if node[i[0]] == -1 :
            que.put(i[0])
        if edge[i[1]] == -1:
            if col == node[start]:
                col += 1
            edge[i[1]] = col
            node[i[0]] = col
            if col > maxi:
                maxi = col
            col +=1
            
print(maxi)
for i in edge[1:]:
    print(i)
### BUGGY CODE ###

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


ans = 0
mod = 7 + 10**9

for i in A:
	i %= mod

for j in range(N-1): 
	for	k in range(j+1, N):
		t = A[j] * A[k] 
		ans += t

ans %= mod
print(ans)

### FIXED CODE ###

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

ans = 0
mod = 7 + 10**9

s = sum(A)
for i in range(N):
	s -= A[i]
	ans += s * A[i]
	ans %= mod

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

from collections import deque
H, W = map(int, input().split())
S = []
for i in range(H):
  S.append(list(input()))

V = {}
for i in range(H):
  for j in range(W):
    V[str(i) + "_" + str(j)] = []
    
for i in range(H):
  for j in range(W):
    
    for dy,dx in [(-1,0), (1,0), (0,-1), (0,1)]:
      y,x = i+dy, j+dx
      if y < 0 or H <= y or x < 0 or W <= x:
        continue
      if S[i][j] == S[y][x]:
        continue
      V[str(i) + "_" + str(j)].append([y,x])
      
ans = 0
visited = [[False for i in range(W)] for j in range(H)]
willsearch = [[False for i in range(W)] for j in range(H)]
Q = deque()
#print(V)
def dfs(y,x):
  wc, bc = 0, 0
  Q.append([y,x])
  while len(Q) > 0:
    b,a = Q.pop()
    #print("pop;", b, a, Q)
    visited[b][a] = True
    if S[b][a] == '.':
      wc += 1
    else:
      bc += 1
    for q,p in V[str(b) + "_" + str(a)]:
      #print("yeah:", q,p)
      if visited[q][p] or willsearch[q][p]:
        continue
      Q.append([q,p])
      willsearch[q][p] = True
    #print(b,a,"|",Q)
  #print(y,x,wc,bc)
  return wc*bc

for i in range(H):
  for j in range(W):
    ans += dfs(i,j)
    
print(ans)

### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
S = []
for i in range(H):
  S.append(list(input()))

V = {}
for i in range(H):
  for j in range(W):
    V[str(i) + "_" + str(j)] = []
    
for i in range(H):
  for j in range(W):
    
    for dy,dx in [(-1,0), (1,0), (0,-1), (0,1)]:
      y,x = i+dy, j+dx
      if y < 0 or H <= y or x < 0 or W <= x:
        continue
      if S[i][j] == S[y][x]:
        continue
      V[str(i) + "_" + str(j)].append([y,x])
      
ans = 0
visited = [[False for i in range(W)] for j in range(H)]
willsearch = [[False for i in range(W)] for j in range(H)]
Q = deque()
#print(V)
def dfs(y,x):
  wc, bc = 0, 0
  Q.append([y,x])
  while len(Q) > 0:
    b,a = Q.pop()
    #print("pop;", b, a, Q)
    visited[b][a] = True
    if S[b][a] == '.':
      wc += 1
    else:
      bc += 1
    for q,p in V[str(b) + "_" + str(a)]:
      #print("yeah:", q,p)
      if visited[q][p] or willsearch[q][p]:
        continue
      Q.append([q,p])
      willsearch[q][p] = True
    #print(b,a,"|",Q)
  #print(y,x,wc,bc)
  return wc*bc

for i in range(H):
  for j in range(W):
    ans += dfs(i,j)
    
print(ans)
### BUGGY CODE ###

# クエリはまとめてしまえ
import sys
sys.setrecursionlimit(10**7)
n, q = map(int, input().split())
ki = [[] for i in range(n)]

def union(a, b):
  # aの子供
  ki[a].append(b)

for i in range(n-1):
  a, b = map(int, input().split())
  union(a-1, b-1)

table = {}
for _ in range(q):
  p, x = map(int, input().split())
  if p-1 not in table:
    table[p-1] = x
  else:
    table[p-1] += x
ans = [0 for _ in range(n)]


def f(k, v, b):
  if len(ki[k])>0:
    # 自分自身
    if b == False:
      ans[k] += v
    for x in ki[k]:
      ans[x] += v
    for x in ki[k]:
      # 再起するときのマーク
      f(x, v, True)
  else:
    if b == False:
      ans[k] += v
for k, v in table.items():
  f(k, v, False)

print(" ".join(list(map(str, ans))))

### FIXED CODE ###

# 木全体の根が決まっているのでふつうにbfsでいい気がするが...
# 毎回探索するんじゃなくて、各枝にポイントをつけておいて、探索するときに1回だけ渡して更新していく
# 考え方は累積和
# なんかafter_contestってテストケースでハネられるんだが。。。。。なんだこれ
# i<jのときiのほうが根に近い、というのを決め打ちしても通ってしまう防止らしい
# 回避するべく
# 両方のノードからエッジを貼り(graph[b].append(a))、
# 探索のときに訪問済みの場所は抜くことにした(if node not in used:)

n, q = map(int, input().split())
graph = [[] for _ in range(n)]
points = [0 for _ in range(n)]

for _ in range(n - 1):
    a, b = map(lambda x: int(x) - 1, input().split())
    graph[a].append(b)
    graph[b].append(a)

for _ in range(q):
    p, x = map(int, input().split())
    points[p - 1] += x

path = [0]
used = set()
used.add(0)
while len(path) > 0:
    cur_node = path.pop()
    cur_point = points[cur_node]
    for node in graph[cur_node]:
        if node not in used:
            used.add(node)
            points[node] += cur_point
            path.append(node)
print(" ".join(list(map(str, points))))
### BUGGY CODE ###

from collections import deque
import numpy as np
n,m,k=map(int,input().split())
link=[[] for _ in range(n)]
block=[[]  for _ in range(n)]
ans=[]
s=[]
for i in range(m):
    a,b=map(int,input().split())
    link[a-1].append(b-1)
    link[b-1].append(a-1)
for i in range(k):
  a,b=map(int,input().split())
  block[a-1].append(b-1)
  block[b-1].append(a-1)
for i in range(n):#スタートの選び方
    visited=[]
    q=deque([i])
    while len(q)>0:
        x=q.pop()
        visited.append(x)
        for j in link[x]:
            if j not in visited:
              if j not in q:
                q.append(j)
    ans.append(len(visited))
    s.append(visited)
res=[]
for i in range(n):
  l=1
  for j in s[i]:
    l+=link[i].count(j)
    l+=block[i].count(j)
  res.append(l)
print(*(np.array(ans)-np.array(res)))

### FIXED CODE ###

class UnionFind():
    def __init__(self,n):
      self.n=n
      self.root=[-1]*(n+1)
      self.rank=[0]*(n+1)
      
    def find(self,x):
      if self.root[x]<0:
        return x
      else:
        self.root[x]=self.find(self.root[x])
        return self.root[x]
    
    def unite(self,x,y):
      x=self.find(x)
      y=self.find(y)
      if x==y:
        return 0
      elif self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      else:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
          
    def Same(self,x,y):
      return self.find(x)==self.find(y)
    
    def size(self,x):
      return -self.root[self.find(x)]
import sys
input=sys.stdin.buffer.readline
n,m,k=map(int,input().split())
link=UnionFind(n)
f=[0]*n
block=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    link.unite(a,b)
    f[a]+=1
    f[b]+=1
for _ in range(k):
    a,b=map(int,input().split())
    block[a-1].append(b-1)
    block[b-1].append(a-1)
ans=[]
for i in range(n):
  ret=link.size(i)-f[i]-1
  for j in block[i]:
    if link.Same(i,j):
      ret-=1
  ans.append(ret)
print(*ans)
### BUGGY CODE ###

n,k=map(int,input().split())
s={n}
while True:
  n=abs(n-k)
  if(n in s):
    break
  else:
    s.add(n)
print(min(s))

### FIXED CODE ###

n,k=map(int,input().split())
n%=k
if(k==1):
  print(0)
  exit()
s={n}
while True:
  n=abs(n-k)
  if(n in s):
    break
  else:
    s.add(n)
print(min(s))
### BUGGY CODE ###

mod = 10 ** 9 + 7

S = input()

dp = [0] * 13

dp[0] = 1

l = len(S)

for i in S:
    nextdp = [0] * 13
    if i == "?":
        for k in range(10):
            for j in range(13):
                nextdp[((j * 10) + k) % 13] += dp[j]
                nextdp[((j * 10) + k) % 13] %= mod

    else:
        k = int(i)
        for j in range(13):
            nextdp[((j * 10) + k) % 13] += dp[j]
            nextdp[((j * 10) + k) % 13] %= mod

    dp = nextdp


print(dp[5])

### FIXED CODE ###

mod = 10 ** 9 + 7

S = input()

dp = [0] * 13

dp[0] = 1

l = len(S)

for i in S:
    nextdp = [0] * 13
    if i == "?":
        for k in range(10):
            for j in range(13):
                nextdp[((j * 10) + k) % 13] += dp[j]
                # nextdp[((j * 10) + k) % 13] %= mod

    else:
        k = int(i)
        for j in range(13):
            nextdp[((j * 10) + k) % 13] += dp[j]
            # nextdp[((j * 10) + k) % 13] %= mod

    dp = [nextdp[i] % mod for i in range(13)]

    # for i in range(13):
    #     dp[i] = nextdp[i] % mod

print(dp[5])
### BUGGY CODE ###

import itertools
import math

a = int(input())
cnt = 0
ans = []
l = list(range(1,int(math.sqrt(a))))

for x,y,z in itertools.product(l, repeat=3):
	ans.append(x*x+y*y+z*z+x*y+y*z+z*x)

for i in range(1,a+1):
    print(ans.count(i))

### FIXED CODE ###

import itertools
import math

a = int(input())
cnt = 0
ans = [0]*100000
l = list(range(1,int(math.sqrt(a))))

for x,y,z in itertools.product(l, repeat=3):
	ans[x*x+y*y+z*z+x*y+y*z+z*x]+=1

for i in range(1,a+1):
    print(ans[i])
### BUGGY CODE ###

# coding: utf-8
import re
import bisect
from datetime import datetime as dt
n, m = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
B = []
C = []
for i in range(m):
    b, c = map(int, input().split())
    for i in range(b):
        if A[i] < c:
            A[i] = c
        else:
            break
    A.sort()
print(sum(A))


### FIXED CODE ###

n,m=map(int,input().split())
a = list(map(int,input().split()))
bc=[list(map(int,input().split())) for i in [0]*m]
a.sort()
bc.sort(key=lambda x: x[1], reverse=True)  
i=0
for b,c in bc:
    for j in range(i,min(n,i+b)):
        if a[j] < c:
            a[j] = c
            i+=1
        else:
            break
print(sum(a))
### BUGGY CODE ###

n = int(input())
x = list(map(int,input().split()))
y = x.copy()
y.sort()
z = set(x)
t1 = y[n//2-1]
t2 = y[n//2]
idx = dict([])
for i in z:
    idx[i] = y.index(i)
for i in x:
    t = idx[i]
    if t<n//2:
        print(t2)
    else:
        print(t1)

### FIXED CODE ###

n = int(input())
x = list(map(int,input().split()))
y = x.copy()
y.sort()
z = set(x)
t1 = y[n//2-1]
t2 = y[n//2]
idx = dict([])
idx[y[0]] = 0
l = y[0]
cnt = 0
for i in y:
    if i == l:
        cnt += 1
        continue
    else:
        idx[i] = cnt
        l = i
        cnt += 1

for i in x:
    t = idx[i]
    if t<n//2:
        print(t2)
    else:
        print(t1)
### BUGGY CODE ###

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

N, K = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))


ans = -INF
for i in range(N):
    nx = i
    total = 0
    L = [] 
    while True:
        nx = P[nx]
        total += C[nx]
        L.append(C[nx])
        if nx == i:
            break
    l = len(L)
    now = 0
    for j in range(l):
        if j + 1 > K:
            break
        now += L[j]
        ans = max(ans, now)
    if total > 0:
        now = total * (K // l)
        ans = max(ans, now)
        r = K % l
        for j in range(r):
            now += L[j]
            ans = max(ans, now)
print(ans)




### FIXED CODE ###

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

N, K = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))


ans = -INF
for i in range(N):
    nx = i
    total = 0
    L = [] 
    while True:
        nx = P[nx]
        total += C[nx]
        L.append(C[nx])
        if nx == i:
            break
    l = len(L)
    tmp = 0
    for j in range(l):
        if j + 1 > K:
            break
        tmp += L[j]
        now = tmp
        if total > 0:
            e = (K - j - 1) // l
            now += total * e
        ans = max(ans, now)
    # if total > 0:
    #     now = total * (K // l)
    #     ans = max(ans, now)
    #     r = K % l
    #     for j in range(r):
    #         now += L[j]
    #         ans = max(ans, now)
print(ans)
### BUGGY CODE ###


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

from collections import defaultdict

N, M = map(int, input().split())
P = [0] * M
Y = [0] * M
dd = defaultdict(list)

for i in range(M):
    p, y = map(int, input().split())
    P[i] = p
    Y[i] = y

    dd[p].append(y)

for k, v in dd.items():
    v.sort()
    dd[k] = v

#print(dd)

for i in range(M):
    p = P[i]
    y = Y[i]

    print('{0:06d}'.format(p), end='')
    x = dd[p].index(y) +1
    print('{0:06d}'.format(x))

### FIXED CODE ###


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

N, M = map(int, input().split())
src = [tuple(map(int, input().split())) for _ in range(M)]
#print(src)

# 1-index なので+1
X = [ [] for _ in range(N+1) ]

for i, (p, y) in enumerate(src):
    X[p].append((y, i))
for c in X:
    c.sort()

#print(X)

ans = [None] * M
for p in range(len(X)):
    # 0([])の場合は、通らない
    for i,(_,j) in enumerate(X[p]):
        s = str(p).zfill(6) + str(i+1).zfill(6)
        ans[j] = s

print(*ans, sep='\n')
### BUGGY CODE ###

H, W = map(int, input("").split(" "))

grid = []
blacks = set()
for i in range(H):
    row = list(input(""))
    grid.append(row)

    for idx, r in enumerate(row):
        if r == "#":
            blacks.add((i, idx))

c = 0
while len(blacks) > 0:
    c += 1

    new_blacks = set()
    while len(blacks) > 0:
        b = blacks.pop()

        top = b[0]-1
        bottom = b[0]+1
        left = b[1]-1
        right = b[1]+1

        if top >= 0:
            if grid[top][b[1]] == ".":
                grid[top][b[1]] = "#"
                new_blacks.add((top, b[1]))
        if bottom < H:
            if grid[bottom][b[1]] == ".":
                grid[bottom][b[1]] = "#"
                new_blacks.add((bottom, b[1]))
        if left >= 0:
            if grid[b[0]][left] == ".":
                grid[b[0]][left] = "#"
                new_blacks.add((b[0], left))
        if right < W:
            if grid[b[0]][right] == ".":
                grid[b[0]][right] = "#"
                new_blacks.add((b[0], right))

    blacks = new_blacks


print(c-1)


### FIXED CODE ###

H, W = map(int, input("").split(" "))

grid = []
blacks = []
for i in range(H):
    row = list(input(""))
    grid.append(row)

    for idx, r in enumerate(row):
        if r == "#":
            blacks.append((i, idx))

c = 0
while len(blacks) > 0:
    c += 1

    new_blacks = []
    for b in blacks:
        top = b[0] - 1
        bottom = b[0] + 1
        left = b[1] - 1
        right = b[1] + 1

        if top >= 0:
            if grid[top][b[1]] == ".":
                grid[top][b[1]] = "#"
                new_blacks.append((top, b[1]))
        if bottom < H:
            if grid[bottom][b[1]] == ".":
                grid[bottom][b[1]] = "#"
                new_blacks.append((bottom, b[1]))
        if left >= 0:
            if grid[b[0]][left] == ".":
                grid[b[0]][left] = "#"
                new_blacks.append((b[0], left))
        if right < W:
            if grid[b[0]][right] == ".":
                grid[b[0]][right] = "#"
                new_blacks.append((b[0], right))

    blacks = new_blacks

print(c - 1)