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

import sys
from bisect import bisect_left


class RangeUpdateTree:
    def __init__(self, n, initial=-1, sentinel=-2):
        n2 = 1 << n.bit_length()
        self.n = n2
        self.offset = n2
        self.data = [initial] * (n2 << 1)
        self.sentinel = sentinel

    def update(self, a, b, x):
        stack = [(1, 0, self.n)]
        while stack:
            i, l, r = stack.pop()
            if a <= l and r <= b:
                self.data[i] = x
                continue
            y = self.data[i]
            j = i << 1
            if y != self.sentinel:
                self.data[i] = self.sentinel
                self.data[j] = self.data[j + 1] = y
            m = (l + r) // 2
            if a < m:
                stack.append((j, l, m))
            if m < b:
                stack.append((j + 1, m, r))

    def aggregate(self):
        stack = [1]
        ans = 0
        while stack:
            i = stack.pop()
            if self.data[i] != self.sentinel:
                ans += self.data[i] * (self.n >> i.bit_length() - 1)
                continue
            i <<= 1
            stack.append(i)
            stack.append(i + 1)
        return ans

    def propagate(self):
        stack = [(1, 0, self.n)]
        while stack:
            i, l, r = stack.pop()
            if self.data[i] != self.sentinel:
                self.data[l + self.offset:r + self.offset] = [self.data[i]] * (r - l)
                continue
            i <<= 1
            m = (l + r) // 2
            stack.append((i, l, m))
            stack.append((i + 1, m, r))

    def debug_print(self):
        i = 1
        while i <= self.offset:
            print(self.data[i:2 * i])
            i <<= 1


n, q = list(map(int, input().split()))
lines = sys.stdin.readlines()
kkk = []
for line in lines[:n]:
    s, t, x = list(map(int, line.split()))
    kkk.append((x, s, t))
kkk.sort(reverse=True)
ddd = [int(line) for line in lines[n:]]
rut = RangeUpdateTree(q)
for x, s, t in kkk:
    ss = bisect_left(ddd, s - x)
    tt = bisect_left(ddd, t - x)
    if ss == tt:
        continue
    # print(x, s, t, s - x, t - x, ss, tt)
    rut.update(ss, tt, x)
rut.propagate()
data = rut.data[rut.offset:]
# rut.debug_print()
print('\n'.join(map(str, data[:q])))


### FIXED CODE ###

import sys
from bisect import bisect_left

n, q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:n]:
    s, t, x = map(int, line.split())
    kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[n:]))

ans = [-1] * q
skip = [-1] * q
for x, s, t in kkk:
    ss = bisect_left(ddd, s - x)
    tt = bisect_left(ddd, t - x)
    while ss < tt:
        if skip[ss] == -1:
            ans[ss] = x
            skip[ss] = tt
            ss += 1
        else:
            ss = skip[ss]
print('\n'.join(map(str, ans)))
### BUGGY CODE ###

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

ans = 1
for a in A:
    ans *= a

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

### FIXED CODE ###

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

A = sorted(A)
ans = 1
for a in A:
    ans *= a
    if a == 0:
        ans = 0
        break
    if ans > 10**18:
        ans = -1
        break

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

# D - Blue and Red Balls

# 青いボールを並べる→赤いボールを青いボールの間に挿入する→残りの赤いボールを両端に置く

from math import factorial

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

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

# 連続した同色のボールの数nと、それらを何分割するか示すaを与えると、分割のパターン数を返す関数
def separate_balls(n,a):
    return combinations(n-1, a-1)

ans_list = []
for i in range(1,K+1):
    if N-K < i-1: # 赤いボール不足でi分割不可
        ans_list.append(0)
    elif i == 1:
        ans_list.append(N-K+1)
    else:
        tmp_blue = separate_balls(K, i) # K個の青いボールをi分割するパターン数
        tmp_red = 0
        for j in range(i-1, N-K+1): # 青いボールの分割に使う赤いボールの個数
            tmp_red_inner = separate_balls(j, i-1)  # j個の赤いボールをi-1分割して青いボールの隙間に入れるパターン数
            tmp_red_side = N-K-j+1 # N-K-j個の赤いボールを両端に置くパターン数
            tmp_red += tmp_red_inner * tmp_red_side
        ans_list.append((tmp_blue * tmp_red) % MOD)  # 青いボールの置き方*赤いボールの置き方

