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

import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

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

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

def DFS(G, W, Wlist, visit, node):
	for i in G.graph[node]:
		if visit[i] != "Yes":
			visit[i] = "Yes"
			DFS(G, W, Wlist, visit, i)
			W[node] += W[i]
			Wlist[node].append(W[i])

#処理内容
def main():
	#入力
	N = int(input())
	G = Graph()
	for i in range(N - 1):
		a, b = getlist()
		a -= 1; b -= 1
		G.add_edge(a, b)
		G.add_edge(b, a)

	#DFS
	W = [1] * N
	Wlist = [[0] for i in range(N)]
	visit = ["No"] * N
	visit[0] = "Yes"
	DFS(G, W, Wlist, visit, 0)
	# print(W)
	# print(Wlist)
	for i in range(N):
		Wlist[i].append(N - 1 - sum(Wlist[i]))

	# print(Wlist)
	ans_up = 0
	pow2 = pow(2, N - 1, con)
	for i in range(N):
		ans_up += pow2 - 1
		for j in Wlist[i]:
			ans_up -= pow(2, j, con) - 1

	# print(ans_up)

	ans = ans_up * pow(pow2 * 2, con - 2, con)
	print(ans % con)

if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
from collections import deque
con = 10 ** 9 + 7; INF = float("inf")

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

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

def DFS(G, W, Wlist, visit, node):
	for i in G.graph[node]:
		if visit[i] == 0:
			visit[i] = 1
			DFS(G, W, Wlist, visit, i)
			W[node] += W[i]
			Wlist.append(W[i])

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = deque(); self.Q.append(s)
		self.dist = [INF] * N; self.dist[s] = 0
		self.prev = [None] * N; self.prev[s] = -1
		self.order = []
		while self.Q:
			v = self.Q.popleft()
			self.order.append(v)
			for i in self.g[v]:
				if self.dist[i] == INF:
					self.dist[i] = self.dist[v] + 1
					self.prev[i] = v
					self.Q.append(i)


#処理内容
def main():
	#入力
	N = int(input())
	G = Graph()
	Nedge = [0] * N
	for i in range(N - 1):
		a, b = getlist()
		a -= 1; b -= 1
		G.add_edge(a, b)
		G.add_edge(b, a)
		Nedge[a] += 1; Nedge[b] += 1

	W = [1] * N
	#葉の場合の処理
	# for i in range(N):
	# 	if Nedge[i] == 1:
	# 		W[i] = 1

	BF = BFS(G, 0, N)

	for i in range(N - 1, 0, -1):
		v = BF.order[i]
		W[BF.prev[v]] += W[v]

	Wlist = []
	for i in range(N):
		for j in G.graph[i]:
			if j != BF.prev[i]:
				Wlist.append(W[j])
	for i in range(N):
		Wlist.append(N - W[i])

	pow2 = pow(2, N - 1, con)
	ans_up = N * (pow2 - 1)
	for i in Wlist:
		ans_up -= pow(2, i, con) - 1
		ans_up %= con

	ans = ans_up * pow(pow2 * 2, con - 2, con)
	print(ans % con)

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

n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
p = [pow(2, i, mod) for i in range(60)]
ans = 0
for i in range(60):
    c = 0
    for j in a:
        if (j >> i) & 1:
            c += 1
    ans += (c * (n - c) * p[i]) % mod
    ans %= mod
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
p = [pow(2, i, mod) for i in range(60)]
ans = 0
for i in range(60):
    c = 0
    for j in a:
        if (j >> i) & 1:
            c += 1
    ans += (c * (n - c) * p[i]) % mod
    ans %= mod
print(ans)
### BUGGY CODE ###

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

l=[0]*60
for i in A:
  for j in range(60):
    if i&(1<<j):l[j]+=1
ans=0
for i in range(60):
  ans+=l[i]*(N-l[i])*(1<<i)
  ans%=10**9+7
print(ans)

### FIXED CODE ###

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

l=[0]*60
for i in A:
  for j in range(60):
    if i&(1<<j):l[j]+=1
