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

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

def main():
    h, w, d = map(int, input().split())

    num = [0] * (h * w)
    for i in range(h):
        a = list(map(int, input().split()))
        for j in range(w):
            num[a[j] - 1] = (i, j)

    ans = []
    q = int(input())
    for _ in range(q):
        # s = answer
        s = 0
        l, r = map(int, input().split())
        l -= 1
        r -= 1
        for i in range(l, r, d):
            v, w = num[i]
            x, y = num[i+d]
            s += abs(v-x) + abs(w-y)
        ans.append(s)

    for i in ans:
        print(i)

main()

### FIXED CODE ###

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

def main():
    h, w, d = map(int, input().split())

    x = [0] * (h*w)
    y = x.copy()
    for i in range(h):
        a = list(map(int, input().split()))
        for j in range(w):
            x[a[j] - 1] = i
            y[a[j] - 1] = j

    # 累積和
    cost = [[0] for _ in range(d)]
    for i in range(d, h*w):
        cost[i%d].append(cost[i%d][-1] + abs(x[i]-x[i-d]) + abs(y[i]-y[i-d]))

    ans = []
    q = int(input())
    for _ in range(q):
        l, r = map(int, input().split())
        l -= 1
        r -= 1
        ans.append(cost[r%d][r//d] - cost[l%d][l//d])

    for i in ans:
        print(i)

main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

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

dp1 = [0] * (N+1)
dp2 = [0] * (N+1)
parents = [-1] * (N+1)
leaf_nodes = []

def solve1(node, parent):
  global dp1
  global parents
  global leaf_nodes
  parents[node] = parent
  if dp1[node] > 0:
    return dp1[node]
  else:
    children = tree[node]
    t = 1
    for child in children:
      if child == parent:
        continue
      
      t *= (solve1(child, node) + 1)
      t %= M
    
    if t == 1:
      leaf_nodes.append(node)
    
    dp1[node] = t
    return t


def solve2(node):
  global dp2
  global parents
  parent = parents[node]
  if dp2[node] > 0:
    return dp2[node]
  else:
    children = tree[node]
    t = 1
    for child in children:
      if child == parent:
        t *= (solve2(parent)//(dp1[node] + 1) + 1)
      else:
        t *= (dp1[child] + 1)
    
    dp2[node] = t
    return t
  

_ = solve1(1, 0)
for leaf in leaf_nodes:
  _ = solve2(leaf)


for ans in dp2[1:]:
  print(ans%M)

### FIXED CODE ###

# 参考 -> https://atcoder.jp/contests/dp/submissions/8271798

import itertools
import sys
input = sys.stdin.readline

N, MOD = map(int, input().split())
XY = [list(map(int, input().split())) for i in range(N-1)]
prod = lambda x, y: x*y%MOD

tree = [[] for i in range(N)]
for x, y in XY:
  tree[x-1].append(y-1)
  tree[y-1].append(x-1)

root = 0
parent = [-1] * (N+1)
order = []
stack = [root]
while stack:
  node = stack.pop()
  order.append(node)
  for child in tree[node]:
    if child == parent[node]:
      continue
    parent[child] = node
    stack.append(child)

# dp_down[i] : 頂点iを黒く塗ったときの子側の塗り方
dp_down = [0] * N
for node in order[::-1]: # 葉から根に向かって伝搬させる
  res = 1
  for child in tree[node]:
    res *= dp_down[child] + 1
    res %= MOD
  dp_down[node] = res

# dp_up[i] : 頂点iを黒く塗ったときの親側の塗り方
dp_up = [1] * N
for node in order: # 根から葉に向かって伝搬させる
  par = parent[node]
  arr = [dp_down[c]+1 if c!=par else dp_up[node] for c in tree[node]]
  # それぞれの子(=c)について、自身を根とする下側の部分木を除いた積
  left = [1] + list(itertools.accumulate(arr, prod))[:-1]
  right = list(itertools.accumulate(reversed(arr), prod))[-2::-1] + [1]
  upper_cases = [l*r%MOD for l, r in zip(left, right)]
  for c, res in zip(tree[node], upper_cases):
    if c != par:
      dp_up[c] = res + 1 # (+1 : cより上側が全て白である場合を足し合わせる)

ans = [d*u%MOD for d, u in zip(dp_down, dp_up)]
print(*ans, sep='\n')
### BUGGY CODE ###

import math

n=int(input())
alist = [int(i) for i in input().split()]
alist=sorted(alist)

keta=math.floor(math.log2(max(alist[-1],1)))+1
zeros=[0]*keta
ones=[0]*keta

for al in alist:
    kaz2=bin(al)[2:]
    kaz2=(keta-len(kaz2))*'0'+kaz2
    #print(kaz2)
    for i in range(keta):
        if kaz2[i]=='1':
            ones[i]+=1
        else:
            zeros[i]+=1

answer=0
for i in range(keta):
    tas=ones[-i-1]*zeros[-i-1]
    tas*=((2**i)%(10**9+7))
    answer+=tas%(10**9+7)

print(answer%(10**9+7))

### FIXED CODE ###

import math

n=int(input())
alist = [int(i) for i in input().split()]
alist=sorted(alist)

keta=math.floor(math.log(max(alist[-1],1), 2))+1
zeros=[0]*keta
ones=[0]*keta

for al in alist:
    kaz2=bin(al)[2:]
    kaz2=(keta-len(kaz2))*'0'+kaz2
    for i in range(keta):
        if kaz2[i]=='1':
            ones[i]+=1
        else:
            zeros[i]+=1

answer=0
for i in range(keta):
    tas=ones[-i-1]*zeros[-i-1]
    tas*=((2**i)%(10**9+7))
    answer+=tas%(10**9+7)

print(answer%(10**9+7))
### BUGGY CODE ###

import sys

class binarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, key):
        z = Node(key)
        y = None
        x = self.root
        while x:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right

        if y is None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

    def printBT(self):
        print self.root.inorderTreeWalk()
        print self.root.preorderTreeWalk()

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

    def inorderTreeWalk(self):
        ret = ""
        if self.left:
            ret += self.left.inorderTreeWalk()
        ret += " " + str(self.key)
        if self.right:
            ret += self.right.inorderTreeWalk()

        return ret

    def preorderTreeWalk(self):
        ret = " " + str(self.key)
        if self.left:
            ret += self.left.preorderTreeWalk()
        if self.right:
            ret += self.right.preorderTreeWalk()

        return ret

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    del lines[0]

    bt = binarySearchTree()
    for line in lines:
        if line[0] == "i":
            t = line.split()
            bt.insert(int(t[1]))
        else:
            bt.printBT()

### FIXED CODE ###

import sys

class Node:
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None

def insert(z):
    global root
    y = None
    x = root
    while x is not None:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.parent = y
    if y is None:
        root = z
    elif z.key < y.key:
        y.left = z
    else:
        y.right = z

def inorderTreeWalk(node):
    global In
    if node:
        inorderTreeWalk(node.left)
        In.append(str(node.key))
        inorderTreeWalk(node.right)

def preorderTreeWalk(node):
    global Pre
    if node:
        Pre.append(str(node.key))
        preorderTreeWalk(node.left)
        preorderTreeWalk(node.right)

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    del lines[0]

    root = None
    for line in lines:
        if line[0] == "i":
            insert(Node(int(line.split()[1])))
        else:
            In = []
            Pre = []
            inorderTreeWalk(root)
            print " " + " ".join(map(str, In))
            preorderTreeWalk(root)
            print " " + " ".join(map(str, Pre))
### BUGGY CODE ###

import itertools
n=(int)(input())
moji = []
s=input()
for i in itertools.combinations(range(n), 3):
  #print(i)
  moji.append(s[i[0]] + s[i[1]] + s[i[2]])
  #print(moji)
print(len(list(set(moji))))

### FIXED CODE ###

import itertools
n=(int)(input())
moji = list('0123456789')
s=input()
count = 0

for i in itertools.product(moji, repeat=3):
  sousa = list(s)
  try:
    
    n1 = sousa.index(i[0])
    n2 = sousa[n1+1:].index(i[1])+n1+1
    n3 = sousa[n2+1:].index(i[2])+n2+1
    #print(sousa, sousa[n1+1:], sousa[n1+2:])
    count += 1
  except ValueError:
    continue
  #print(i)
  #moji.append(s[i[0]] + s[i[1]] + s[i[2]])
  #print(moji)
  
print(count)
### BUGGY CODE ###

import numpy as np

n = int(input())

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

a.sort()

if a[0] != 1:
    a = np.array(a)

    i = 0

    while i < len(a):
        b = a / a[i]

        a = a[(b != b.astype(int)) | (b == 1)]

        i += 1

    u, counts = np.unique(a, return_counts=True)

    print(sum(counts == 1))

elif (len(a) > 1) and (a[0] == a[1]):
    print(0)
else:
    print(1)

### FIXED CODE ###

n = int(input())

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

a.sort()

dp = [True] * (a[-1] + 1)

ans = 0

m = a[-1]

for i, x in enumerate(a[:-1]):
    if not a[i+1] == x and dp[x]:
        ans += 1
    for b in range(x, m + 1, x):
        dp[b] = False

if dp[a[-1]]:
    ans += 1

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

def resolve():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    for i in range(m):
        m = a[-1]
        disc = m // 2
        a.pop()
        a.append(disc)
        a.sort()
    print(sum(a))


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

import heapq


def resolve():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    query = []
    for i in range(n):
        heapq.heappush(query, -a[i])
    for i in range(m):
        nexta = -1 * heapq.heappop(query) // 2
        heapq.heappush(query, -nexta)
    print(-sum(query))


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

n = int(input())
a = map(int, input().split())
ans = 1
for i in a:
    ans *= i

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

### FIXED CODE ###

n = int(input())
a = map(int, input().split())
a = sorted(a, reverse=True)
ans = 1

if 0 in a:
    print(0)
    exit()

for i in a:
    ans *= i
    if ans > 10**18:
        print(-1)
        exit()

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

# -*- coding: utf-8 -*-
import sys

def main():
	N = int(input())
	tmp = input()
	lines = list(tmp)
	
	ans_min = 100001
	for i, val in enumerate(lines):
		ans = 0
		for j, vol in enumerate(lines):
			if i == j:
				continue
			if i < j and vol == "E":
				ans += 1
			if j < i and vol == "W":
				ans += 1
		if ans_min > ans:
			ans_min = ans
	
	print(ans_min)
		
if __name__ == "__main__":
	main()
	

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys

def main():
	N = int(input())
	tmp = input()
	lines = list(tmp)
	
	nisi = [0 for _ in range(N)]
	higasi = [0 for _ in range(N)]
	for i, val in enumerate(lines):
		if val == "W":
			if i != 0:
				nisi[i] = nisi[i-1] + 1
			else:
				nisi[i] = 1
		else:
			if i != 0:
				nisi[i] = nisi[i-1]
			else:
				nisi[i] = 0
		
	for i in range(N-1, -1, -1):
		if lines[i] == "E":
			if i < N-1:
				higasi[i] = higasi[i+1] + 1
			else:
				higasi[i] = 1
		else:
			if i < N-1:
				higasi[i] = higasi[i+1]
			else:
				higasi[i] = 0
	
	ans_min = -1
	for i, val in enumerate(lines):
		ans = 0
		ans1 = 0
		ans2 = 0
		if i < (N - 1):
			ans1 = higasi[i+1]
		if i > 0:
			ans2 = nisi[i-1]
		ans = ans1 + ans2
			
		if -1 == ans_min:
			ans_min = ans
		if ans_min > ans:
			ans_min = ans
	
	print(ans_min)
		
if __name__ == "__main__":
	main()
### BUGGY CODE ###

from bisect import bisect_left


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

dp1 = [[False] * (K + 1) for _ in range(N + 1)]

for i in range(N + 1):
    dp1[i][0] = True
for i in range(N):
    a = A[i]
    d = K if a >= K else a - 1
    for j in range(K, d, -1):
        dp1[i + 1][j] = dp1[i][j] | dp1[i][j - a]

dp2 = [[False] * (K + 1) for _ in range(N + 1)]
for i in range(N + 1):
    dp2[i][0] = True
for i in range(N):
    a = A[N - 1 - i]
    d = K if a >= K else a - 1
    for j in range(K, d, -1):
        dp2[i + 1][j] = dp2[i][j] | dp2[i][j - a]


def solve(i):
    d1 = []
    d2 = []
    n = A[i]
    for j, k in enumerate(dp1[i]):
        if k:
            d1.append(j)
    for j, k in enumerate(dp2[N - 1 - i]):
        if k:
            d2.append(j)
    for a in d1:
        l = bisect_left(d2, K - n - a)
        r = bisect_left(d2, K - a)
        if r - l >= 1:
            return True
    return False


# [ok, ng) - Maximum
# (ng, ok] - Minimum
# ok が 最終的な答え
ok = N
ng = -1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid


print(ok)


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()


    # [ok, ng) - Maximum
    # (ng, ok] - Minimum
    # ok が 最終的な答え
    ok = N
    ng = -1
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        n = mid
        dp = [0] * (K + 1)
        dp[0] = 1
        for i in range(N):
            a = A[i]
            if i == n or a >= K:
                continue
            for j in range(K, -1, -1):
                dp[min(K, j + a)] |= dp[j]
        rst = any(dp[k] for k in range(max(0, K - A[n]), K))
        if rst:
            ok = mid
        else:
            ng = mid
    print(ok)


main()
### BUGGY CODE ###

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]

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

for i in range(0, N):
    w = wv[i][0]
    v = wv[i][1]
    for j in range(W + 1):
        if j - w >= 0:
            dpp = dp[i][j - w] + v
            dp[i + 1][j] = max(dp[i + 1][j], dpp)    
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])