for x in ans_list:
    print(x)


### FIXED CODE ###

# D - Blue and Red Balls

# 青いボールを並べる→赤いボールを青いボールの間に挿入する→残りの赤いボールを両端に置く

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

# nCkを漸化式で求め、メモしておく
combinations_table = [[0]*(N+1) for _ in range(N+1)]
for idx in range(N+1):
    combinations_table[0][idx] = 1
    combinations_table[idx][0] = 1
    combinations_table[idx][1] = idx
for n in range(2, N+1):
    for k in range(2, n+1):
        combinations_table[n][k] = combinations_table[n-1][k-1] + combinations_table[n-1][k]

# 連続した同色のボールの数nと、それらを何分割するか示すaを与えると、分割のパターン数を返す関数
def separate_balls(n,a):
    return combinations_table[n-1][a-1]

ans_list = []
for n_separate in range(1,K+1):
    if N-K < n_separate-1: # 赤いボール不足でi分割不可
        ans_list.append(0)
    elif n_separate == 1:
        ans_list.append(N-K+1)
    else:
        tmp_blue = separate_balls(K, n_separate) % MOD  # K個の青いボールをi分割するパターン数
        tmp_red = 0
        for n_red_ball in range(n_separate-1, N-K+1): # 青いボールの分割に使う赤いボールの個数
            tmp_red_inner = separate_balls(n_red_ball, n_separate-1)  # j個の赤いボールをi-1分割して青いボールの隙間に入れるパターン数
            tmp_red_side = N-K-n_red_ball+1 # N-K-j個の赤いボールを両端に置くパターン数
            tmp_red += (tmp_red_inner * tmp_red_side) % MOD
        ans_list.append((tmp_blue * tmp_red) % MOD)  # 青いボールの置き方*赤いボールの置き方

for x in ans_list:
    print(x)
### BUGGY CODE ###

N = int(input())
Alst = list(map(int, input().split()))
ans = 0
l = len(Alst)
for i in range(l):
    for j in range(i+1, l):
        ans = (ans + Alst[i]*Alst[j])%(10**9 +7)

print(ans)

### FIXED CODE ###

N = int(input())
Alst = list(map(int, input().split()))
l = len(Alst)
Blst = [0]*l
k = 0
ans = 0
for i in range(l-1, 0, -1):
    k = (k + Alst[i])%(10**9 + 7)
    Blst[i] = k

for j in range(l-1):
    ans = (ans + Alst[j] * Blst[j+1])%(10**9 + 7)

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

N=int(input())
s=[sorted(input()) for n in range(N)]
ans=0

for i in range(N):
    for j in range(1,N-i):
        if s[i]==s[i+j]:
            ans+=1

print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline

N=int(input())

D={}
ans=0
for i in range(N):
    s =".".join(sorted(input()))
    if s in D.keys():
        ans+=D[s]
        D[s] += 1
    else:
        D[s]=1

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

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

def lcm(x, y):
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    return (x * y) // gcd(x, y)
X = lcm(N ,M)

if S[0] != T[0]:
    print(-1)
elif X == N*M:
    print(N*M)