ans=0
for i in range(60):
  ans+=l[i]*(N-l[i])*(1<<i)
  ans%=10**9+7
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from heapq import heappush,heappop,heapify
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
X,Y=[0]*N,[0]*N
dx,dy=defaultdict(list),defaultdict(list)
for i in range(N):
    X[i],Y[i]=map(int,input().split())
    dx[X[i]].append(i)
    dy[Y[i]].append(i)
ux,uy=list(set(X)),list(set(Y))
ux.sort()
uy.sort()
uxi={x:i for i,x in enumerate(ux)}
uyi={y:i for i,y in enumerate(uy)}
edge=[[] for i in range(N)]
for i,(x,y) in enumerate(zip(X,Y)):
    for index in dx[x]+dy[y]:
        edge[i].append((0,index))
    if uxi[x]>=1:
        for index in dx[ux[uxi[x]-1]]:
            if index!=i:
                edge[i].append((abs(ux[uxi[x]-1]-x),index))
    if uxi[x]<len(ux)-1:
        for index in dx[ux[uxi[x]+1]]:
            if index!=i:
                edge[i].append((abs(ux[uxi[x]+1]-x),index))
    if uyi[y]>=1:
        for index in dy[uy[uyi[y]-1]]:
            if index!=i:
                edge[i].append((abs(uy[uyi[y]-1]-y),index))
    if uyi[y]<len(uy)-1:
        for index in dy[uy[uyi[y]+1]]:
            if index!=i:
                edge[i].append((abs(uy[uyi[y]+1]-y),index))

def prim(n,edges):
    used=[False]*n
    used[0]=True
    edgelist=[]
    for edge in edges[0]:
        heappush(edgelist,edge)
    cost=0
    while edgelist:
        minedge=heappop(edgelist)
        if used[minedge[1]]:
            continue
        v=minedge[1]
        used[v]=True
        for edge in edges[v]:
            if not used[edge[1]]:
                heappush(edgelist,edge)
        cost+=minedge[0]
    return cost

print(prim(N,edge))

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from heapq import heappush,heappop,heapify
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
X,Y=[],[]
for i in range(N):
    x,y=map(int,input().split())
    X.append((y,i))
    Y.append((x,i))
X.sort(key=lambda t:t[0])
Y.sort(key=lambda t:t[0])
edge=[[] for i in range(N)]
for i in range(N-1):
    edge[X[i][1]].append((abs(X[i][0]-X[i+1][0]),X[i+1][1]))
    edge[X[i+1][1]].append((abs(X[i][0]-X[i+1][0]),X[i][1]))
    edge[Y[i][1]].append((abs(Y[i][0]-Y[i+1][0]),Y[i+1][1]))
    edge[Y[i+1][1]].append((abs(Y[i][0]-Y[i+1][0]),Y[i][1]))

def prim(n,edges):
    used=[False]*n
    used[0]=True
    edgelist=[]
    for edge in edges[0]:
        heappush(edgelist,edge)
    cost=0
    while edgelist:
        minedge=heappop(edgelist)
        if used[minedge[1]]:
            continue
        v=minedge[1]
        used[v]=True
        for edge in edges[v]:
            if not used[edge[1]]:
                heappush(edgelist,edge)
        cost+=minedge[0]
    return cost

print(prim(N,edge))
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
    ai = int(input())
    a.append(ai)
max_a = max(a)
for i in a:
    if i != max_a:
        print(max_a)
    else:
        print(sorted(a)[-2])

### FIXED CODE ###

n = int(input())
max_a = 0
next_a = 0
max_loc = 0
for i in range(n):
    ai = int(input())
    if ai > max_a:
        max_a =ai
        max_loc = i
    elif ai > next_a:
        next_a = ai
if next_a == 0:
    for i in range(n):
        print(max_a)
else:
    for i in range(max_loc):
        print(max_a)
    print(next_a)
    for i in range(n-max_loc-1):
        print(max_a)
### BUGGY CODE ###

import numpy as np
n=input()
data=list(map(int,input().split()))
is_i=0
num=sorted(data)
count=num[1]
if 2<len(data):
    while num[0]<count and any([x%count!=0 for x in num[1::]]):
        count=int(count/2)
for i in range(count+1)[::-1]:
    is_i=0
    if all([x%i==0 for x in data]):
        print(i)
        break
    else:
        for j in range(len(data)):
            if data[j]%i!=0:
                is_i+=1
        if is_i==1:
            print(i)
            break