print(max(dp[-1]))

### FIXED CODE ###

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]

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

for i in range(1, N + 1):
    for j in range(W):
        w = wv[i - 1][0]
        v = wv[i - 1][1]
        if j + w <= W:
            dp[i][j + w] = max(dp[i][j + w], dp[i - 1][j] + v)
        dp[i][j] = max(dp[i][j], dp[i - 1][j])
        
print(max(dp[-1]))
### BUGGY CODE ###

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

if n < k:
    ans = min(abs(n-k), n)

else:    
    if n%k == 0:
        ans = 0
    else:
        for i in range(-k,k+1):
            if (i%k == n%k and i < 0):
                nega = -i
            elif (i%k == n%k and i >= 0):
                posi = i
        ans = (min(nega, posi))
print(ans)

### FIXED CODE ###

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

a = n%k
b = abs(a-k)
print(min(n,a,b))
### BUGGY CODE ###

import fractions

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

temp = n*m//fractions.gcd(n,m)
s_step = temp//n
t_step = temp//m

s_index = [1+s_step*i for i in range(n)]
t_index = [1+t_step*i for i in range(m)]

index = set(s_index)&set(t_index)

ans = temp

if len(index):
  for i in index:
    if t[t_index.index(i)] != s[s_index.index(i)]:
      ans = -1
    
