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

from itertools import*

n,m,o=map(int,input().split())
*R,=map(int,input().split())
INF=float("inf")
d=[[INF]*n for _ in range(n)]
r=range
for i in r(n):
	d[i][i]=0
for _ in r(m):
	a,b,c=map(int,input().split())
	d[a-1][b-1]=d[b-1][a-1]=c
for k in r(n):
	for i in r(n):
		for j in r(n):
			d[i][j]=min(d[i][j],d[i][k]+d[k][j])
v=[[d[i-1][j-1]for j in R]for i in R]
m=INF
for t in permutations(r(o)):
	a=0;f=1
	for i,j in zip(t,t[1:]):
		if v[i][j]==INF:
			f=0
			break
		else:
			a+=v[i][j]
	if f:
		m=min(m,a)
print(m)

### FIXED CODE ###

from itertools import permutations

n,m,r=map(int,input().split())
*R,=map(int,input().split())
INF=float("inf")
dist=[[INF]*n for _ in range(n)]
for i in range(n):
	dist[i][i]=0
for _ in range(m):
	a,b,c=map(int,input().split())
	dist[a-1][b-1]=c
	dist[b-1][a-1]=c
for k in range(n):
	for i in range(n):
		for j in range(n):
			dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])
v=[]
for i in R:
	t=[]
	for j in R:
		t.append(dist[i-1][j-1])
	v.append(t)
mn=INF
for t in permutations(range(r)):
	a=0;f=1
	for i,j in zip(t,t[1:]):
		if v[i][j]==INF:
			f=0
			break
		else:
			a+=v[i][j]
	if f:
		mn=min(mn,a)
print(mn)
### BUGGY CODE ###

# encoding: "utf-8"

from collections import defaultdict

class Stdin:
    @staticmethod
    def read_line(converter=str):
        return [converter(x) for x in input().split()]
    
    @staticmethod
    def read_lines(n, converter=str):
        result = list()
        for _ in range(n):
            result.append(Stdin.read_line(converter))
        return result
    
    @staticmethod
    def convert(data, converter):
        assert(len(data) == len(converter))
        return tuple(map(lambda x, f: f(x), data, converter))

    @staticmethod
    def convert_lines(datas, n, converter):
        return [converter(data, n, converter) for data in datas]


def first_count_and_pop(xs):
    cnt = 0
    fst = xs[0]
    # cnt = xs.count(fst)
    for x in xs:
        if x != fst:
            break
        cnt += 1
    return (cnt, xs[cnt:])    
    

def main():
    _ = input()
    xs = Stdin.read_line(converter=int)
    xs.sort()
    ys = defaultdict(int)
    while xs:
        key = xs[0]
        cnt, xs = first_count_and_pop(xs)
        ys[key] += cnt
        ys[key-1] += cnt
        ys[key+1] += cnt

    print(max(ys.values()))

# def main_():
#     input()
#     xs = Stdin.read_line(converter=int)
#     xs.sort()
#     counts = list()
#     for i in range(100000):
#         if not xs:
#             counts.extend([0] * (100000 - len(counts)))
#             break     
#         elif i == xs[0]:
#             cnt, xs = first_count_and_pop(xs)
#             counts.append(cnt)
#         else:
#             counts.append(0)
#     m = 0
#     for i in range(0, 100000):
#         if i == 0:
#             temp = counts[i] + counts[i+1]
#         elif i == 100000 - 1:
#             temp = counts[i-1] + counts[i]
#         else:
#             temp = counts[i-1] + counts[i] + counts[i+1]
#         if m < temp:
#             m = temp
#     print(m)

if __name__ == "__main__":
    main()

### FIXED CODE ###

input()
a_list = [int(s) for s in input().split()]

count = [0]*100002

for a in a_list:
    count[a] += 1
    count[a+1] += 1
    count[a+2] += 1
    
print(max(count))
### BUGGY CODE ###

S = input()
dp = [0] * (len(S)+1)

