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

def sol():
    N = int(input())
    XYP = [tuple(map(int, input().split())) for _ in range(N)]
    X = [x for x, _, _ in XYP]
    Y = [y for _, y, _ in XYP]
    INF = 10**18

    def calcCost(AP, A):
        ret = [[INF] * N for _ in range(1 << N)]
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i, (a, p) in enumerate(AP):
                cost = abs(a)
                for z in useA:
                    cost = min(cost, abs(a - z))
                ret[state][i] = cost * p
        return ret

    costX = calcCost([(x, p) for x, _, p in XYP], X)
    costY = calcCost([(y, p) for _, y, p in XYP], Y)

    def makeState(state, sign):
        ret = 0
        for s in state[::-1]:
            ret <<= 1
            if s == sign:
                ret |= 1
        return ret

    ans = [INF] * (N + 1)
    for state in range(pow(3, N)):
        stateX = 0
        stateY = 0
        M = N
        for _ in range(N):
            state, r = divmod(state, 3)
            stateX <<= 1
            stateY <<= 1
            if r == 0: M -= 1
            if r == 1: stateX |= 1
            if r == 2: stateY |= 1

        cost = 0
        for i in range(N):
            cost += min(costX[stateX][i], costY[stateY][i])

        if ans[M] > cost:
            ans[M] = cost

    print(*ans, sep='\n')

sol()

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from numba import njit
import numpy as np
INF = 10**18

@njit('(i8, i8[:,:])')
def solve(N, XYP):
    X = XYP[:, 0]
    Y = XYP[:, 1]

    def calcCost(sign, A):
        ret = np.ones((1 << N, N), dtype=np.int64) * INF
        for state in range(1 << N):
            useA = [a for i, a in enumerate(A) if (state & (1 << i)) != 0]
            for i in range(N):
                xyp = XYP[i]
                cost = abs(xyp[sign])
                for z in useA:
                    cost = min(cost, abs(xyp[sign] - z))
                ret[state][i] = cost * xyp[2]
        return ret

    costX = calcCost(0, X)
    costY = calcCost(1, Y)
    ans = np.ones(N + 1, dtype=np.int64) * INF

    for state in range(pow(3, N)):
        stateX = 0
        stateY = 0
        M = N
        for _ in range(N):
            state, r = divmod(state, 3)
            stateX <<= 1
            stateY <<= 1
            if r == 0: M -= 1
            if r == 1: stateX |= 1
            if r == 2: stateY |= 1

        cx, cy = costX[stateX], costY[stateY]
        cost = 0
        for i in range(N):
            cost += min(cx[i], cy[i])
        ans[M] = min(ans[M], cost)

    for a in ans:
        print(a)

def sol():
    N = int(input())
    XYP = np.asarray([list(map(int, input().split())) for _ in range(N)])
    solve(N, XYP)

sol()
### BUGGY CODE ###

import networkx as nx
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


G = nx.Graph()
N, M = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(M)]
G.add_edges_from(edge)
path = nx.shortest_path(G, source=1)

print("Yes")
for i in range(2, N + 1):
    print(path[i][-2])

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())
edge = [[] for _ in range(N + 1)]
for _ in range(M):
    x, y = map(int, input().split())
    edge[x].append(y)
    edge[y].append(x)

prev = [None] * (N + 1)
seen = [False] * (N + 1)
node = deque([1])
seen[1] = True

while node:
    s = node.popleft()
    for t in edge[s]:
        if not seen[t]:
            seen[t] = True
            prev[t] = s
            node.append(t)

if any(x is None for x in prev[2:]):
    print("No")
else:
    print("Yes")
    print(*prev[2:], sep="\n")
### BUGGY CODE ###

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
              #if (d[i][k] != float("INF")) and (d[k][j] != float("INF")):
                if d[i][j] > d[i][k] + d[k][j]:
                  d[i][j] = d[i][k] + d[k][j]
                  if [i, j] in hen:
                    ll = hen.index([i, j])
                    used[ll] += 1
                  elif [j, i] in hen:
                    ll = hen.index([j, i])
                    used[ll] += 1 
        #print(d)
    return d