### FIXED CODE ###

from fractions import gcd
import numpy as np
n=int(input())
data=list(map(int,input().split()))
left=np.zeros(n+1,dtype=np.int)
right=np.zeros(n+1,dtype=np.int)
kotae=1
for i in range(n):
    left[i+1]=gcd(left[i],data[i])
    right[n-i-1]=gcd(right[n-i],data[n-i-1])
for j in range(n):
    num=gcd(left[j],right[j+1])
    kotae=max(num,kotae)
print(kotae)
### BUGGY CODE ###

n,m = map(int,input().split())

for i in range(m//n,0,-1):
    if (m-n*i)%i == 0:
        print(i)
        exit()

### FIXED CODE ###

import bisect
n,m = map(int,input().split())
l = []
for i in range(1,int(m**0.5)+1):
    if m%i == 0:
        l.append(i)
        l.append(m//i)

l.sort()
for i in range(len(l)-1,-1,-1):
    if l[i] <= m//n:
        print(l[i])
        exit()
### BUGGY CODE ###

import numpy as np
import collections
N, K = map(int, raw_input().split())
P_list = list()
for i in range(N):
    P_list.append(raw_input()[0])
    C_list = collections.Counter(P_list).values()

# clean
C_vec = np.array(C_list)

while True:
    m = int(C_vec.sum() / K)
    C_vec = np.minimum(C_vec, m)
    m_next = int(C_vec.sum() / K)
    if m_next == m:
        break
    else:
        m = m_next

print m

### FIXED CODE ###

import numpy as np
C_vec = np.zeros(26)
N, K = map(int, raw_input().split())

for i in range(N):
    C_vec[ord((raw_input()[0])) - ord('A')] += 1


while True:
    m = int(C_vec.sum() / K)
    C_vec = np.minimum(C_vec, m)
    m_next = int(C_vec.sum() / K)
    if m_next == m:
        break
    else:
        m = m_next

print m
### BUGGY CODE ###

def pow_mod(a, b, p):
    res = 1
    mul = a
    for i in range(len(bin(b)) - 2):
        if (1 << i) & b:
            res = (res * mul) % p
        mul = (mul ** 2) % p
    return res


def perm_mod(n, r, p):
    res = 1
    for i in range(r):
        res = (res * (n - i)) % p
    return res


def comb_mod(n, r, p, factorial=None, invert_factorial=None):
    if factorial and invert_factorial:
        return (factorial[n] * invert_factorial[r] * invert_factorial[n - r]) % p

    r = min(r, n - r)
    return (perm_mod(n, r, p) * pow_mod(perm_mod(r, r, p), p - 2, p)) % p


def main():
    p = 10 ** 9 + 7
    n, k = map(int, input().split())

    factorial = [1] * (n + 1)
    for i in range(1, n + 1):
        factorial[i] = (factorial[i - 1] * i) % p

    invert_factorial = [pow_mod(x, p - 2, p) for x in factorial]

    res = 0
    for i in range(min(k + 1, n)):
        res = (res + comb_mod(n, i, p, factorial, invert_factorial)
               * comb_mod(n - 1, i, p, factorial, invert_factorial)) % p
    print(res)


main()


### FIXED CODE ###

def pow_mod(a, b, p):
    res = 1
    mul = a
    for i in range(len(bin(b)) - 2):
        if (1 << i) & b:
            res = (res * mul) % p
        mul = (mul ** 2) % p
    return res


def comb_mod(n, r, p, factorial=None, invert_factorial=None):
    return (factorial[n] * invert_factorial[r] * invert_factorial[n - r]) % p


def main():
    p = 10 ** 9 + 7
    n, k = map(int, input().split())

    factorial = [1] * (n + 1)
    for i in range(1, n + 1):
        factorial[i] = (factorial[i - 1] * i) % p

    invert_factorial = [0] * (n + 1)
    invert_factorial[n] = pow_mod(factorial[n], p - 2, p)
    for i in range(n - 1, -1, -1):
        invert_factorial[i] = (invert_factorial[i + 1] * (i + 1)) % p

    res = 0
    for i in range(min(k + 1, n)):
        res = (res + comb_mod(n, i, p, factorial, invert_factorial)
               * comb_mod(n - 1, i, p, factorial, invert_factorial)) % p
    print(res)


main()
### BUGGY CODE ###

# n: 参加者人数
# k: 初期ポイント
# q: ラウント回数
n, k, q = map(int, input().split())
data = [ int(input()) for _ in range(q) ]

table = [k] * n

for winnner in data:
    for j in range(n):
        table[j] -= 1
    
    table[winnner - 1] += 1

for k in range(n):
    if table[k] > 0:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

# n: 参加者人数
# k: 初期ポイント
# q: ラウント回数
n, k, q = map(int, input().split())
data = [ int(input()) for _ in range(q) ]

table = [k] * n

for winnner in data:    
    table[winnner - 1] += 1

for j in range(n):
    table[j] -= q

for k in range(n):
    if table[k] > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import fractions
 
N = int(input())
A = list(map(int, input().split()))
 
l = 1
for a in A:
    l = (l * a) // fractions.gcd(l, a)
 
ans = 0
for a in A:
    ans += l // a
 
print(ans % (10**9 + 7))

### FIXED CODE ###

import fractions
 
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
 
N = int(input())
A = list(map(int, input().split()))
 
l = 1
for a in A:
    l = lcm(l, a)
 
ans = 0
for a in A:
    ans += l // a
 
print(ans % (10**9 + 7))
### BUGGY CODE ###

def solve():
  h,w = (int(i) for i in input().split())
  maze = [input() for _ in range(h)]
  visit = [[False]*w for i in range(h)]
  count = h*w
  ans = 0
  
  white = []
  for i in range(h):
    for j in range(w):
      if maze[i][j] == "#":
        white.append((i,j))
        count -= 1
  d = [(1,0),(0,1),(-1,0),(0,-1)]
  while count > 0:
   ans += 1
   newwhite = []
   while white:
      x,y = white.pop(0)
      for dx,dy in d:
        nx,ny = x+dx,y+dy
        if nx < 0 or nx >= h or ny < 0 or ny >=w :
         continue  
        if maze[nx][ny] == ".":
          count -= 1
          str_list = list(maze[nx])
          str_list[ny] = "#"
          maze[nx] = "".join(str_list)          
          newwhite.append((nx,ny))
   white = newwhite
    
  print(ans)
solve()


### FIXED CODE ###


from collections import deque
def solve():
  h,w = (int(i) for i in input().split())
  maze = ["0"*(w+2)]
  for i in range(h):
    maze.append("0"+input()+"0")
  maze.append("0"*(w+2))
  black = deque([])
  count = 0
  visit = [[False]*(w+2) for _ in range(h+2)]
  
  for i in range(h+2):
    for j in range(w+2):
      if maze[i][j] == "#":
        black.append((0,i,j)) #move,h,w

  d = [(0,1),(1,0),(-1,0),(0,-1)]
  ans = 0
  
  while count != h*w:
    move,y,x = black.popleft()
    #print(move,y,x)
    if visit[y][x]:
      continue
    else:
      visit[y][x] = True
      count += 1
      for dy,dx in d:
        ny,nx = y+dy,x+dx
        if visit[ny][nx]:
          continue
        elif maze[ny][nx] ==".":
          black.append((move+1,ny,nx))
  print(move)
          

    
solve()
### BUGGY CODE ###

import sys
import bisect
n = int(sys.stdin.readline().strip())
s = list(sys.stdin.readline().strip())
alpha = "abcdefghijklmnopqrstuvwxyz"
dict = {i:[] for i in alpha}
for i, _s in enumerate(s):
    dict[_s].append(i)
q = int(sys.stdin.readline().strip())
for i in range(q):
    type, first, last = [i for i in sys.stdin.readline().split()]
    if type == "2":
        first = int(first)
        last = int(last)
        first -= 1
        last -= 1
        cnt = 0
        for a in alpha:
            ls = dict[a]
            if bisect.bisect_left(ls, first) != bisect.bisect_right(ls, last):
                cnt += 1
        print(cnt)
    else:
        first = int(first)
        first -= 1
        dict[s[first]].pop(bisect.bisect_left(dict[s[first]], first))
        s[first] = last
        bisect.insort_left(dict[last], first)

### FIXED CODE ###

import sys
import bisect
n = int(sys.stdin.readline().strip())
s = list(sys.stdin.readline().strip())
alpha = "abcdefghijklmnopqrstuvwxyz"
dict = {i:[] for i in alpha}
for i, _s in enumerate(s):
    dict[_s].append(i)
q = int(sys.stdin.readline().strip())
for i in range(q):
    type, first, last = [i for i in sys.stdin.readline().split()]
    if type == "2":
        first = int(first)
        last = int(last)
        first -= 1
        last -= 1
        cnt = 0
        for ls in dict.values():
            if bisect.bisect_left(ls, first) != bisect.bisect_right(ls, last):
                cnt += 1
        print(cnt)
    else:
        first = int(first)
        first -= 1
        _s = s[first]
        if _s == last:
            continue
        del dict[_s][(bisect.bisect_left(dict[_s], first))]
        s[first] = last
        bisect.insort_left(dict[last], first)
### BUGGY CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = int(input())
print(0)
l = input()
r = l
if L == "Vacant":
    exit()

ng = 0
ok = n
while True:
    mid = (ng + ok) // 2
    print(mid)
    q = input()
    if q == "Vacant":
        exit()
    if (q == l) ^ ((mid - ng)%2 == 1):
        ng = mid
        l = q
    else:
        ok = m
        r = q

### FIXED CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = int(input())
print(0)
l = input()
r = l
if l == "Vacant":
    exit()

ng,ok = 0,n
while True:
    mid = (ng + ok) // 2
    print(mid)
    q = input()
    if q == "Vacant":
        exit()
    if (q == l) ^ ((mid - ng)%2 == 1):
        ng = mid
        l = q
    else:
        ok = mid
        r = q
### BUGGY CODE ###

from copy import *
from sys import *
from math import *
import queue
from collections import defaultdict,Counter,deque

setrecursionlimit(1000000)

def main():
	n,m = map(int,input().split())
	ab = [list(map(int,input().split())) for _ in range(m)]
	b = {}
	for i in ab:
		try:
			b[i[0]].append(i[1])
		except:
			b[i[0]] = [i[1]]
		try:
			b[i[1]].append(i[0])
		except:
			b[i[1]] = [i[0]]
	ab = deepcopy(b)
	for i in ab[1]:
		if(n in ab[i]):
			print('POSSIBLE')
			exit()
	print('IMPOSSIBLE')

def zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(m,n):
	x = max(m,n)
	y = min(m,n)
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	return y

class Queue():
	#競プロ用のQueue
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)

class Stack():
	#怯プロ用のStack
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)