print(ans)

### FIXED CODE ###

import fractions

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

gcd = fractions.gcd(n,m)

print(n*m//gcd if all([s[i*n//gcd]==t[i*m//gcd] for i in range(gcd)]) else -1)
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
ccc = list(map(int, input().split()))

aabb = [a + b for a in aaa for b in bbb]
aabb.sort(reverse=True)
aabb = aabb[:k]

aabbcc = [ab + c for ab in aabb for c in ccc]
aabbcc.sort(reverse=True)
aabbcc = aabbcc[:k]

print('\n'.join(map(str, aabbcc)))


### FIXED CODE ###

x, y, z, k = map(int, input().split())
aaa = sorted(map(int, input().split()), reverse=True)
bbb = sorted(map(int, input().split()), reverse=True)
ccc = sorted(map(int, input().split()), reverse=True)
ma, mb, mc = aaa[0], bbb[0], ccc[0]
cakes = [(ma - a, 0) for a in aaa[1:]]
cakes += [(mb - b, 1) for b in bbb[1:]]
cakes += [(mc - c, 2) for c in ccc[1:]]
cakes.sort()

buf = [[ma], [mb], [mc]]
ans = [ma + mb + mc]

for d, i in cakes:
    if i == 0:
        a = aaa[len(buf[i])]
        if len(ans) == k and ans[-1] >= a + mb + mc:
            break
        buf[i].append(a)
        ans.extend(a + b + c for b in buf[1] for c in buf[2])
        ans.sort(reverse=True)
        ans = ans[:k]
    elif i == 1:
        b = bbb[len(buf[i])]
        if len(ans) == k and ans[-1] >= ma + b + mc:
            break
        buf[i].append(b)
        ans.extend(a + b + c for a in buf[0] for c in buf[2])
        ans.sort(reverse=True)
        ans = ans[:k]
    else:
        c = ccc[len(buf[i])]
        if len(ans) == k and ans[-1] >= ma + mb + c:
            break
        buf[i].append(c)
        ans.extend(a + b + c for a in buf[0] for b in buf[1])
        ans.sort(reverse=True)
        ans = ans[:k]

print('\n'.join(map(str, ans)))
### BUGGY CODE ###

#ABC077C
N=int(input())
#大きい順に# 並べる
A=sorted(list(map(int,input().split())), reverse=True)
B=sorted(list(map(int,input().split())), reverse=True)
C=sorted(list(map(int,input().split())), reverse=True)
#あるBの下にいくつCが入るか数える
C_under_B=[0]*N     #i番目のBの下に入るCの数
for i in range(N):
    if i > 0:
        if B[i] == B[i-1]:
            C_under_B[i]=C_under_B[i-1]
            continue
    for j in range(N):
        if C[j]>B[i]:
            C_under_B[i]+=1
        else:       #C[j+1]>C[j]>B[i]なので検討を中止する
            break
#あるAの下にいくつBが入るか数える
B_under_A=[0]*N     #i番目のBの下に入るCの数
for i in range(N):
    if i > 0:
        if A[i] == A[i-1]:
            B_under_A[i]=B_under_A[i-1]
            continue
    for j in range(N):
        if B[j]>A[i]:
            B_under_A[i]+=1
        else:       #B[j+1]>B[j]>A[i]なので検討を中止する
            break
#あるAのもとに入るBのもとに入るCを数える
C_under_B_under_A=[0]*N
for i in range(N):
    C_under_B_under_A[i]=sum([C_under_B[j] for j in range(B_under_A[i])])
#出力
print(sum(C_under_B_under_A))


### FIXED CODE ###

#ABC077C 解説を見て自作
import bisect
N=int(input())
A=sorted(list(map(int,input().split())))
B=sorted(list(map(int,input().split())))
C=sorted(list(map(int,input().split())))
#あるBの下にいくつCが入るか数える
C_under_B=[0]*N     #i番目のBの下に入るCの数
for i in range(N):
    C_under_B[i]=N-bisect.bisect_right(C,B[i])
#あるBの上にいくつAが乗るか数える
A_on_B=[0]*N     #i番目のBの上に乗るAの数
for i in range(N):
    A_on_B[i]=bisect.bisect_left(A,B[i])
#あるBの上下におけるものを数えて出力
ans=0
for i in range(N):
    ans+=C_under_B[i]*A_on_B[i]
print(ans)
### BUGGY CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

def mapline(t = int):
    return map(t, sysread().split())
def mapread(t = int):
    return map(t, read().split())

def dfs(c, to, cols, max_counts, pre_col = 0):
    colors = set()
    colors.add(pre_col)
    for idx, n in to[c]:
        if cols[idx]:continue
        num = 1
        for i in range(num, max_counts+1):
            if not i in colors:
                num = i
                cols[idx] = i
                colors.add(i)
                dfs(n, to, cols, max_counts, i)
                break


def run():
    N = int(sysread())
    to = [[] for _ in range(N+1)]
    cols = [0] * (N-1)
    counts = [0 for i in range(N+1)]
    for i in range(N-1):
        a,b = mapline()
        to[a].append((i, b))
        to[b].append((i, a))
        counts[a] += 1
        counts[b] += 1

    max_counts = max(counts)
    print(max_counts)
    dfs(1, to, cols, max_counts)

    for c in cols:
        print(c)

    #print(a ^ b)
if __name__ == "__main__":
    run()


### FIXED CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 10 ** 9 + 7

def mapline(t = int):
    return map(t, sysread().split())
def mapread(t = int):
    return map(t, read().split())

def dfs(c, to, cols, max_counts, pre_col = 0):
    colors = set()
    colors.add(pre_col)
    num = 1
    for idx, n in to[c]:
        if cols[idx]:continue
        for i in range(num, max_counts+1):
            if not i in colors:
                num = i
                cols[idx] = i
                colors.add(i)
                dfs(n, to, cols, max_counts, i)
                break


def run():
    N = int(sysread())
    to = [[] for _ in range(N+1)]
    cols = [0] * (N-1)
    counts = [0 for i in range(N+1)]
    for i in range(N-1):
        a,b = mapline()
        to[a].append((i, b))
        to[b].append((i, a))
        counts[a] += 1
        counts[b] += 1

    max_counts = max(counts)
    print(max_counts)
    dfs(1, to, cols, max_counts)

    for c in cols:
        print(c)

    #print(a ^ b)
if __name__ == "__main__":
    run()
### BUGGY CODE ###

n,m = list(map(int,input().split()))
row_data = list()
pref_city = [[] for i in range(n)]

for i in range(m):
    p = list(map(int,input().split()))
    row_data.append(p)
    pref_city[p[0]-1].append(p[1])
    
for i,city in enumerate(row_data):
    pref_city[city[0]-1] = sorted(pref_city[city[0]-1])
    pref_id = "0" * 6 + str(city[0])
    city_id = "0" * 6 + str(pref_city[city[0]-1].index(city[1] ) + 1)
    print(pref_id[-6:] + city_id[-6:])

### FIXED CODE ###

n,m = list(map(int,input().split()))
tmp = [list(map(int,input().split())) for i in range(m)]
cities = [[] for i in range(n+1)]


for i,(pref,year) in enumerate(tmp):
    cities[pref].append([year,i])
    
answers = [""] * m
for i in range(n+1):
    for j,(year,index) in enumerate(sorted(cities[i])):
        answer = str(i).zfill(6) + str(j+1).zfill(6)
        answers[index] = answer
        
print(*answers,sep=("\n"))
### BUGGY CODE ###

n = int(input())
x = input()

num_of_1 = x.count("1")

first = int(x, 2)

def f(x):
    if x == 0:
        return 0
    return 1 + f(x % bin(x).count('1'))

if num_of_1 == 1:
    for i in range(n):
        if x[i] == '1':
            print(0)
        elif i == n-1:
            print(2)
        else:
            print(1)
    exit()

for i in range(n):
    ans = 0

    if x[i] == "0":
        temp_num_of_1 = num_of_1 + 1
        a = first + pow(2, n-i-1)
    else:
        temp_num_of_1 = num_of_1 - 1
        a = first - pow(2, n-i-1)

    a = a % temp_num_of_1

    ans += 1 + f(a)

    print(ans)

### FIXED CODE ###

n = int(input())
x = input()

num_of_1 = x.count("1")

first = int(x, 2)

def f(x):
    if x == 0:
        return 0
    return 1 + f(x % bin(x).count('1'))

if num_of_1 == 1:
    for i in range(n):
        if x[i] == '1':
            print(0)
        elif i == n-1:
            print(2)
        else:
            print(1)
    exit()

first_one, first_zero = first % (num_of_1 - 1), first % (num_of_1 + 1)

for i in range(n):
    if x[i] == "0":
        print(1 + f((first_zero + pow(2, n-i-1, num_of_1 + 1)) % (num_of_1 + 1)))
    else:
        print(1 + f((first_one - pow(2, n-i-1, num_of_1 - 1)) % (num_of_1 - 1)))
### BUGGY CODE ###

n, k, *L = map(int, open(0).read().split())

# dp = [float("inf")] * n
dp = [0] * n

for i in range(1, n):
    j = max(0, i - k)
    dp[i] = min([DP + abs(L[i] - COST) for DP, COST in zip(dp[j:i], L[j:i])])

print(dp[-1])


### FIXED CODE ###

n, k, *L = map(int, open(0).read().split())

# dp = [float("inf")] * n
dp = [0] * n

for i in range(1, n):
    j = max(0, i - k)
    e = L[i]
    dp[i] = min([DP + abs(e - COST) for DP, COST in zip(dp[j:i], L[j:i])])

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

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

def xor(a, b):
  return a^b

ans = 0
for i in range(N-1):
  for j in range(i + 1, N):
    ans += xor(A[i] , A[j])
    ans = ans % MOD

print(ans%MOD)


### FIXED CODE ###

import numpy as np
n = int(input())
A = np.array(list(map(int, input().split())))
mod = 10 ** 9 + 7

ans = 0
for i in range(64):
    tmp = (A >> i) & 1
    #print(tmp)
    x = np.count_nonzero(tmp)
    x *= n - x
    ans += pow(2, i, mod) * x % mod

print(ans % mod)