if int(S[:4]) % 2019 == 0:
    dp[4] += 1

for i in range(5,len(S)+1):
    for j in range(i-4+1):
        # print("i: {}, j:{}".format(i, j))
        # print("string: {}".format(S[i-4-j:i]))
        if int(S[i-4-j:i]) % 2019 == 0:
            dp[i] += 1
    dp[i] += dp[i-1]

print(dp[len(S)])


### FIXED CODE ###

from collections import Counter

S = input()
MOD = 2019
mods = [0]
r = 0
for i, c in enumerate(S[::-1]):
    r += int(c) * pow(10, i, MOD)
    mods.append(r % MOD)

counter = Counter(mods)
# print("counter: {}".format(counter))

ans = 0
for v in counter.values():
    ans += v * (v-1) // 2

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

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

# 各数値の重複数辞書
countdic = dict()
for el in a:
    if el in countdic:
        countdic[el] += 1
    else:
        countdic[el] = 1

# 組み合わせ数
def combi(num):
    if num < 2:
        pair = 0
    else:
        pair = int(num * (num-1) / 2)
    return pair

# 各数字を抽出しない時と抽出した時の組み合わせ数
fulldic = dict()
reducedic = dict()
for k, v in countdic.items():
    fulldic[k] = combi(v)
    reducedic[k] = combi(v-1)
    
for el in a:
    print(sum(fulldic.values()) - (fulldic[el] - reducedic[el]))

### FIXED CODE ###

import collections
n = input()
a = list(input().split())

# 各数値の重複数辞書
counter = collections.Counter(a)

# 組み合わせ数
def combi(num):
    if num < 2:
        pair = 0
    else:
        pair = int(num * (num-1) / 2)
    return pair


total = sum([combi(v) for v in counter.values()])
for el in a:
    print(total - (counter[el] - 1))
### BUGGY CODE ###

R,G,B,N = map(int, input().split())