main()


### FIXED CODE ###

import copy
import sys
import math

def main():
	n,m = map(int,input().split())
	ab = [list(map(int,input().split())) for _ in range(m)]
	b = {}
	for i in ab:
		try:
			b[i[0]].append(i[1])
		except:
			b[i[0]] = [i[1]]
		try:
			b[i[1]].append(i[0])
		except:
			b[i[1]] = [i[0]]
	ab = copy.deepcopy(b)
	for i in ab[1]:
		if(n in ab[i]):
			print('POSSIBLE')
			sys.exit()
	print('IMPOSSIBLE')


def listtodict(a):
	b = {}
	for i in a:
		try:
			b[i] += 1
		except:
			b[i] = 1
	return b

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

main()
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
ans=[]
for i in range(1,len(l)+1):
    ans.append(l.index(i)+1)
print (" ".join(map(str,ans)))

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
ans=[None]*n
i=1
for index in l:
  ans[index-1]=str(i)
  i+=1
print (" ".join(ans))
### BUGGY CODE ###

#!/usr/bin/env python3

N, K = list(map(int, input().split()))
h_list = list(map(int, input().split()))
dp_list = [float("inf")] * N
dp_list[0] = 0

for i in range(1, N):
    # i番目の足場に飛ぶまでの最適解

    for j in range(i - K, i + 1):
        # j番目の足場から飛ぶ
        if j < 0:
            continue

        # j番目の足場までの最適コスト
        cum_cost = dp_list[j]

        # j番目の足場から飛んだ場合のコスト
        cost = dp_list[j] + abs(h_list[j] - h_list[i])

        # 最適コストで更新
        dp_list[i] = min(dp_list[i], cost)

