Harryxun/stf_run huggingface dataset:
N = input()
num_list = list(map(int, input().split(" ")))

def devision(num_list, count):
    new_num_list = []
    for num in num_list:
        if num%2 ==0:
            new_num_list.append(num//2)
        else:
            print(count)
            return
    count += 1
    return devision(new_num_list, count)

devision(num_list, 0)            

### FIXED CODE ###

s = input()
print(s.count('1'))
import sys
from functools import lru_cache
def input(): return sys.stdin.readline().strip()


def main():
    N, Z, W = map(int, input().split())
    A = list(map(int, input().split()))
    """
    O(N^2)dpでも行けるそうです。以下写経：
    https://atcoder.jp/contests/abc078/submissions/14886969
    dpテーブルが訳分からなくなったら@lru_cache使うのが楽。
    """
    @lru_cache(maxsize=None)
    def dfs(turn, top, x, y): # turn: 0 => x, 1 => y
        if top == N: return abs(x - y)
        if turn == 1:
            """
            yのターンは、top以降を取ってなるべくスコアが低くなるようなiを選ぶ
            """
            ret = 10**18
            for i in range(top, N): ret = min(ret, dfs(0, i + 1, x, A[i]))
            return ret
        else:
            """
            xのターンは、top以降を取ってなるべくスコアが高くなるようなiを選ぶ
            """
            ret = 0
            for i in range(top, N): ret = max(ret, dfs(1, i + 1, A[i], y))
            return ret
    
    print(dfs(0, 0, Z, W))

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()


def main():
    N, z, w = map(int, input().split())
    A = list(map(int, input().split()))
    """
    dpかと思ってずっとウンウン唸ってたのに、解説見て唖然。。。
    """
    if N == 1: print(abs(A[0] - w))
    else: print(max(abs(A[-1] - w), abs(A[-1] - A[-2])))


if __name__ == "__main__":
    main()
h,w=map(int,input().split())
ans=[]
import sys
def s(a,b):
    if a%3==1:
        s=a*b
        x=(a//3)*b
        y=((a-(a//3))//2)*b
        z=s-x-y

        e=(a-(a//3))*(b//2)
        d=s-x-e
        ma=max(x,y,z)
        mi=min(x,y,z)
        mc=max(x,e,d)
        mn=min(x,e,d)
        return(min((ma-mi),(mc-mn)))
    elif a%3==2:
        s=a*b
        x=((a//3)+1)*b
        y=((a-(a//3)-1)//2)*b
        z=s-x-y
        e=(a-(a//3)-1)*(b//2)
        d=s-x-e
        ma=max(x,y,z)
        mi=min(x,y,z)
        mc=max(x,e,d)
        mn=min(x,e,d)
        return(min((ma-mi),(mc-mn)))

if h<w:
    h,w=w,h
if (h%3==0)or(w%3==0):
    print(0)
else:
    k=s(h,w)
    ans.append(k)
    r=s(w,h)
    ans.append(r)
    
# print(ans)
print(min(ans))
    


### FIXED CODE ###

h,w=map(int,input().split())
ans=[]
import sys
def s(a,b):
    for i in range(a):
        s=a*b
        x=i*b
        y=((a-i)//2)*b
        z=s-x-y

        d=(a-i)*(b//2)
        e=s-x-d
        ma=max(x,y,z)
        mi=min(x,y,z)
        mc=max(x,e,d)
        mn=min(x,e,d)
        res=min((ma-mi),(mc-mn))
        ans.append(res)
    return min(ans)
        
f=s(h,w)
g=s(w,h)
print(min(f,g))
    
# print(ans)
# print(min(ans))
import sys
from collections import *
import heapq
import math
from math import gcd
import bisect
import copy
from itertools import permutations,accumulate,combinations,product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,c=map(int,input().split())
stc=[list(map(int,input().split())) for i in range(n)]
stc.sort()
lst=[0]*c
for i in range(n):
    for j in range(c):
        if lst[j]==0:
            lst[j]=stc[i]
            break
        else:
            if lst[j][2]==stc[i][2]:
                lst[j]=stc[i]
                break
            elif lst[j][1]+1<stc[i][1]:
                lst[j]=stc[i]
                break

ans=0
for i in range(c):
    if lst[i]!=0:
        ans+=1
print(ans)

### FIXED CODE ###

import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n,c=map(int,input().split())
stc=[list(map(int,input().split())) for i in range(n)]
stc.sort(key=lambda x: x[2])
# print(stc)
lst=[[0]*(10**5+5) for i in range(c)]
for i in range(len(stc)):
    s,t,c=stc[i]
    for j in range(s-1,t):
        lst[c-1][j]+=1
anslst=[0]*(10**5+5)
for i in range(c):
    for j in range(10**5+5):
        if lst[i][j]!=0:
            anslst[j]+=1
print(max(anslst))
import math

n, q = map(int, input().split(" "))
abL = [list(map(int, input().split(" "))) for _ in range(n - 1)]
pxL = [list(map(int, input().split(" "))) for _ in range(q)]

to = [[] for _ in range(200005)]
ans = [0 for _ in range(n + 1)]


def dfs(v, p=-1):
    for u in to[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v)


for a, b in abL:
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)

for p, x in pxL:
    p -= 1
    ans[p] += x

dfs(0)

for a in ans[:n]:
    print(a)

### FIXED CODE ###

import math
import sys

sys.setrecursionlimit(200005)

n, q = map(int, input().split(" "))
abL = [list(map(int, input().split(" "))) for _ in range(n - 1)]
pxL = [list(map(int, input().split(" "))) for _ in range(q)]

to = [[] for _ in range(200005)]
ans = [0 for _ in range(n + 1)]


def dfs(v, p=-1):
    for u in to[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v)


for a, b in abL:
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)

for p, x in pxL:
    p -= 1
    ans[p] += x

dfs(0)

for a in ans[:n]:
    print(a)
import math
print(int(input()*2*math.pi)

### FIXED CODE ###

import math
print(int(input())*2*math.pi)
#以下は上位者のコピー
n, k = map(int, input().split())
mod = 10 ** 9 + 7

from collections import deque

a = list(map(int, input().split()))
a.sort()
minus, zero, plus = 0, 0, 0
for i in range(n):
    if a[i] < 0:
        minus += 1
    elif a[i] == 0:
        zero += 1
    else:
        plus += 1

que = deque(a)

plus_flg = False
tmp = plus - k
if tmp >= 0:
    plus_flg = True
elif tmp*-2 > minus  :
    plus_flg = True

# plus可能
if plus_flg:
    ans = 1
    cnt = 0

    while cnt < k:
        if k - cnt >= 2:
            cnt += 2
            if que[0] * que[1] >= que[-1] * que[-2]:
                ans *= que.popleft()
                ans *= que.popleft()
                ans %= mod
            else:
                ans *= que.pop()
                ans *= que.pop()
                ans %= mod
        else:
            ans *= que.pop()
            ans %= mod
            cnt += 1

    print(ans)



# zero
elif zero > 0:
    print(0)

# minus
else:
    a = [abs(a[i]) for i in range(n)]
    a.sort()
    ans = 1
    for i in range(k):
        ans *= a[i]
        ans %= mod
    ans = -ans % mod
    print(ans)


### FIXED CODE ###

n = int(input())
lis = sorted(list(map(int, input().split())),reverse=True)
idx = 0
res = lis[0]
while True:
    if idx >= n-2:
        break
    res += lis[1+idx//2]
    idx += 1
print(res)
a=int(input())
print(8 if 400 <= a <= 599)
print(7 if 600 <= a <= 799)
print(6 if 800 <= a <= 999)
print(5 if 1000 <= a <= 1199)
print(4 if 1200 <= a <= 1399)
print(3 if 1400 <= a <= 1599)
print(2 if 1600 <= a <= 1799)
print(1 if 1800 <= a <= 1999)

### FIXED CODE ###

a=int(input())
if 400<=a<=599:
  print(8) 
if 600<=a<=799:
  print(7)
if 800<=a<=999:
  print(6)
if 1000<=a<=1199:
  print(5)
if 1200<=a<=1399:
  print(4)
if 1400<=a<=1599:
  print(3)
if 1600<=a<=1799:
  print(2)
if 1800<=a<=1999:
  print(1)
import sys

#+++++
		
def main():
	n, k = map(int, input().split())
	aal = list(map(int, input().split()))
	
	sss = [0]*(n+1)
	si=0
	for i, a in enumerate(aal):
		si+=a-1
		sss[i+1]=si%k
	
	count=0
	mkl=[0]*k
	for j in range(n+1):
		sj=sss[j]
		if j-k >= 0:
			#pa((j-k, sss[j-k]))
			mkl[sss[j-k]]-=1
		#pa((mkl,sj))
		count += mkl[sj]
		mkl[sj] += 1
			
	print(count)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)


### FIXED CODE ###

import sys
from collections import defaultdict

#+++++
		
def main():
	n, k = map(int, input().split())
	aal = list(map(int, input().split()))
	
	sss = [0]*(n+1)
	si=0
	for i, a in enumerate(aal):
		si+=a-1
		sss[i+1]=si%k
	
	count=0
	mkl_dict=defaultdict(lambda :0)
	for j in range(n+1):
		sj=sss[j]
		if j-k >= 0:
			mkl_dict[sss[j-k]]-=1
		count += mkl_dict[sj]
		mkl_dict[sj] += 1
			
	print(count)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
n,m = (int(input()).split())
print((n-1)*(m-2))

### FIXED CODE ###

n,m = map(int,input().split())
print((n-1)*(m-1))
a=sorted(map(int,raw_input().split()))
ans=0
for i in xrange(N):
  x-=a[i]
  if x<0 or i==N-1 and x>0:
    break
  else:
    ans+=1
print ans


### FIXED CODE ###

N,x=map(int,raw_input().split())
a=sorted(map(int,raw_input().split()))
ans=0
for i in xrange(N):
  x-=a[i]
  if x<0 or i==N-1 and x>0:
    break
  else:
    ans+=1
print ans
n,m=map(int,input().split())
if n==1 and m==1:
    print(1)
elif n==1 and m!=1:
    print(m-2)
else:
    print((n-2)(m-2))


### FIXED CODE ###

n,m=map(int,input().split())
print(abs((n-2)*(m-2)))
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

n = I()
#edge[i][j]には頂点iと頂点jをつなぐ辺の色を格納する
edge = [[0]*(n+1) for _ in range(n+1)]
#graph[i]には頂点iと繋がっている頂点を格納する
graph = [[] for _ in range(n+1)]
prev_col = [0]*(n+1)
k = 0
a_b = []
for i in range(n-1):
    a,b = MI()
    a_b.append([a,b])
    graph[a].append(b)
    graph[b].append(a)
#check[i] == -1ならば未探索
check = [-1]*(n+1)
check[0] = 0
check[1] = 0
d = deque()
d.append(1)
while d:
    v = d.popleft()
    check[v] = 1
    cnt = 0
    for i in graph[v]:
      if check[i] != -1:
        continue
      cnt = cnt+1
      if prev_col[v] == cnt:
        cnt = cnt + 1
      edge[i][v] = cnt
      edge[v][i] = cnt
      prev_col[i] = cnt
      d.append(i)
      check[i] = 0
      k = max(k,cnt)
print(k)
for i in range(n-1):
    color = edge[a_b[i][0]][a_b[i][1]]
    print(color)


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
import numpy as np
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

n = I()

#graph[i]には頂点iと繋がっている頂点を格納する
graph = [[] for _ in range(n+1)]
prev_col = [0]*(n+1)
a_b = []
k=0
for i in range(n-1):
    a,b = MI()
    a_b.append(str(a)+" "+str(b))
    graph[a].append(b)
    graph[b].append(a)
#check[i] == -1ならば未探索
check = [-1]*(n+1)
check[0] = 0
check[1] = 0
for i in range(n+1):
    k = max(len(graph[i]),k)
d = deque()
d.append(1)
ans = dict()
while d:
    v = d.popleft()
    check[v] = 1
    cnt = 0
    for i in graph[v]:
      if check[i] != -1:
        continue
      cnt = cnt+1
      if prev_col[v] == cnt:
        cnt = cnt + 1
      prev_col[i] = cnt
      ans[str(min(i,v))+" "+str(max(i,v))]=cnt
      d.append(i)
print(k)
for key in a_b:
    print(ans[key])
n = int(input())

for _ in range(n):
  m, f, r = map(int, input().split())
  s = m+f

if s >= 80:
    print("A")
elif s >= 65 and s < 80:
    print("B")
elif (s >= 50 and s < 65) or f >= 50:
    print("C")
elif s >= 30 and s < 50:
    print("D")
else:
    print("F")


if m == f == r== -1:
    print("F")


### FIXED CODE ###

while True:
    m, f, r = map(int, input().split())
    if m == f == r== -1:
        break
    s = m + f
    if m == -1 or f == -1:
        print("F")
    elif s >= 80:
        print("A")
    elif s >= 65:
        print("B")
    elif s >= 50:
        print("C")
    elif s >= 30:
        if r >= 50:
            print("C")
        else:
            print("D")
    else:
        print("F")
n = int(input())
a = list(map(int, input().split()))
b = []
for i in range(n):
  for j in range(i+1, n):
    b.append(a[i] % (10 ** 9 + 7) * (a[j] % (10 ** 9 + 7))
print(sum(b) % (10 ** 9 + 7))

### FIXED CODE ###

s, t = [input() for i in range(2)]
c = []
for i in range(len(s) - len(t) + 1):
  d = len(t)
  for a, b in zip(s[i:], t):
    if a == b:
      d -= 1
  c.append(d)
print(min(c))
def main():
  N=int(input())
  a=list(map(int,input().split()))
  p=max(a)
  m=len(bin(p))-2
  for i in range(N):
    b=len(bin(a[i]))-2
    ans=0
    for j in range(b):
      if a[i]>>j&1==1:
        if j==m-1 or j==0:
          ans+=pow(2,j)
      else:
        if j==m-1 or j==0:
          continue
        ans+=pow(2,j)
    print(ans,end=' ')
if __name__=='__main__':

### FIXED CODE ###

def main():
  N=int(input())
  a=list(map(int,input().split()))
  ans=0
  for i in range(N):
    ans=ans^a[i]
  for i in range(N):
    print(ans^a[i],end=' ')
if __name__=='__main__':
  main()
N=list[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
K=int(input())
print(N[K-1])

### FIXED CODE ###

N=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
K=int(input())
print(N[K-1])
n = input()
R = []

for i in range(1,n):
    R.append(input())
 
max = R[1] - R[0]
min = R[0]
 
for i in range(2,n):
    if R[i]-min>max:
        max = R[i] - min
    if R[i]<min:
        min = R[i]
 
print 1

### FIXED CODE ###

n = input()

R = [input() for i in range(n)]
  
max = R[1] - R[0]
min = R[0]
  
for i in range(1,n):
    if R[i] - min > max:
        max = R[i] - min
    if R[i] < min:
        min = R[i]
  
print max
N = int(input())
p = list(map(lambda x: int(x) - 1, input().split()))
r = {}
for i in range(N):
    r[p[i]] = i

A = [30000 * i for i in range(1, N + 1)]
B = [30000 * (N - i) + r[i] for i in range(1, N + 1)]
print(A)
print(B)

### FIXED CODE ###

N = int(input())
p = list(map(lambda x: int(x) - 1, input().split()))
r = {}
for i in range(N):
    r[p[i]] = i + 1

A = [30000 * i for i in range(1, N + 1)]
B = [30000 * (N - i) + r[i - 1] for i in range(1, N + 1)]
print(*A)
print(*B)
n,m = map(int,input().split())
A = list(map(int, input().split()))
x = sum(A)/(4*m)
count = 0
for a in A:
    if a >= x:
        count += 1
if count >= m:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

A = list(map(int, input().split()))
print(A[2], A[0], A[1])
n = int(input())
s = str(input())
t = str(input())

result = ""
for i in range(n):
  result += s[i]
  result += t[i]
print(result)

### FIXED CODE ###

n = int(input())
rawString = str(input())
splitString = rawString.split()
s = splitString[0]
t = splitString[1]

result = ""
for i in range(n):
  result += s[i]
  result += t[i]
print(result)
n,k = map(int,input().split())
a = list(map(int,input().split()))
l = [1]
for i in range(n):  
    l.append(a[l[i]])
    
p = l.index(l[-1])
if k<=n:
  print(l[k])
  exit()
  
x = (k-n+1)%(n-p)
if x==0:
  print(l[n-1])
else:
  print(l[x+p-1])


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
l = [1]

for i in range(n):
  l.append(a[l[i]-1])
p = l.index(l[n])
#print(p,l[n])
if k<=n:
  print(l[k])
else:
  x = (k-n+1)%(n-p)
  if x ==0:
    x += (n-p)
    print(l[x-1])
  else:
    print(l[x+p-1])
def main():
    n = map(int, input().split())
    for i in range(1, 10, 1):
        if 1 <= n//i <= 9:
            print('Yes')
        else:
            print('No')
main()

### FIXED CODE ###

import sys

def main():
    n = int(input())
    for i in range(1, 10, 1):
        if 1 <= n//i <= 9 and (n/i).is_integer():
            print('Yes')
            sys.exit()
    print('No')
    
main()
a,b,c = map(int, input().split())
K = int(input())

cnt = 0
while b <= a:
    cnt += 1
    b *= 2
while c <= b:
    cnt += 1
    c *= 2
if cnt <= K:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

x = int(input())
a = (x - 400)//200
print(8-a)
a, b, c = map(int, input().split())
print(a + b if op == + else a - b)

### FIXED CODE ###

a, op, b = map(str, input().split())
a = int(a)
b = int(b)
print(a + b if op == "+" else a - b)
s=list(input())
t=list(input())
dp=[[0]*(30) for j in range(30)]
ans=[]
memo=-1
for i in range(len(s)):
    for j in range(len(t)):
        if s[i]==t[j]:
             dp[i+1][j+1] = dp[i][j]+1
             if memo < i:
                 ans.append(t[j])
                 memo = i

        else:
            dp[i+1][j+1] =max(dp[i][j+1],dp[i+1][j])

#print(dp[len(s)][len(t)])
answer=[]
i,j=len(s),len(t)
d=dp[i-1][j-1]
while i!=0 and j!=0:
    if dp[i-1][j-1]!=dp[i][j]:
        answer.append(s[i-1])
        i-=1
        j-=1
    elif dp[i-1][j]==dp[i][j]:
        i-=1
    elif dp[i][j-1]==dp[i][j]:
        j-=1
print("".join(reversed(answer)))

### FIXED CODE ###

s=list(input())
t=list(input())
dp=[[0]*(3030) for j in range(3030)]
ans=[]
memo=-1
for i in range(len(s)):
    for j in range(len(t)):
        if s[i]==t[j]:
             dp[i+1][j+1] = dp[i][j]+1
             if memo < i:
                 ans.append(t[j])
                 memo = i

        else:
            dp[i+1][j+1] =max(dp[i][j+1],dp[i+1][j])

#print(dp[len(s)][len(t)])
answer=[]
i,j=len(s),len(t)
d=dp[i-1][j-1]
while i>=0 and j>=0:

    if dp[i-1][j]==dp[i][j]:
        i-=1
    elif dp[i][j-1]==dp[i][j]:
        j-=1
    else:
        answer.append(s[i - 1])
        i -= 1
        j -= 1
print("".join(reversed(answer)))
x = int(input())
try_n = x - 1
b_flg = True
roop_c = 0
while b_flg:
    try_n += 1
    for n in range(2, try_n):
        roop_c += 1
        if try_b == 2: # 2の場合は特別
            b_flg =False
            break
        if try_n % n == 0: # 素数でないことが確定した場合
            break
        else:
            if roop_c == try_n - 2:
                b_flg = False
print(try_n)

### FIXED CODE ###

x = int(input())
b_flg = True
try_n = x - 1
roop_c = 0
if x == 2:
    print(x)
else:
    while b_flg:
        try_n += 1
        for n in range(2, try_n):
            roop_c += 1
            if try_n % n == 0: # 素数でないことが確定した場合
                break
            else:
                if roop_c == try_n - 2:
                    b_flg = False
    print(try_n)
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math

N,M = map(int,input().split())
S = input()
N = len(S)-1

if "1"*M in S:
  print(-1)
  exit()  

S = list(map(int,S))

max_n = [0]
mask = (1<<M) -1
b = 0
for i in range(N+1):
  b = ((b<<1) + (1- S[i])) & mask
  max_n.append(math.floor(math.log(b)/math.log(2))+1)


now = N
deme = []
while now != 0:
  x = max_n[now]
  now = now-x
  deme.append(x)
print(*deme[::-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline

import math
import bisect

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

if "1"*M in S:
  print(-1)
  exit()  

S = [int(S[i]) for i in range(N+1)]

L = [(1<<i) -1 for i in range(1,M+1)]

max_n = [0]
mask = (1<<M) -1
b = 0
for i in range(N):
  b = ((b<<1) + (1- S[i])) & mask
  max_n.append(bisect.bisect_left(L,b)+1)

now = N
deme = []
while now != 0:
  x = max_n[now]
  now -= x
  deme.append(x)
print(*deme[::-1])
n, m = map(int, input().split())
pys = [[] for _ in range(n + 1)]

ans = [None for _ in range(m)]

for i in range(m):
    p, y = map(int, input().split())
    lst = [y, i]
    pys[p].append(lst)

for p in range(1, n + 1):
    t = sorted(pys[p], key=lambda x: x[0])
    for j, [y, i] in enumerate(t, 1):
        ans[i] = f'{p:06}{j:06}'

print('\n'.join(ans))

'''
zero padding: 
f'{i:03}'
002etc
'''

### FIXED CODE ###

from bisect import bisect_left

n, m = map(int, input().split())
qs = [list(map(int, input().split())) for _ in range(m)]
pys = [[] for _ in range(n)]
for q in qs:
    p, y = q
    p -= 1
    pys[p].append(y)

for i in range(n):
    pys[i] = sorted(pys[i])

for q in qs:
    p, y = q
    p -= 1
    number = bisect_left(pys[p], y) + 1

    print(str(p + 1).zfill(6) + str(number).zfill(6))
N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
a.sort()
MOD = 10**9 + 7

dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1 if a[0]!=1 else 0

a = [i for i in range(2, N+1) if i not in a]
for i in a:
    dp[i] = (dp[i-1] + dp[i-2]) % MOD
print(dp[N] % MOD)

### FIXED CODE ###

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
MOD = 10**9 + 7
 
dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1 if 1 not in a else 0
 
a = set(list(range(2,N+1))) - set(a)
for i in a:
    dp[i] = (dp[i-1] + dp[i-2]) % MOD
print(dp[N] % MOD)
while True:
        a,op,b=map(str,input().split())
        a=int(a)
        b=int(b)
           
        if op=("+"):
                print(a+b)
        elif op=("-"):
                print(a-b)
        elif op=("*"):
                print(a*b)
        elif op=("/"):
                print(a/b)
        elif op=("?"):
                break



### FIXED CODE ###



while 1:
     s=input()
     if '?' in s: break
     print(int(eval(s)))
K, X = map(int, input().split())

if (500 * x) >= K:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

K, X = map(int, input().split())

if (500 * K) >= X:
    print('Yes')
else:
    print('No')
N = int(input())
names = set()
citydict = dict()
for i in range(N):
    S,P = input().split()
    names.add(S)
    if S[i] in citydict:
        citydict[S].append((int(P),i))
    else:
        citydict[S] = [(int(P),i)]

for name in sorted(names):
    for point in sorted(citydict[name],reverse = True):
        print(point[1] + 1)

### FIXED CODE ###

N = int(input())
names = set()
citydict = dict()
for i in range(N):
    S,P = input().split()
    names.add(S)
    if S in citydict:
        citydict[S].append((int(P),i))
    else:
        citydict[S] = [(int(P),i)]

for name in sorted(names):
    for point in sorted(citydict[name],reverse = True):
        print(point[1] + 1)
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))

li_f = list.sort(F)
li_a = list.sort(A, reverse=True)

for i in range(K + 1):
  combined1 = [x * y for (x, y) in zip(li1, li2)]
  n_max = combined1.index(max(combined1))
  li_a[n_max] = li_a[n_max] - (i - (i - 1))

print(max(combined1))

### FIXED CODE ###

import numpy as np

import sys
input = sys.stdin.buffer.readline

N, K = map(int, input().split())
A = np.array(input().split(), np.int64)
F = np.array(input().split(), np.int64)

A.sort()
F.sort()

F= F[::-1]

left = -1
right = (A * F).sum()
while left + 1 < right:
  middle = (left + right) // 2
  right_arr = np.maximum(0, A - middle // F).sum() <= K
  if right_arr:
    right = middle
  else:
    left = middle
print(right)
N, M = map(int, input().split())
S = input()
T = input()

# ユークリッドの互除法
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

length = N * M // gcd(N, M)
ans1 = ['']*length
ans2 = ['']*length

for i in range(N):
    index = i * length // N + 1
    ans1[index-1] = S[i]

for i in range(M):
    index = i * length // M + 1
    ans2[index-1] = T[i]

for s, t in zip(ans1, ans2):
    if s != '' and t != '':
        if s != t:
            print(-1)
            exit()

print(length)


### FIXED CODE ###

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

# ユークリッドの互除法
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

length = N * M // gcd(N, M)

if S[0::length//M] == T[0::length//N]:
    print(length)
else:
    print(-1)