##############################
n,m = map(int,input().split()) #n:頂点数　m:辺の数

d = [[float("INF")] * n for i in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
used = [0] * m
hen = [0] * m
for i in range(m):
    x,y,z = map(int,input().split())
    d[x - 1][y - 1] = z
    d[y - 1][x - 1] = z
    hen[i] = [x - 1, y - 1]
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０

ans = warshall_floyd(d)
#それぞれの出発地点ごとにmaxをとり、そのmaxが最小の地点に引っ越し
#そのときの所要時間がp
#print(used)
zero = used.count(0)
ans = m - zero
print(ans)





### FIXED CODE ###

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
              #if (d[i][k] != float("INF")) and (d[k][j] != float("INF")):
                d[i][j] = min(d[i][k] + d[k][j], d[i][j])
                
        #print(d)
    return d

##############################
n,m = map(int,input().split()) #n:頂点数　m:辺の数

d = [[float("INF")] * n for i in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)

hen = [0] * m
for i in range(m):
    x,y,z = map(int,input().split())
    d[x - 1][y - 1] = z
    d[y - 1][x - 1] = z
    hen[i] = [x - 1, y - 1, z]
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０

ans = warshall_floyd(d)
#それぞれの出発地点ごとにmaxをとり、そのmaxが最小の地点に引っ越し
#そのときの所要時間がp
#print(used)
answer = 0
for i in range(m):
  now = hen[i]
  if d[now[0]][now[1]] != now[2]:
    answer += 1
  
print(answer)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
a=1
for i in l:
  a=a*i
if a>10**18:
  print(-1)
else:
  print(a)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
if 0 in l:
  print(0)
else:
  a=1
  for i in l:
    a=a*i
    if a>10**18:
      print(-1)
      exit()
  print(a)
### BUGGY CODE ###

while True:
    n = int(input())
    if n == 0:
        break
    sum_max = 0
    a = []
    for i in range(n):
        a.append(int(input()))
        for j in range(i + 1):
            sum_tmp = sum(a[j:i + 1])
            if sum_tmp > sum_max:
                sum_max = sum_tmp
    print(sum_max)



### FIXED CODE ###

while True:
    n = int(input())
    if n == 0:
        break
    dp = [int(input())]
    for i in range(1, n):
        a_i = int(input())
        dp.append(max(dp[i - 1] + a_i, a_i))
    print(max(dp))
### BUGGY CODE ###


INF = float("INF")


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

cost = [[INF] * N for _ in range(N)]
for i in range(N):
    cost[i][i] = 0

for _ in range(M):
    v1, v2, w = map(int, input().split())
    v1, v2 = v1-1, v2-1
    cost[v1][v2] = w
    cost[v2][v1] = w

for k in range(N):
    for i in range(N):
        for j in range(N):
            cost[i][j] = min(
                cost[i][j],
                cost[i][k] + cost[k][j])

for i in range(N):
    for j in range(N):
        if cost[i][j] == 0:
            pass
        elif cost[i][j] <= L:
            cost[i][j] = 1
        else:
            cost[i][j] = INF

for k in range(N):
    for i in range(N):
        for j in range(N):
            cost[i][j] = min(
                cost[i][j],
                cost[i][k] + cost[k][j])

q = int(input())
for _ in range(q):
    s, t = map(int, input().split())
    ans = cost[s-1][t-1]
    if ans == INF:
        print(-1)
    else:
        print(ans - 1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
 
n, m, l = map(int, input().split())
 
INF = float("INF")
 
d = [[INF] * n for _ in range(n)]
for i in range(n):
    d[i][i] = 0
 
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d[a][b] = c
    d[b][a] = c
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
 
# print()
# print(*d, sep='\n')
 
for i in range(n):
    for j in range(n):
        if i == j:
            continue
 
        if d[i][j] <= l:
            d[i][j] = 1
        else:
            d[i][j] = INF
 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k] + d[k][j]:
                d[i][j] = d[i][k] + d[k][j]
 
# print()
# print(*d, sep='\n')
 
q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
 
    if d[s][t] == INF:
        print(-1)
    else:
        print(d[s][t]-1)
### BUGGY CODE ###

n,k=map(int,input().split())
while(abs(n-k)<n):
    n=abs(n-k)
print(n)

### FIXED CODE ###

def zettai(n,k):
    return abs(n-k)
n,k=map(int,input().split())
n=n%k
while(zettai(n,k)<n):
    n=zettai(n,k)
print(n)
### BUGGY CODE ###

#!python3

def LI():
    return list(map(int, input().split()))

# input
N = int(input())
UVW = [LI() for _ in range(N - 1)]

# params
link = [[] for _ in range(N)]
w = [[None] * N for _ in range(N)]
for u, v, c in UVW:
    u -= 1
    v -= 1
    link[u].append(v)
    link[v].append(u)
    w[u][v] = w[v][u] = c


def dfs(ans, x):
    for y in link[x]:
        if ans[y] is None:
            if w[x][y] % 2 == 0:
                ans[y] = ans[x]
            else:
                ans[y] = 1 ^ ans[x]
            dfs(ans, y)


def main():
    ans = [None] * N
    ans[0] = 0
    dfs(ans, 0)
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!python3

import sys
sys.setrecursionlimit(10 ** 6)


def LI():
    return list(map(int, input().split()))

# input
N = int(input())
UVW = [LI() for _ in range(N - 1)]


# params
link = [[] for _ in range(N)]
for u, v, w in UVW:
    u -= 1
    v -= 1
    link[u].append((v, w))
    link[v].append((u, w))


def dfs(ans, x):
    for y, w in link[x]:
        if ans[y] is None:
            if w % 2 == 0:
                ans[y] = ans[x]
            else:
                ans[y] = 0 if ans[x] else 1
            dfs(ans, y)


def main():
    ans = [None] * N
    ans[0] = 0
    dfs(ans, 0)
    for a in ans:
        print(a)


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

import itertools


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

C = list(itertools.permutations(V, N))
S = set(C)
ans = 0
for s in S:
    a = s[0]
    for i in range(1, N):
        a = (a + s[i]) / 2
    ans = max(ans, a)
print(ans)

### FIXED CODE ###

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

C = sorted(V)

ans = 0
a = C[0]
for i in range(1, N):
    a = (a + C[i]) / 2
ans = max(ans, a)
print(ans)
### BUGGY CODE ###

import sys
from collections import deque
import heapq

def solve():
    input = sys.stdin.readline
    N, M, P = map(int, input().split())
    graph = [None for i in range(M)]
    for i in range(M):
        a, b, c = map(int, input().split())
        graph[i] = (a - 1, b - 1, P - c)

    gain = [10 ** 20 for i in range(N)]
    gain[0] = 0
    
    for i in range(N):
        update = False
        for efrom, eto, ecost in graph:
            if gain[efrom] < 10 ** 20 and gain[eto] > gain[efrom] + ecost:
                gain[eto] = gain[efrom] + ecost
                update = True
        if not update:
            print(max(-gain[N-1], 0))
            break
    else:
        possible_min = gain[N-1]
        for i in range(N):
            for efrom, eto, ecost in graph:
                if gain[efrom] < 10 ** 20 and gain[eto] > gain[efrom] + ecost:
                    gain[eto] = gain[efrom] + ecost

        if gain[N-1] == possible_min: print(max(-gain[N-1], 0))
        else: print(-1)

    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
from collections import deque
import heapq

def solve():
    input = sys.stdin.readline
    N, M, P = map(int, input().split())
    graph = [None for i in range(M)]
    for i in range(M):
        a, b, c = map(int, input().split())
        graph[i] = (a - 1, b - 1, P - c)

    gain = [10 ** 20 for i in range(N)]
    gain[0] = 0
    
    for i in range(N):
        update = False
        for efrom, eto, ecost in graph:
            if gain[efrom] < 10 ** 20 and gain[eto] > gain[efrom] + ecost:
                gain[eto] = gain[efrom] + ecost
                update = True
        if not update:
            print(max(-gain[N-1], 0))
            break
    else:
        possible_min = gain[N-1]
        for i in range(N):
            for efrom, eto, ecost in graph:
                if gain[efrom] < 10 ** 20 and gain[eto] > gain[efrom] + ecost:
                    gain[eto] = gain[efrom] + ecost

        if gain[N-1] == possible_min: print(max(-gain[N-1], 0))
        else: print(-1)

    return 0

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

n,m = map(int, input().split())
LR = [list(map(int, input().split())) for i in range(m)]
ANS = []
for i in range(m):
  ANS.append(set(range(LR[i][0],LR[i][1]+1)))
  
X = ANS[0]
for i in range(1,m):
  X = X&ANS[i]
  
print(len(X))

### FIXED CODE ###

n,m = map(int, input().split())
LR = [list(map(int, input().split())) for i in range(m)]
X = [LR[i][0] for i in range(m)]
Y = [LR[i][1] for i in range(m)]

print(max(min(Y)-max(X)+1,0))
### BUGGY CODE ###

X = int(input())
Y = 100
i = 0
while 1:
  if X == Y:
    print(i)
    break
  Y += Y // 100
  i += 1

### FIXED CODE ###

X = int(input())
Y = 100
i = 0
while 1:
  if X <= Y:
    print(i)
    break
  Y += Y // 100
  i += 1
### BUGGY CODE ###

import copy
n=int(input())
A=list(map(int,input().split()))

for i in range(n):
    print(A.count(i+1))


### FIXED CODE ###

import copy
n=int(input())
A=list(map(int,input().split()))
L=[0]*n

for x in A:
    L[x-1] += 1
for i in L:
    print(i)
### BUGGY CODE ###

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

ans = 0
dp = [0] * (S + 1)

for a in A:
    dp[0] += 1
    for s in range(S + 1)[:: -1]:
        if s + a <= S:
            dp[s + a] += dp[s]
    ans += dp[S]

print(ans % MOD)

### FIXED CODE ###

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

dp = [0] * (S + 1)
ans = 0

for i, a in enumerate(A):
    for s in range(S + 1)[:: -1]:
        if s + a <= S:
            dp[s + a] += dp[s]
    if a <= S:
        dp[a] += (i + 1)
    ans += dp[S]

print(ans % MOD)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
for i in range(1,N+1):
    ans=A.count(i)
    print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans=[0]*N
for i in A:
  ans[i-1]+=1
for j in range(N):
  print(ans[j])
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
xyh = [LI() for _ in range(n)]
lst = []
for cx in range(101):
    for cy in range(101):
        for x,y,h in xyh:
            X,Y = abs(cx-x), abs(cy-y)
            if h == 0:
                lst.append([X+Y,cx,cy,1])
            else:
                lst.append([X+Y+h,cx,cy,0])
for a,b,c,d in lst:
    if d:
        for H in range(1,a+1):
            for x,y,h in xyh:
                if max(H - abs(x-b) - abs(y-c),0) != h:
                    break
            else:
                print(b,c,H)
                quit()
    else:
        for x,y,h in xyh:
            if max(a - abs(x-b) - abs(y-c),0) != h:
                break
        else:
            print(b,c,a)
            quit()


### FIXED CODE ###

#!/usr/bin/env python3
#ABC112 C

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

maxh = 0
for x,y,h in xyh:
    maxh = max(maxh,h)
for H in range(maxh,maxh+201):
    for cx in range(101):
        for cy in range(101):
            for x,y,h in xyh:
                if h != max(H-abs(x-cx)-abs(y-cy),0):
                    break
            else:
                print(cx,cy,H)
                quit()
### BUGGY CODE ###

INF = 10**10

def chmax(a, b):
    if(a>b):
        return a
    else:
        return b

def chmin(a, b):
    if(a<b):
        return a
    else:
        return b


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

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

dp = N*[INF]
dp[0]=0


for i in range(1,N):
    for j in range(1,K+1):
        dp[i] = chmin(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
        if i < j:
            break

#print(dp)
print(dp[N-1])

### FIXED CODE ###

INF = 10**10

def chmax(a, b):
    if(a>b):
        return a
    else:
        return b

def chmin(a, b):
    if(a<b):
        return a
    else:
        return b


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

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

dp = N*[INF]
dp[0]=0


for i in range(1,N):
    for j in range(1,K+1):
        dp[i] = chmin(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
        if i < j:
            break

#print(dp)
print(dp[N-1])
### BUGGY CODE ###

count = int(input())
number_li = input().split(' ')

check = 'a'

check_3 = 0
for i in range(count):
    check_2 = 0
    for n in range(count):
        if check == number_li[i]:
            check_2 += 1    
        check = number_li[n]
    if check_2 > 1:
        check_3 = 1
        break

if check_3 == 0:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

count = int(input())
number_li = input().split(' ')
number_set = set(number_li)

list_len = len(number_li)
set_len = len(number_set)

if list_len == set_len:
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

n,*t=map(int,open(r:=0).read().split());A=t[:n];c=B=t[n:]
while c:
 c=0
 for i in range(n):b=B[~-i%n]+B[-~i%n];t=(A[i]<B[i]>b)*(B[i]-A[i])//b;c+=t;B[i]-=t*b
 r+=c
print([-1,r][A==B])

### FIXED CODE ###

from heapq import heappush,heappop
n,*t=map(int,open(0).read().split())
a=t[:n]
b=t[n:]
B=[]
for i,j in enumerate(b):heappush(B,(-j,i))
c=0
d=0
while B and d<2*10**6:
    d+=1
    y,i=heappop(B)
    x,z=b[(i-1)%n],b[(i+1)%n]
    t=(b[i]-a[i])//(x+z)
    b[i]-=t*(x+z)
    c+=t
    if b[i]>a[i]:
        heappush(B,(-b[i],i))
print([-1,c][a==b])
### BUGGY CODE ###

n,W=map(int,input().split())
w=[]
v=[]

for i in range(n):
    a=[int(j) for j in input().split()]
    w.append(a[0])
    v.append(a[1])

def dfs(i,j):
    if i==n:
        return 0
    elif j<w[i]:
        return dfs(i+1,j)
    else:
        return max(dfs(i+1,j),dfs(i+1,j-w[i])+v[i])

print(dfs(0,W))



### FIXED CODE ###

n,w=map(int,input().split())
wv=[]
dp=[[0 for i in range(100010)]for j in range(110)]
for i in range(n):
    a=[int(j) for j in input().split()]
    wv.append(a)

from operator import itemgetter
wv.sort(key=itemgetter(0))

for i in range(n):
    for j in range(w+1):
        if j>=wv[i][0]:
            dp[i+1][j]=max(dp[i][j],dp[i][j-wv[i][0]]+wv[i][1])
        else:
            dp[i+1][j]=dp[i][j]


print(dp[n][w])
### BUGGY CODE ###

from collections import deque
from itertools import product
import sys
input = sys.stdin.readline
h, w = map(int, input().split())
si, sj = map(lambda x: int(x)-1, input().split())
gi, gj = map(lambda x: int(x)-1, input().split())
fld = ''.join([input().rstrip()for _ in range(h)])
INF = 10**18


def to_v(i, j):
    return i*w+j


n = h*w
start = to_v(si, sj)
goal = to_v(gi, gj)


def generate_v2(v):
    i, j = divmod(v, w)
    if 0 < i:
        yield v-w
    if i < h-1:
        yield v+w
    if 0 < j:
        yield v-1
    if j < w-1:
        yield v+1


def generate_v2_b(v):
    i, j = divmod(v, w)
    it = [-2, -1, 1, 2]
    for di, dj in product(it, repeat=2):
        x, y = i+di, j+dj
        if x < 0 or h <= x or y < 0 or w <= y:
            continue
        yield x*w+y

    it = [(-2, 0), (2, 0), (0, -2), (0, 2)]
    for di, dj in it:
        x, y = i+di, j+dj
        if x < 0 or h <= x or y < 0 or w <= y:
            continue
        yield x*w+y


def bfs(init_v):
    next_v = deque([init_v])
    dist = [INF]*n
    dist[init_v] = 0
    while next_v:
        v = next_v.popleft()
        for v2 in generate_v2(v):
            if fld[v2] == '#':
                continue
            if dist[v2] <= dist[v]:
                continue
            dist[v2] = dist[v]
            next_v.append(v2)

        for v2 in generate_v2_b(v):
            if fld[v2] == '#':
                continue
            if dist[v2] <= dist[v]+1:
                continue
            dist[v2] = dist[v]+1
            next_v.append(v2)

    return dist


ans = bfs(start)[goal]
print(-1 if ans == INF else ans)


### FIXED CODE ###

import heapq
from itertools import product
h, w = map(int, input().split())
si, sj = map(lambda x: int(x)-1, input().split())
gi, gj = map(lambda x: int(x)-1, input().split())
fld = ''.join([input()for _ in range(h)])
INF = 10**18


def to_v(i, j):
    return i*w+j


n = h*w
start = to_v(si, sj)
goal = to_v(gi, gj)


def generate_v2(v):
    i, j = divmod(v, w)
    it = [-2, -1, 0, 1, 2]
    for di, dj in product(it, repeat=2):
        x, y = i+di, j+dj
        if x < 0 or h <= x or y < 0 or w <= y:
            continue
        if (di, dj) in [(-1, 0), (1, 0), (0, -1), (0, 1), (0, 0)]:
            d = 0
        else:
            d = 1
        yield d, x*w+y


def dijkstra(init_v):
    next_v = [(0, init_v)]
    dist = [INF]*n
    dist[init_v] = 0
    while next_v:
        d, v = heapq.heappop(next_v)
        if dist[v] < d:
            continue
        for d, v2 in generate_v2(v):
            if fld[v2] == '#':
                continue
            if dist[v2] <= dist[v]+d:
                continue
            dist[v2] = dist[v]+d
            heapq.heappush(next_v, (dist[v2], v2))
    return dist


ans = dijkstra(start)[goal]
print(-1 if ans == INF else ans)
### BUGGY CODE ###

n,m=map(int,input().split())
for i in reversed(range(1,m//n+1)):
  if  (m-i*n)%i==0 :break
print(i)
  

### FIXED CODE ###

n,m=map(int,input().split())
d=[]
f=1
while f*f<m+1:
  if m%f==0:
    d.append(f)
    d.append(m//f)
  f+=1
d.sort(reverse=True)
for i in d:
  if  (m-i*n)>=0 and (m-i*n)%i==0 :break
print(i)
### BUGGY CODE ###

n,m=map(int,input().split())
p=[]
for i in range(m):
    p.append(list(map(int,input().split())))
    p[i].append(i)
p.sort(key=lambda x:x[1])
count=0
for i in range(1,n+1):
    count = 0
    j=0
    while j<m:
        if p[j][0]==i:
            count +=1
            ans1 = '{0:06d}'.format(p[j][0])
            ans2 = '{0:06d}'.format(count)
            p[j].append(ans1 + ans2)
        j +=1
p.sort(key=lambda x: x[2])
for i in range(m):
    print(p[i][3])

### FIXED CODE ###

n,m=map(int,input().split())
p=[]
for i in range(m):
    p.append(list(map(int,input().split())))
    p[i].append(i)
p.sort(key=lambda x:x[1])
p.sort(key=lambda x:x[0])
count=0
j=0
for i in range(m):
    if p[i][0] != j:
        count = 1
        j=p[i][0]
    else:
        count += 1
    ans1 = '{0:06d}'.format(p[i][0])
    ans2 = '{0:06d}'.format(count)
    p[i].append(ans1 + ans2)
p.sort(key=lambda x: x[2])
for i in range(m):
    print(p[i][3])