ans = dp_list[-1]
print(ans)


### FIXED CODE ###

N, K = list(map(int, input().split()))
h_list = list(map(int, input().split()))
dp_list = [float("inf")] * N
dp_list[0] = 0

for i in range(1, N):
    # j番目の足場からi番目の足場に飛ぶ

    for j in range(max(i - K, 0), i + 1):

        # j番目の足場までの最適コスト
        cum_cost = dp_list[j]

        # j番目の足場から飛んだ場合のコスト
        cost = dp_list[j] + abs(h_list[j] - h_list[i])

        # 最適コストで更新
        dp_list[i] = min(dp_list[i], cost)

ans = dp_list[-1]
print(ans)
### BUGGY CODE ###

import numpy as np
n,t = map(int,input().split())
ab = [list(map(int, input().split())) for i in range(n)]
ab.sort()
dp = np.array([[0 for i in range(t+1)]for j in range(n+1)])
for i in range(n):
    ti,vi = ab[i]
    for j in range(t+1):
        if j + ti <= t:
            dp[i+1][j+ti] = max(dp[i+1][j+ti],dp[i][j]+vi)
        dp[i+1][j] = max(dp[i][j],dp[i+1][j])
ma = 0
for i in range(n):
    ma = max(ma,dp[i][t-1]+ab[i][1])