ans = 0
L = sorted([R,G,B], reverse=True)
for i in range(N//L[0]+1):
    if i*L[0] > N:
        break
    for j in range(N//L[1]+1):
        if i*L[0] + j*L[1] > N:
            break
        for k in range(N//L[2]+1):
            if i*L[0] + j*L[1] + k*L[2] > N:
                break
            elif i*L[0] + j*L[1] + k*L[2] == N:
                ans += 1

print(ans)

### FIXED CODE ###

R,G,B,N = map(int, input().split())

ans = 0
L = sorted([R,G,B], reverse=True)
for i in range(N//L[0]+1):
    for j in range((N-i*L[0])//L[1]+1):
        if (N-i*L[0]-j*L[1])%L[2] == 0:
                ans += 1

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

import numpy as np
n, w = map(int, input().split())
wv = [tuple(map(int, input().split())) for _ in range(n)]

dp = np.zeros((n+1, w+1), np.int64)

for i in range(n):
    for sum_w in range(w+1):
        wi = wv[i][0]
        vi = wv[i][1]
        if sum_w - wi >= 0:
            #dp[i+1][sum_w] = max(dp[i][sum_w - wi] + vi, dp[i+1][sum_w])
            dp[i+1][sum_w] = dp[i][sum_w - wi] + vi
        dp[i+1][sum_w] = max(dp[i][sum_w], dp[i+1][sum_w])

print(dp[n][w])

### FIXED CODE ###

import numpy as np

n, w = map(int, input().split())
wv = [tuple(map(int, input().split())) for _ in range(n)]

dp = np.zeros((n+1, w+1), np.int64)

for i, (wi, vi) in enumerate(wv):
    dp[i+1] = dp[i]
    np.maximum(dp[i][wi:], dp[i][:-wi] + vi, out=dp[i+1][wi:])
"""
for i in range(n):
    for sum_w in range(w+1):
        wi = wv[i][0]
        vi = wv[i][1]
        if sum_w - wi >= 0:
            dp[i+1][sum_w] = dp[i][sum_w - wi] + vi
        dp[i+1][sum_w] = max(dp[i][sum_w], dp[i+1][sum_w])
"""
#print(dp)
print(dp[n][w])
### BUGGY CODE ###

N, K = map(int, input().split())
A = [int(x) for x in input().split()]
list_score = [1]*(N-K+1)
for i in range(len(list_score)):
  for j in range(K):
    list_score[i] *=A[i+j]
    
for i in range(1, len(list_score)):
  if list_score[i] > list_score[i-1]:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

N, K = map(int, input().split())
A = [int(x) for x in input().split()]
for i in range(N-K):
  if A[i] >= A[i+K]:
    print('No')
  else:
    print('Yes')
### BUGGY CODE ###

from fractions import Fraction as F
mod=10**9+7
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[]
ret=1
cnt=0
for x in a:
	if x<0:
		b.append((-x,0))
	else:
		b.append((x,1))
b.sort(reverse=True)
p=-1
m=-1
for i in range(k):
	ret*=b[i][0]
	ret%=mod
	if b[i][1]==0:
		cnt+=1
		m=i
	else:
		p=i
if cnt%2==0:
	print(ret)
	exit()
ret1=-1
ret2=-1
f1=f2=0
if p!=-1:
	ret1=ret*pow(b[p][0],mod-2,mod)%mod
	for i in range(k,n):
		if b[i][1]==0:
			ret1*=b[i][0]
			ret1%=mod
			f1=1
			val1=F(b[i][0],b[p][0])
			break
if m!=-1:
	ret2=ret*pow(b[m][0],mod-2,mod)%mod
	for i in range(k,n):
		if b[i][1]==1:
			ret2*=b[i][0]
			ret2%=mod
			f2=1
			val2=F(b[i][0],b[m][0])
			break
if f1==0:
	ret1=-1
if f2==0:
	ret2=-1
if ret1==ret2==-1:
	ret=-1
	for i in range(k):
		ret*=b[-i-1][0]
	print(ret%mod)
elif ret1==-1:
	print(ret2)
elif ret2==-1:
	print(ret1)
else:
	if val1>val2:
		print(ret1)
	else:
		print(ret2)

### FIXED CODE ###

from fractions import Fraction as F
mod=10**9+7
n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[]
ret=1
cnt=0
for x in a:
	if x<0:
		b.append((-x,0))
	else:
		b.append((x,1))
b.sort(reverse=True)
p=-1
m=-1
for i in range(k):
	ret*=b[i][0]
	ret%=mod
	if b[i][1]==0:
		cnt+=1
		m=i
	else:
		p=i
if cnt%2==0:
	print(ret)
	exit()
ret1=-1
ret2=-1
f1=f2=0
if p!=-1:
	ret1=ret*pow(b[p][0],mod-2,mod)%mod
	for i in range(k,n):
		if b[i][1]==0:
			ret1*=b[i][0]
			ret1%=mod
			f1=1
			val1=F(b[i][0],b[p][0])
			break
if m!=-1:
	ret2=ret*pow(b[m][0],mod-2,mod)%mod
	for i in range(k,n):
		if b[i][1]==1:
			ret2*=b[i][0]
			ret2%=mod
			f2=1
			val2=F(b[i][0],b[m][0])
			break
if f1==0:
	ret1=-1
if f2==0:
	ret2=-1
if ret1==ret2==-1:
	ret=-1
	for i in range(k):
		ret*=b[-i-1][0]
		ret%=mod
	print(ret%mod)
elif ret1==-1:
	print(ret2)
elif ret2==-1:
	print(ret1)
else:
	if val1>val2:
		print(ret1)
	else:
		print(ret2)
### BUGGY CODE ###

from collections import defaultdict
import sys
from functools import lru_cache
sys.setrecursionlimit(100000)
N = int(input())
 
counts = [0,0,0]
for a in map(int,input().split()):
  counts[a-1] += 1

A,B,C = counts


# dp[i][j][k] = 残り1個の皿がi枚、残り2個の皿がj枚、残り3個の皿がk枚のときの回数の期待値
# dp[i][j][k] = (i/N)(dp[i-1][j][k])+(j/N)(dp[i+1][j-1][k])+(k/N)(dp[i][j+1][k-1])+(N-i-j-k/N)(dp[i][j][k])+1
# dp[i][j][k] = (i(dp[i-1][j][k])+j(dp[i+1][j-1][k])+k(dp[i][j+1][k-1])+N)/(i+j+k)

@lru_cache(maxsize=None)
def h(i,j,k):
  if (i,j,k) == (0,0,0):
    return 0
  return ((i*h(i-1,j  ,k  ) if i else 0)+
          (j*h(i+1,j-1,k  ) if j else 0)+
          (k*h(i  ,j+1,k-1) if k else 0)+
          N)/(i+j+k)
print(h(A,B,C))

### FIXED CODE ###

from collections import defaultdict
import sys
from functools import lru_cache
sys.setrecursionlimit(100000)
N = int(input())
 
counts = [0,0,0]
for a in map(int,input().split()):
  counts[a-1] += 1

A,B,C = counts


# dp[i][j][k] = 残り1個の皿がi枚、残り2個の皿がj枚、残り3個の皿がk枚のときの回数の期待値
# dp[i][j][k] = (i/N)(dp[i-1][j][k])+(j/N)(dp[i+1][j-1][k])+(k/N)(dp[i][j+1][k-1])+(N-i-j-k/N)(dp[i][j][k])+1
# dp[i][j][k] = (i(dp[i-1][j][k])+j(dp[i+1][j-1][k])+k(dp[i][j+1][k-1])+N)/(i+j+k)
dp = [[[None]*(C+1) for _ in range(B+C+1)] for _ in range(A+B+C+1)]
dp[0][0][0] = 0

for k in range(C+1):
  for j in range(B+C+1-k):
    for i in range(A+B+C+1-k-j):
      try:
        dp[i][j][k] =((i*dp[i-1][j][k] if i else 0)+
                      (j*dp[i+1][j-1][k] if j else 0)+
                      (k*dp[i][j+1][k-1] if k else 0)+
                      N)/(i+j+k)
      except ZeroDivisionError:
        pass

print(dp[A][B][C])
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
b = [num for num in a]
x = max(a)
for i in range(n) :
    if a[i] != x :
        print(x)
    else :
        b.remove(a[i])
        print(max(b))
        b.append(a[i])

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
x = max(a)
m = a.index(x)
a.remove(x)
y = max(a)
for i in range(n) :
    if i == m :
        print(y)
    else :
        print(x)
### BUGGY CODE ###

from itertools import groupby
import copy
def calc():
  s = 0
  for i in range(h):
    gr = groupby(g[i])
    j = 0
    for key,it in gr:
      if key==-1: continue
      l = len(list(it))
      if l >= K:
        for k in range(l):
          g[i][j+k] = -1
        # print("s", key, l, key*l)
        s += key*l
      j += l
      # print("j", j)

  return s

def flatten():
  for j in range(w):
    lst = []
    for i in range(h-1, -1, -1):
      if g[i][j] > 0:
        lst.append(g[i][j])

    lst += [-1] * (h - len(lst))

    for i in range(h-1, -1, -1):
      g[i][j] = lst[h-i-1]

h,w,K = map(int,input().split())
mat = []
for _ in range(h):
  mat.append([int(e) for e in list(input())])

res = 0
for i in range(h):
  for j in range(w):
    score = 0
    g = copy.deepcopy(mat)
    g[i][j] = -1
    time = 0
    flatten()
    while True:
      s = calc()
      if s > 0:
        score += pow(2, time) * s
      else:
        break
      flatten()
      time += 1
    res = max(res, score)

print(res)



### FIXED CODE ###

from itertools import groupby

def calc(time):
  t = 0
  for i in range(h):
    gr = groupby(g[i])
    lst = []
    p = 0
    for key,it in gr:
      j = len(list(it))
      lst.append([p,key,j])
      p += j
    for j in range(len(lst)):
      if lst[j][1] == -1:
        continue
      if lst[j][2] >= K:
        t += (2**time)*lst[j][1]*lst[j][2]
        for k in range(lst[j][0],lst[j][0]+lst[j][2]):
          g[i][k] = 0

  return t

def flatten():
  for j in range(w):
    lst = []
    for i in range(h-1, -1, -1):
      if g[i][j] > 0:
        lst.append(g[i][j])

    lst += [-1] * (h - len(lst))

    for i in range(h-1, -1, -1):
      g[i][j] = lst[h-i-1]

h,w,K = map(int,input().split())
mat = [ [int(e) for e in list(input())] for _ in range(h) ]

res = 0
for i in range(h):
  for j in range(w):
    score = 0
    g = [ [ mat[n][m] for m in range(w) ] for n in range(h) ]
    g[i][j] = -1
    time = 0
    flatten()
    while True:
      s = calc(time)
      if s==0: break
      score += s
      flatten()
      time += 1
    res = max(res, score)

print(res)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

from collections import deque

n = int(input())
uvw = [list(map(int, input().split())) for _ in range(n-1)]
 
graph = [[] for _ in range(n)]
for i in range(n-1):
    graph[uvw[i][0]-1].append((uvw[i][1]-1, uvw[i][2]))
    graph[uvw[i][1]-1].append((uvw[i][0]-1, uvw[i][2]))
 
stack = deque([0])
visited = []
ans = [0]*n
while stack:
    node = stack.pop()
    visited.append(node)
    for child in graph[node]:
        if child[0] in visited:
            continue
        
        stack.append(child[0])
        if child[1]%2 == 0:
            ans[child[0]] = ans[node]
        else:
            ans[child[0]] = (ans[node]+1)%2
 
[print(ans[i]) for i in range(n)]

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

graph = [[] for _ in range(n)]
for i in range(n-1):
    graph[uvw[i][0]-1].append((uvw[i][1]-1, uvw[i][2]))
    graph[uvw[i][1]-1].append((uvw[i][0]-1, uvw[i][2]))

stack = [0]
ans = [-1]*n
ans[0] = 0
while stack:
    node = stack.pop()
    for child in graph[node]:
        if ans[child[0]]!=-1:
            continue
        
        stack.append(child[0])
        if child[1]%2 == 0:
            ans[child[0]] = ans[node]
        else:
            ans[child[0]] = (ans[node]+1)%2

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

import sys
input = sys.stdin.readline

class UnionFind():
    def __init__(self,n):
        self.n = n
        self.parents = [-1] * n

    def find(self,x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]    

def main():
    N, K, L = map(int, input().split())
    road = UnionFind(N)
    train = UnionFind(N)
    for _ in range(K):
        p, q = map(int, input().split())
        p -= 1
        q -= 1
        road.union(p,q)
    for _ in range(L):
        r, s = map(int, input().split())
        r -= 1
        s -= 1
        train.union(r,s)

    ans = [0] * N
    for i in range(N):
        a = set(road.members(i))
        b = set(train.members(i))
        ans[i] = len(list(a & b))

    print(*ans)




if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline

class UnionFind():
    def __init__(self,n):
        self.n = n
        self.parents = [-1] * n

    def find(self,x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]    

def main():
    N, K, L = map(int, input().split())
    road = UnionFind(N)
    train = UnionFind(N)
    for _ in range(K):
        p, q = map(int, input().split())
        p -= 1
        q -= 1
        road.union(p,q)
    for _ in range(L):
        r, s = map(int, input().split())
        r -= 1
        s -= 1
        train.union(r,s)

    d = defaultdict(int)
    for i in range(N):
        a = road.find(i)
        b = train.find(i)
        d[(a,b)] += 1

    ans = [0] * N

    for i in range(N):
        a = road.find(i)
        b = train.find(i)
        ans[i] = d[(a,b)]
    print(*ans)




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

q = int(input())
lr = []
for i in range(q):
    lr.append(list(map(int, input().split())))


def is_prime(num):
    i = 2
    while i ** 2 <= num:
        if num % i == 0:
            return False
        i += 1
    return True


primes = []
for i in range(2, 10 ** 5 + 1):
    if is_prime(i):
        primes.append(i)

like_2017 = []
count = [0 for _ in range(10 ** 5)]
for i in range(len(primes)):
    if primes[i] * 2 - 1 in primes:
        like = 2 * primes[i] - 1
        count[like] += 1
for i in range(len(count) - 1):
    count[i + 1] += count[i]
for i in range(q):
    print(count[lr[i][1]] - count[lr[i][0] - 1])


### FIXED CODE ###

q = int(input())
lr = []
for i in range(q):
    lr.append(list(map(int, input().split())))


def binarySearch(alist, item):
    first = 0
    last = len(alist) - 1
    found = False
    while first <= last and not found:
        midpoint = (first + last) // 2
        if alist[midpoint] == item:
            found = True
        else:
            if item < alist[midpoint]:
                last = midpoint - 1
            else:
                first = midpoint + 1
    return found


def is_prime(num):
    i = 2
    while i ** 2 <= num:
        if num % i == 0:
            return False
        i += 1
    return True


primes = []
for i in range(2, 10 ** 5 + 1):
    if is_prime(i):
        primes.append(i)

like_2017 = []
for i in range(len(primes)):
    if binarySearch(primes, primes[i] * 2 - 1):
        like_2017.append(2 * primes[i] - 1)

count = [0 for _ in range(10 ** 5)]
for like in like_2017:
    count[like] += 1
for i in range(len(count) - 1):
    count[i + 1] += count[i]
for i in range(q):
    print(count[lr[i][1]] - count[lr[i][0]-1])
### BUGGY CODE ###

from collections import deque

n = int(input())
visit = [-1 for _ in range(n+1)]
tree = [[-1 for _ in range(n+1)] for __ in range(n+1)]
friends = [[] for _ in range(n+1)]
for i in range(n-1):
    u, v, w = map(int, input().split())
    tree[u][v] = w
    tree[v][u] = w
    friends[u].append(v)
    friends[v].append(u)

q = deque([1])
visit[1] = 0
while q:
    position = q.popleft()
    for i in friends[position]:
        if visit[i] < 0:
            visit[i] = visit[position] + tree[position][i]
            q.append(i)

for i in visit[1:]:
    print(i%2)

### FIXED CODE ###

from collections import deque

n = int(input())
visit = [-1 for _ in range(n+1)]
friends = [[] for _ in range(n+1)]
for i in range(n-1):
    u, v, w = map(int, input().split())
    friends[u].append([v, w])
    friends[v].append([u, w])

q = deque([1])
visit[1] = 0
while q:
    position = q.popleft()
    for i, cost in friends[position]:
        if visit[i] < 0:
            visit[i] = visit[position] + cost
            q.append(i)

for i in visit[1:]:
    print(i%2)
### BUGGY CODE ###

import sys
n,k = map(int,input().split())
l = list(map(int, input().split()))
dp = [sys.maxsize] *n
dp[0] = 0
for i in range(n):
    for j in range(i+1,i+k+1):
        if(j<n):
            dp[j]=min(dp[j],dp[i]+abs(l[i]-l[j]))
print(dp[n-1])

### FIXED CODE ###

import sys
n,k = map(int,input().split())
l = list(map(int, input().split()))
dp = [sys.maxsize] *n
dp[0] = 0
for i in range(n):
    for j in range(i+1,i+k+1):
        if(j<n):
            dp[j]=min(dp[j],dp[i]+abs(l[i]-l[j]))
print(dp[n-1])
### BUGGY CODE ###

Figures = []
N = int(input())
for _ in range(N):
  A = input()
  if A in Figures:
    Figures.remove(A)
  else:
    Figures.append(A)
Answer = len(Figures)
print(Answer)

### FIXED CODE ###

dic = {}
N = int(input())
for _ in range(N):
  x = int(input())
  if x in dic:
    dic[x] += 1
  else:
    dic[x] = 1
counter = 0
for i in dic.keys():
  if dic[i] %2 == 1:
    counter +=1
print(counter)
### BUGGY CODE ###

n = int(input())
s = input()
cnt_l = []
for i in range(n):
  cnt = 0
  if i != 0:
    for j in s[:i]:
      if j == "W":
        cnt += 1  
  if i != n - 1:
    for k in s[i+1:]:
      if k == "E":
        cnt += 1
  cnt_l.append(cnt) 
print(min(cnt_l))

### FIXED CODE ###

import numpy
n = int(input())
s = input()
Ws = [0] + [1 if i == "W" else 0 for i in s]
Ws_sum = list(numpy.cumsum(Ws))
cnt_l = []
for i in range(n):
    cnt_l.append(Ws_sum[i]+n-i-1-Ws_sum[-1]+Ws_sum[i+1])
print(min(cnt_l))
### BUGGY CODE ###

def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N = int(input())
    b = list(map(int, input().split()))
  else:
    # b = [1,2,1]
    # b = [2,2]
    b = [1,1,1,2,2,1,2,3,2]
    N = len(b)
   
  if check(b) != True:
    print(-1)
    
def check(B):
  # if 'get_ipython' in globals(): print(B)
  lenB = len(B)
  if lenB == 0 :
    return True
  for i in reversed(range(lenB)):
    if B[i] == i+1:
      if check(B[:i]+B[(i+1):]) == True:
        print(B[i])
        return True
        break
    
main()

### FIXED CODE ###

import sys

def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    N = int(input())
    b = [int(i) for i in input().split()] 
  else:
    # b = [1,2,1]
    # b = [2,2]
    b = [1,1,1,2,2,1,2,3,2]
    N = len(b)

  ans = []
  while True:
    for i in range(N-1,-1,-1):
      if b[i] == i+1:
        ans.append(i+1)
        del b[i]
        N = N -1
        break
      if i == 0:
        print(-1)
        sys.exit()
    if N == 0:
      break

  for i in reversed(ans):
    print(i)
    
main()
### BUGGY CODE ###

h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I:=h*w]*I
m+=d,
q=[a:=~w+a*w+b]
d[a]=1
for s in q:
 for x in 0,1,2,3:
  for z in range(k):
   y=~z,0,z+1,0;i,j=s//w+y[x],s%w+y[x^1];t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

### FIXED CODE ###

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)
### BUGGY CODE ###

n, m =  map(int, input().split())
py = [map(int, input().split()) for _ in range(m)]
p, y = [list(i) for i in zip(*py)]
pre = {}
for i in range(m):
    if p[i] not in pre.keys():
        pre[p[i]] = []
    pre[p[i]].append(y[i])
for i in pre.keys():
    pre[i].sort()
for i in range(m):
    num = str(p[i]*(10**6)+(pre[p[i]].index(y[i])+1)).zfill(12)
    print(num)

### FIXED CODE ###

import sys
n,m = map(int, sys.stdin.readline().rstrip("\n").split())
city = {}
yton = {}
for i in range(m):
    p,y = map(int, sys.stdin.readline().rstrip("\n").split())
    if p not in city.keys():
        city[p] = []
        city[p].append(y)
        yton[y] = i
    else:
        city[p].append(y)
        yton[y] = i
ans = [None]*m
for p in city.keys():
    city[p].sort()
    for i,y in enumerate(city[p]):
        ans[yton[y]] = str(p*(10**6)+i+1).zfill(12)
print(*ans, sep = '\n')