else:
    for i in range(1,(N*M//X)+1):
        L = X * i
        counter = L
        y = L // N
        z = L // M
        match = lcm( y, z)
        for j in range(1, (L // match) ):
            k = j * N * match // L
            l = j * M * match // L
            if S[k] != T[l]:
                counter = -1
        if counter == L:
            break
    print(counter)


### FIXED CODE ###

N, M = map(int, input().split())
S = str(input())
T = str(input())
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
 
def lcm(x, y):
    return (x * y) // gcd(x, y)
X = lcm(N ,M)
 
if S[0] != T[0]:
    print(-1)
elif X == N*M:
    print(N*M)
else:
        L = X
        match = lcm(  L // N,  L // M)
        for j in range(1, (L // match) ):
            if S[j * N * match // L] != T[ j * M * match // L]:
                L = -1
                break
        if L == X :
            print(L)
        else:
            print(-1)
### BUGGY CODE ###

N,Y = map(int, input().split())


a = Y//10000
b = Y//5000
c = Y//1000

flag = False

for i in range(a+1):
    if flag == True:
        break
    for j in range(b+1):
        if flag == True:
            break
        for k in range(c+1):
            if i+j+k == N:
                if i*10000+j*5000+k*1000 == Y:
                    flag = True
                    s = i
                    t = j
                    u = k

if flag == True:
    print(s,t,u)
else:
    print(-1,-1,-1)

### FIXED CODE ###

N,Y = map(int, input().split())


a = Y//10000
b = Y//5000

flag = False

for i in range(a+1):
    if flag == True:
        break
    for j in range(b+1):
        if N-i-j<0:
            break
        if i*10000+j*5000+(N-i-j)*1000 == Y:
            flag = True
            s = i
            t = j
            u = N-i-j
            break

if flag == True:
    print(s,t,u)
else:
    print(-1,-1,-1)
### BUGGY CODE ###

N = int(input())
alist = [int(input()) for i in range(N)]
### 三角形が成立しない場合を数える
MOD = 998244353
asum = [0]
for i in range(N):
    asum += [asum[-1] + alist[i]]
S = asum[-1]
Sharf = S / 2

#dptable[i番目までは振り分けた][Rの合計] -> そこからR>=S/2となる数
tbsize = int(Sharf//1)+1
dptable = [[0 for j  in range(tbsize)] for k in range(N)]
dpflag = [[False for j  in range(tbsize)] for k in range(N)]
def ddpR(cur_N, R): #R>=S/2となる数
    if cur_N == N: #末端
        ret = 1 if R >= Sharf else 0
        return ret 
    if R >= Sharf: #R>=S/2はこれ以降のパターン全てR>=S/2
        #となるので残りの要素をRGBどこに割り振っても良い
        ret = pow(3, N-cur_N, MOD)
        return ret
    if asum[cur_N] - R > Sharf: #Rに入れないものがS/2を超える
        return 0 #どう頑張ってもR >= S/2を実現できない
    if dpflag[cur_N][R]: #DPテーブルにある
        return dptable[cur_N][R]
    
    #そうではない場合は計算が必要
    ai = alist[cur_N]
    #aiをRGBのどれかに振り分ける
    retR = ddpR(cur_N+1, R+ai) #Rに振り分けた場合
    retGB = ddpR(cur_N+1,R) * 2 #Rに入れなかった場合, GBで2通りあるので2倍
    ret = (retR+retGB) % MOD
    dpflag[cur_N][R] = True
    dptable[cur_N][R] = ret
    return ret

#dptable2[i番目までは振り分けた][Rの合計] -> そこからR=G=S/2, B=0となる数
dptable2 = [[0 for j  in range(tbsize)] for k in range(N)]
dpflag2 = [[False for j  in range(tbsize)] for k in range(N)]
def ddpRG(cur_N, R): #R=G=S/2,B=0の場合
    if cur_N == N:
        return 1 if R==Sharf else 0
    if R == Sharf:
        return 1
    if (R > Sharf) or (asum[cur_N]-R > Sharf):
        return 0
    if dpflag2[cur_N][R]:
        return dptable2[cur_N][R]
    ai = alist[cur_N]
    retR = ddpRG(cur_N+1, R+ai)
    retG = ddpRG(cur_N+1,R)
    ret = (retR+retG) % MOD
    dpflag2[cur_N][R] = True
    dptable2[cur_N][R] = ret
    return ret
score = pow(3, N, MOD) - ddpR(0, 0)*3 + ddpRG(0, 0)*3
score = score % MOD
print(score)

### FIXED CODE ###

N = int(input())
alist = [int(input()) for i in range(N)]
import numpy as np
### 三角形が成立しない場合を数える
alist.sort(reverse=False) #大きい方からチェックするとS/2に早く到達しやすい
MOD = 998244353
asum = [0]
for i in range(N):
    asum += [asum[-1] + alist[i]]
S = asum[-1]
Sharf = S / 2

#dptableA[i番目までは振り分けた][Rの合計] -> そこからR>=S/2となる数
dptableA = np.zeros((N+1, S+1), dtype=np.int) #[[0 for i in range(S+1)] for j in range(N+1)]
dptableA[N, int(np.ceil(Sharf)):] = 1
#dptableB[i番目までは振り分けた][Rの合計] -> そこからR=G=S/2, B=0となる数
dptableB = np.zeros((N+1, S+1), dtype=np.int) #[[0 for i in range(S+1)] for j in range(N+1)]
if S %2 == 0:
    dptableB[N, int(Sharf)] = 1 

#dpの計算をまとめて行う
for i in range(N, 0, -1): #後ろから見ていく
    n = i - 1
    an = alist[n]
    asn = asum[n]
    dptableA[n, 0:asn+1] = (2*dptableA[n+1, 0:asn+1] + dptableA[n+1, an:an+asn+1])%MOD
    #dptableA[n] = [(2*dptableA[n+1][k]+dptableA[n+1][k+alist[n]]) % MOD for k in range(asum[n]+1)]
    dptableB[n, 0:asn+1] = (dptableB[n+1, 0:asn+1] + dptableB[n+1, an:an+asn+1])%MOD
    #dptableB[n] = [(dptableB[n+1][k]+dptableB[n+1][k+alist[n]]) %MOD for k in range(asum[n]+1)]
retA, retB = dptableA[0,0], dptableB[0,0]
#全体 - (ある辺がS/2以上) + (2辺がS/2)
ans = (pow(3, N, MOD) - retA*3 + retB*3) % MOD
print(ans)
### BUGGY CODE ###

import heapq
N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
F = sorted(list(map(int, input().split())), reverse=True)
C = [(-A[i]*F[i], F[i], A[i]) for i in range(N)]
heapq.heapify(C)
x1, y1, z1 = heapq.heappop(C)
while z1 > 0 and K > 0:
    #print(x1, y1)
    x2, y2, z2 = heapq.heappop(C)
    a = min((x2 - x1)//z1 + 1, K, z1)
    K -= a
    heapq.heappush(C, (x1 + a*y1, y1, z1 - a))
    x1, y1, z1 = x2, y2, z2
    #print(y2)
print(- x1)

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
A = np.array(sorted(list(map(int, input().split()))))
F = np.array(sorted(list(map(int, input().split())), reverse=True))

left = - 1
right = 10**12

def f(x):
    return np.maximum(0, A - x//F) .sum()<= K

while right - left > 1:
    mid = (left + right)//2
    if f(mid):
        right = mid
    else:
        left = mid
    
print(right)
### BUGGY CODE ###

from collections import deque


h, w = map(int, input().split())
hs, ws = set(range(h)), set(range(w))
a = []
d = deque([])
memo = [[None] * w for j in hs]
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
for i in hs:
    a.append(list(input()))
for i in hs:
    for j in ws:
        if a[i][j] == '#':
            d.append([i, j])
            memo[i][j] = 0


def d_list_update(d, hmax, wmax):
    dh, dw = d.popleft()
    for i, j in move:
        if (0 <= dh + i < hmax) and (0 <= dw + j < wmax) and not(memo[dh + i][dw + j]):
            memo[dh + i][dw + j] = memo[dh][dw] + 1
            d.append([dh + i, dw + j])
    return d


while(d):
    d = d_list_update(d, h, w)
ans = max([max(e) for e in memo])
print(ans)


### FIXED CODE ###

from collections import deque
 
 
h, w = map(int, input().split())
hs, ws = set(range(h)), set(range(w))
d = deque()
memo = [[-1] * w for j in hs]
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
a = tuple(input() for _ in hs)
b = [[i, j] for i in hs for j in ws if a[i][j] == '#']
for i, j in b:
    d.append((i, j))
    memo[i][j] = 0
while d:
    dh, dw = d.popleft()
    for i, j in move:
        dhn, dwn = dh + i, dw + j
        if (0 <= dhn < h) and (0 <= dwn < w) and (memo[dhn][dwn] < 0):
            d.append((dhn, dwn))
            memo[dhn][dwn] = memo[dh][dw] + 1
ans = max([max(e) for e in memo])
print(ans)
### BUGGY CODE ###

S=input()
x,y=map(int,input().split())
Xmove=[]
Ymove=[]
xdist=True
cnt=0
for i in range(len(S)):
  if S[i]=="T":
    if xdist:
      Xmove.append(cnt)
    else:
      Ymove.append(cnt)
    cnt=0
    xdist^=True
  else:
    cnt+=1
if S[-1]=="F":
  if xdist:
    Xmove.append(cnt)
  else:
    Ymove.append(cnt)

dpX=[[False for j in range(16001)] for i in range(len(Xmove)+1)]
dpY=[[False for j in range(16001)] for i in range(len(Ymove)+1)]

indX=0
if S[0]=="F":
  dpX[1][8000+Xmove[0]]=True
  indX=1
else:
  dpX[0][8000]=True
dpY[0][8000]=True

for i in range(indX,len(Xmove)):
  for j in range(len(dpX[i])):
    if dpX[i][j]:
      dpX[i+1][j-Xmove[i]]=True
      dpX[i+1][j+Xmove[i]]=True


if not dpX[-1][x+8000]:
  print("No")
  exit(0)

for i in range(len(Ymove)):
  for j in range(len(dpY[i])):
    if dpY[i][j]:
      dpY[i+1][j+Ymove[i]]=True
      dpY[i+1][j-Ymove[i]]=True

print(("No","Yes")[dpY[-1][y+8000]])    
  

### FIXED CODE ###

S = input()
X,Y = map(int,input().split())

# [文字,その文字が連続する数]
from collections import deque
sumS = deque()
import itertools
for key,g in itertools.groupby(S):
  sumS.append([key,len(list(g))])
  
startx = 0 # Fで始まる場合はX軸の正の方向にあらかじめ進めて置く
# 最初のTが出るまではX軸正の方向に進む
if sumS[0][0] == "F":
  startx = sumS[0][1]
  sumS.popleft()

xdir = True # X軸方向を向いている
dpXcur = set()
dpXcur.add(startx)
dpYcur = set()
dpYcur.add(0) # Y軸は必ず0から始まる
dpXnex = set()
dpYnex = set()
for i in range(len(sumS)):
  if sumS[i][0] == "F":
    steps = sumS[i][1] # 進む数
    if xdir: # X軸方向を向いている場合
      for x in dpXcur:
        dpXnex.add(x + steps)
        dpXnex.add(x - steps)
      dpXcur = dpXnex
      dpXnex = set()
    else:
      for y in dpYcur:
        dpYnex.add(y + steps)
        dpYnex.add(y - steps)
      dpYcur = dpYnex
      dpYnex = set()
  elif sumS[i][0] == "T":
    turns = sumS[i][1] # 方向転換する数
    if turns % 2 == 1:
      # 奇数回の場合はX/Y軸の切り替え (偶数回の場合は何も起こらない)
      xdir ^= True
      
if X in dpXcur and Y in dpYcur:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

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

for i in range(n):
  b[i] = a.index(i+1)+1
  
  
print(*b)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
d=[0]*n
for i,val in enumerate(l):
  d[val-1]=i+1
print(*d)
### BUGGY CODE ###

n = int(input())
l = [int(input()) for _ in range(n)]

for i in range(n):
    if i == 0:
        print(max(l[i+1:]))
    elif i == n-1:
        print(max(max(l[:i]), l[-1]))
    elif i == n:
        print(max(l[:i]))
    else:
        print(max(max(l[:i]), max(l[i+1:])))

### FIXED CODE ###

n = int(input())
l = [int(input()) for _ in range(n)]
_l = l.copy()
_l.sort(reverse=True)
lmax = _l[0]
lsec = _l[1]

for i in range(n):
    if l[i] == lmax:
        print(lsec)
    else:
        print(lmax)
### BUGGY CODE ###

import copy
def main():
    n = int(input())
    s = [list(map(int,list((input())))) for i in range(n)]
    k = []
    f = True
    for start in range(n):
        s_ = copy.deepcopy(s)
        group = [0]*n
        group[start] = 1
        v = [start]
        searched = set([start])
        mx_k = 2
        f = True
        while True:
            v_ = []
            for i in v:
                edge = s_[i]
                for j in range(n):
                    if edge[j] == 1:
                        if group[j] == 0:
                            v_.append(j)
                            group[j] = mx_k
                        elif not abs(group[j]-group[i])==1:
                            f = False
                            break
                searched = searched | set(v)
                if not f:
                    break
            if not f:
                break
            if len(searched) == n:
                k.append(mx_k-1)
                break
            v = copy.deepcopy(v_)
            mx_k += 1
    if k:
        print(max(k))
    else:
        print(-1)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import copy
def main():
    n = int(input())
    s = [list(map(int,list((input())))) for i in range(n)]
    k = []
    f = True
    for start in range(n):
        s_ = copy.deepcopy(s)
        group = [0]*n
        group[start] = 1
        v = [start]
        searched = set([start])
        mx_k = 2
        f = True
        while True:
            v_ = []
            for i in v:
                edge = s_[i]
                for j in range(n):
                    if edge[j] == 1:
                        if group[j] == 0:
                            v_.append(j)
                            group[j] = mx_k
                        elif not abs(group[j]-group[i])==1:
                            f = False
                            break
                searched = searched | set(v)
                if not f:
                    break
            if not f:
                break
            if len(searched) == n:
                k.append(mx_k-1)
                break
            v = copy.deepcopy(v_)
            mx_k += 1
    if k:
        print(max(k))
    else:
        print(-1)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N = int(input())
tmp = input()

WL = []
WL.append(tmp)
leng = 1

for i in range(N-1):
    flg = 1
    tmp = input()
    for j in range(leng):
        if tmp == WL[j]:
            flg = 0
            break
    if flg == 1:
        WL.append(tmp)
        leng += 1

print(leng)

### FIXED CODE ###

N = int(input())

WL = []
for i in range(N):
    WL.append(input())

print(len(set(WL)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
score = 0
for i in range(0, N-1):
    score += A[i] * sum(A[i+1:])
print(score % (10**9+7))


### FIXED CODE ###

import sys
input = sys.stdin.readline
 
N = int(input())
A = list(map(int, input().split()))
score = 0
sum_A = sum(A)
for a in A[:-1]:
  sum_A -= a
  score += a * sum_A
print(score % (10**9+7))
### BUGGY CODE ###

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

count = 1
for i in range(1,N):
    for j in range(i):
        if(P[i]>P[j]):
            break
        elif(i == j + 1):
            count+=1

print(count)



### FIXED CODE ###

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

Pmin = float("inf")
count = 0
for i in P:
    if i < Pmin:
        Pmin = i
        count += 1

print(count)
### BUGGY CODE ###

n, m = list(map(int, input().split()))
tmps = [[] for _ in range(n)]
pys = []

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

for tmp in tmps:
    tmp.sort()

for py in pys:
    p, y = py
    yindex = tmps[p-1].index(y)+1
    print('{:06}'.format(p) + '{:06}'.format(yindex))

### FIXED CODE ###

n, m = list(map(int, input().split()))
tmps = [[] for _ in range(n)]
pyxs = []

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

pyxs.sort(key = lambda x: x[1])

num = [0] * (n+1)
ans = [None]*m

for p, y, x in pyxs:
    ans[x] = '{:06}'.format(p) + '{:06}'.format(num[p]+1)
    num[p] += 1

for s in ans:
    print(s)
### BUGGY CODE ###

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

ans = "Yes"

for i in range(n):
    for j in range(i):    
        if h[i] < h[j]-1:
            ans = "No"
            break

print(ans)


### FIXED CODE ###

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

ans = "Yes"
max = h[0]

for i in range(n):
    if h[i] < max-1:
        ans = "No"
    if h[i] > max:
        max = h[i]
    

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

#!/usr/bin/env python3

import sys


def main():
    n, m, q = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]

    cities_l = [[] for i in range(n+1)]
    cities_r = [[] for i in range(n+1)]
    cities_qp = [[] for i in range(n+1)]
    cities_qq = [[] for i in range(n+1)]

    table = {(i, j): 0 for i in range(n+1) for j in range(n+1)}

    for i in range(m):
        l, r = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
        for j in range(0, l+1):
            for k in range(r, n+1):
                table[(j, k)] += 1
        #cities_l[l].append(i)
        #cities_r[r].append(i)

    for i in range(q):
        qp, qq = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
        print(table[(qp, qq)])
        #cities_qp[qp].append(i)
        #cities_qq[qq].append(i)

    #z = set()
    #ans = [[[], []] for i in range(q)]
    #for i in range(1,n+1):
    #    z |= set(cities_qp[i])
    #    for j in z:
    #        ans[j][0] += cities_l[i]
    #       ans[j][1] += cities_r[i]
    #    z -= set(cities_qq[i])

    #for i in range(q):
    #    print(len(set(ans[i][0]) & set(ans[i][1])))

if __name__=='__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3

import sys


def main():
    n, m, q = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]

    x = [[0 for j in range(n+1)] for i in range(n+1)]
    c = [[0 for j in range(n+1)] for i in range(n+1)]
    z = [[0 for j in range(n+1)] for i in range(n+1)]

    for i in range(m):
        l, r = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
        x[l][r] += 1
    
    for i in range(1, n+1):
        for j in range(1, n+1):
            c[i][j] = c[i][j-1] + x[i][j]

    for j in range(1, n+1):
        for i in range(1, n+1):
            z[i][j] = z[i-1][j] + c[i][j]
    
    for i in range(q):
        qp, qq = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
        print(z[qq][qq] - z[qq][qp-1] - z[qp-1][qq] + z[qp-1][qp-1])


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

N = int(input())
a = list(input().split())
A = [int(a[i])for i in range(N)]
frag = [0 for i in range(60)]
mod = 10 ** 9 + 7

for i in range(N):
    for j in range(len(bin(A[i])) - 2):
        if A[i] & (1 << j):
            frag[j] += 1

print(sum([(frag[i] * (N - frag[i]) * 2 ** i) % mod for i in range(60)]) % mod)

### FIXED CODE ###

N = int(input())
a = list(input().split())
A = [int(a[i])for i in range(N)]
frag = [0 for i in range(60)]
mod = 10 ** 9 + 7
ans = 0

for i in range(60):
    j = 1 << i
    cnt = sum((k & j) >> i for k in A)
    ans += (cnt * (N - cnt)) << i
    ans %= mod
    
print(ans)
### BUGGY CODE ###

L = input()
n = 1

for i, s in enumerate(L[::-1]):
    if s == '1':
        n = n * 2 + 3 ** i
        n %= 10 ** 9 + 7

print(n)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000)

L = input()
n = 1
p = (1, 0)  # 3 ** 0 = 1
mod = 10 ** 9 + 7

for i in range(len(L)):
    if L[len(L) - 1 - i] == '1':
        k = (p[0] * (3 ** (i - p[1]))) % mod
        n = n * 2 + k
        n %= mod
        p = (k, i)

print(n)