print(ma)

### FIXED CODE ###

N, W = map(int, input().split())
items = sorted([list(map(int, input().split())) for i in range(N)])

dp = [[0] * (W + 1) for i in range(N + 1)]

# dpテーブルを埋める
for i in range(N):
    wi, vi = items[i]
    for j in range(W + 1):
        if j + wi <= W:
            dp[i + 1][j + wi] = max(dp[i + 1][j + wi], dp[i][j] + vi)
        dp[i + 1][j] = max(dp[i][j], dp[i + 1][j])


ans = 0
# 最後に入れる商品は、残り容量１の時に入れるとしてしまってよい
for i, (wi, vi) in enumerate(items):
    ans = max(ans, dp[i][W - 1] + vi)

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

K, N = map(int, input().rstrip().split())
dist_list = list(map(int, input().rstrip().split()))

result = 0
for i, v in enumerate(dist_list):
  offset = 1
  total = 0
  while offset < N:
    now_pos = dist_list[((i + offset - 1) % N)]
    next_pos = dist_list[((i + offset) % N)]
    if next_pos < now_pos:
      next_pos += K
    total += next_pos - now_pos
    offset += 1

  if (result == 0 or result > total):
    result = total

print(result)


### FIXED CODE ###

K, N = map(int, input().rstrip().split())
dist_list = list(map(int, input().rstrip().split()))

maxdist = 0
for i in range(N - 1):
  dist = dist_list[i + 1] - dist_list[i]
  maxdist = max(maxdist, dist)
else:
  dist = (dist_list[0] + K) - dist_list[-1]
  maxdist = max(maxdist, dist)

print(K - maxdist)
### BUGGY CODE ###

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

p_list = []
y_list = []
shi_map = {}

for i in range(M):
    p, y = map(int, input().split())
    p_list.append(p)
    y_list.append(y)
    if p in shi_map:
        tmp = shi_map[p]
        tmp.append(y)
        tmp.sort()
        shi_map[p] = tmp

    else:
        shi_map[p] = [y]


for i in range(M):
    p = p_list[i]
    y = y_list[i]
    j = shi_map[p].index(y)
    p_str = str(p).zfill(6)
    j_str = str(j+1).zfill(6)
    print(p_str + j_str)



### FIXED CODE ###

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

shi_map = []

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

shi_map = sorted(shi_map, key=lambda x: (x[1], x[2]))

result = {}
shi_count = {}
for i, p, y in shi_map:

    if p in shi_count:
        c = shi_count[p]
        count = c + 1
        shi_count[p] = count
    else:
        shi_count[p] = 1
        count = 1
    result[i] = [p, count]
result = list(sorted(result.items(), key=lambda x: x[0]))

for i, p in result:

    p2 = str(p[0]).zfill(6)

    y = str(p[1]).zfill(6)
    r = p2+y
    print(r)