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

n = int(input())
A = list(map(int, input().split()))
F = [int()] * n
F[0] = A[0]
for b in range(1, n):
    F[b] = F[b - 1] + A[b]



res = [0]*4
data = [10 ** 18] * 2
ex = [0]*4
ans = 10 ** 18
for i in range(1, n - 1):
    for j in range(0, i):
        res[0] = F[j]
        res[1] = F[i] - F[j]
        if data[0] > abs(res[1] - res[0]) or j == 0:
            ex[0] = res[0]
            ex[1] = res[1]
            data[0] = abs(res[1] - res[0])
    for k in range(i + 1, n):
        res[2] = F[k] - F[i]
        res[3] = F[n - 1] - F[k]
        if data[1] > abs(res[3] - res[2]) or k == i + 1:
            ex[2] = res[2]
            ex[3] = res[3]
            data[1] = abs(res[3] - res[2])
    ans = min(ans, max(ex) - min(ex))

print(ans)


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
F = [int()] * n
F[0] = A[0]
for b in range(1, n):
    F[b] = F[b - 1] + A[b]


res = [0]*4
data = [10 ** 18] * 2
ex = [0]*4
ans = 10 ** 18
s = 0
t = 2
for i in range(1, n - 2):
    bl = [True, True]
    for j in range(s, i):
        res[0] = F[j]
        res[1] = F[i] - F[j]
        if not bl[0]:
            break
        if data[0] > abs(res[1] - res[0]) or j == s:
            s = j
            ex[0] = res[0]
            ex[1] = res[1]
            data[0] = abs(res[1] - res[0])
        else:
            bl[0] = False
    for k in range(t, n):
        res[2] = F[k] - F[i]
        res[3] = F[n - 1] - F[k]
        if not bl[1]:
            break
        if data[1] > abs(res[3] - res[2]) or k == t:
            t = k
            ex[2] = res[2]
            ex[3] = res[3]
            data[1] = abs(res[3] - res[2])
        else:
            bl[1] = False
    ans = min(ans, max(ex) - min(ex))

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

N, Q = map(int, input().split())
S = input()
for _ in range(Q):
    ans = 0
    l, r = map(int, input().split())
    tar = S[l-1:r]
    print(tar.count('AC'))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
imosu = [0] * (N + 1)
for i in range(N):
    imosu[i + 1] = imosu[i] + (1 if S[i:i+2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(imosu[r-1]-imosu[l-1])
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
for _ in range(q):
  l, r = [int(x) for x in input().split()]
  l -= 1
  print(s[l:r].count('AC'))


### FIXED CODE ###

n, q = map(int, input().split())
s = input()

dp = [0 for column in range(n)]

for j in range(1, n):
    if s[j-1] == 'A' and s[j] == 'C':
        dp[j] = dp[j-1] + 1
    else:
        dp[j] = dp[j-1]

for _ in range(q):
    i, j =  map(int, input().split())
    print(dp[j-1] - dp[i-1])
### BUGGY CODE ###

n = int(input())
A = [int(input()) for _ in range(n)]
As = set(A)
ans = 0
for i in As:
    if A.count(i) % 2 == 0:
        continue
    else:
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
A = [input() for _ in range(n)]
AS = set()
for i in A:
    if i not in AS:
        AS.add(i)
    else:
        AS.remove(i)
print(len(AS))
### BUGGY CODE ###

from itertools import combinations

N,K = map(int,input().split())
h = [int(input()) for _ in range(N)]

res = 10**10
for i in combinations(h,K):
    tmp = max(i) - min(i)
    res = min(res,tmp)
print(res)

### FIXED CODE ###

from itertools import combinations

N,K = map(int,input().split())
h = [int(input()) for _ in range(N)]

'''
res = 10**10
for i in combinations(h,K):
    tmp = max(i) - min(i)
    res = min(res,tmp)
'''

d = sorted(h)
res = 1e+9
for i in range(N-K+1):
    res = min(res,d[i+K-1] - d[i])
print(res)
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**7)
k = int(input())
ans = []
def bfs(que):
    finished = set()
    while que and len(ans) <= 10**6:
        x = que.popleft()
        ans.append(int(x))
        if x not in finished:
            finished.add(x)
            p = int(x[-1])
            que.append(x + str(p))
            if 1 <= p <= 8:
                que.append(x + str(p+1))
                que.append(x + str(p-1))
            elif p == 0:
                que.append(x + str(p+1))
            else:
                que.append(x + str(p-1))
que = deque([])
for i in range(1,10):
    que.append(str(i))
bfs(que)
ans.sort()
print(ans[k-1])

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**7)
k = int(input())
ans = []
def bfs(que):
    finished = set()
    while que and len(ans) <= 10**5:
        x = que.popleft()
        ans.append(int(x))
        if x not in finished:
            finished.add(x)
            p = int(x[-1])
            if 1 <= p <= 8:
                que.append(x + str(p-1))
                que.append(x + str(p))
                que.append(x + str(p+1))
            elif p == 0:
                que.append(x + str(p))
                que.append(x + str(p+1))
            else:
                que.append(x + str(p-1))
                que.append(x + str(p))
que = deque([])
for i in range(1,10):
    que.append(str(i))
bfs(que)
ans.sort()
print(ans[k-1])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, p: "List[float]"):
    dp = [[0] * (N + 1) for _ in range(N + 1)]
    dp[0][0] = 1.0

    for i in range(N):
        for j in range(N):
            dp[i+1][j+1] += p[i] * dp[i][j]
            dp[i+1][j] += (1.0 - p[i]) * dp[i][j]
    return sum(dp[-1][(N // 2 + 1):])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    p = [ float(next(tokens)) for _ in range(N) ]  # type: "List[float]"
    result = solve(N, p)
    if isinstance(result, Iterable) and not isinstance(result, str):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, p: "List[float]"):
    dp = [[0] * (N + 1) for _ in range(N + 1)]
    dp[0][0] = 1.0

    for i in range(N):
        for j in range(N):
            dp[i+1][j+1] += p[i] * dp[i][j]
            dp[i+1][j] += (1.0 - p[i]) * dp[i][j]
    return sum(dp[-1][(N // 2 + 1):])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    p = [ float(next(tokens)) for _ in range(N) ]  # type: "List[float]"
    result = solve(N, p)
    print(result)

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

n,k = (int(x) for x in input().split())
list = list(map(int, input().split()))
max = 0
min=1000000000000000000000
if k<=n/2:
	for i in range(0,n-k+1):
		su = sum(list[i:i+k])
		if su>max:
			max=su
	print((max+k)/2)
else:
	for i in range(0,n-k+1):
		su = sum(list[0:i])
		su+=sum(list[i+k:])
		if su<min:
			min=su
	print((sum(list)-min+k)/2)

### FIXED CODE ###

n,k = (int(x) for x in input().split())
list = list(map(int, input().split()))
max=0
list2=[0]
for i in range(n):
	list2.append(list2[i]+list[i])
for i in range(n-k+1):
	if max < list2[i+k] - list2[i]:
		max=list2[i+k]-list2[i]
print((max+k)/2)
### BUGGY CODE ###

from collections import deque
H,W = map(int,input().split())
mat = []
alr = [[-1 for i in range(W)] for j in range(H)]
que = deque()
for i in range(H):
    mat.append(list(input()))
    for j in range(W):
        if mat[i][j] == '#':
            alr[i][j] = 0
            que.append([i,j])

x1 = [0,0,1,-1]
y1 = [1,-1,0,0]
count = 0
while que:
    q = que.popleft()
    for i in range(4):
        if (0 <= q[0]+x1[i] <= H-1) and (0 <= q[1]+y1[i] <= W-1):
            if mat[q[0]+x1[i]][q[1]+y1[i]] == '.' and alr[q[0]+x1[i]][q[1]+y1[i]] == -1:
                alr[q[0]+x1[i]][q[1]+y1[i]] = alr[q[0]][q[1]] + 1
                que.append([q[0]+x1[i],q[1]+y1[i]])
                mat[q[0]+x1[i]][q[1]+y1[i]] = '#'
maxa = 0
for i in alr:
    for j in i:
        maxa = max(maxa,j)
print(maxa)


### FIXED CODE ###

from collections import deque
H,W = map(int,input().split())
mat = []
alr = [[-1 for i in range(W)] for j in range(H)]
que = deque()
for i in range(H):
    mat.append(list(input()))
    for j in range(W):
        if mat[i][j] == '#':
            alr[i][j] = 0
            que.append([i,j])

x1 = [0,0,1,-1]
y1 = [1,-1,0,0]
count = 0
while que:
    q = que.popleft()
    for i in range(4):
        if (0 <= q[0]+x1[i] <= H-1) and (0 <= q[1]+y1[i] <= W-1):
            if mat[q[0]+x1[i]][q[1]+y1[i]] == '.' and alr[q[0]+x1[i]][q[1]+y1[i]] == -1:
                alr[q[0]+x1[i]][q[1]+y1[i]] = alr[q[0]][q[1]] + 1
                count = max(count,alr[q[0]][q[1]] + 1)
                que.append([q[0]+x1[i],q[1]+y1[i]])
                mat[q[0]+x1[i]][q[1]+y1[i]] = '#'

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

n,m = map(int,input().split( ))
ls_a = []
ls_b = [[] for i in range(n)]
for i in range(m):
    p,y = map(int,input().split( ))
    ls_a.append([p,y])
    ls_b[p-1].append(y)
for i in range(n):
    if len(ls_b[i]) !=0:
        ls_b[i].sort()
for i in range(m):
    print(str(ls_a[i][0]).zfill(6) + str(ls_b[ls_a[i][0]-1].index(ls_a[i][1])+1).zfill(6))

### FIXED CODE ###

N,M=map(int,input().split())
PY=[list(map(int,input().split()))+[i] for i in range(M)] #定義終了
 
PY.sort(key= lambda x:x[1])
num=[0]*N
w=[""]*M
 
for p,y,i in PY:
	num[p-1]+=1
	w[i]=str(p).zfill(6)+str(num[p-1]).zfill(6)

for i in range(M):
  	print(w[i])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(210000)
def s(x,v,d):
  r=[d,v]
  for u in g[v]:
    if u!=x:
      t=s(v,u,d+1)
      if r[0]<t[0]:r=t
  return r
n,*t=map(int,open(0).read().split())
g=[set()for _ in range(n+1)]
for a,b in zip(t[::2],t[1::2]):
  g[a].add(b)
  g[b].add(a)
print('SFeicrosntd'[s(0,s(0,1,0)[1],0)[0]%3!=1::2])

### FIXED CODE ###

import sys
sys.setrecursionlimit(250000)
def s(x,v,d):
  r=[d,v]
  for u in g[v]:
    if u!=x:
      t=s(v,u,d+1)
      if r[0]<t[0]:r=t
  return r
n,*t=map(int,open(0).read().split())
g=[[]for _ in range(n+1)]
for a,b in zip(t[::2],t[1::2]):
  g[a].append(b)
  g[b].append(a)
print('SFeicrosntd'[s(0,s(0,1,0)[1],0)[0]%3!=1::2])
### BUGGY CODE ###

n=int(input())
a=[]
for i in range(n):
  x=int(input())
  a.append(x)
ans=0
a_set=set(a)
for i in a_set:
  if a.count(i)%2==1:
    ans+=1
print(ans)
  

### FIXED CODE ###

import sys
n = int(input())
a = [int(i) for i in sys.stdin]
a.sort()
dict = {}
for i in range(n):
  if a[i] in dict:
    del dict[a[i]]
  else: 
  	dict[a[i]]=0
print(len(dict))
### BUGGY CODE ###

def examD():
    N = I()
    g, s, c = [0]*2, [0]*2, [0]*2
    for i in range(2):
        g[i],s[i],c[i] = LI()
    dp1 = [0]*(N+1)
    v1 = [g[1]-g[0],s[1]-s[0],c[1]-c[0]]
    w1 = [g[0],s[0],c[0]]
    v2 = [g[0]-g[1],s[0]-s[1],c[0]-c[1]]
    w2 = [g[1],s[1],c[1]]
    for i in range(N):
        if i+w1[0]<=N:
            dp1[i+w1[0]] = max(dp1[i+w1[0]],dp1[i]+v1[0])
        if i+w1[1]<=N:
            dp1[i+w1[1]] = max(dp1[i+w1[1]],dp1[i]+v1[1])
        if i+w1[2]<=N:
            dp1[i+w1[2]] = max(dp1[i+w1[2]],dp1[i]+v1[2])
    newN = max(dp1)+N
#    print(newN)
    dp2 = [0]*(newN+1)
    for i in range(newN):
        if i+w2[0]<=newN:
            dp2[i+w2[0]] = max(dp2[i+w2[0]],dp2[i]+v2[0])
        if i+w2[1]<=newN:
            dp2[i+w2[1]] = max(dp2[i+w2[1]],dp2[i]+v2[1])
        if i+w2[2]<=newN:
            dp2[i+w2[2]] = max(dp2[i+w2[2]],dp2[i]+v2[2])
    ans = max(dp2)+newN
    print(ans)

from string import digits
import sys,copy,bisect,itertools,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()


### FIXED CODE ###

def examD():
    N = I()
    g, s, c = [0]*2, [0]*2, [0]*2
    for i in range(2):
        g[i],s[i],c[i] = LI()
    dp1 = [0]*(N+1)
    v1 = [g[1]-g[0],s[1]-s[0],c[1]-c[0]]
    w1 = [g[0],s[0],c[0]]
    v2 = [g[0]-g[1],s[0]-s[1],c[0]-c[1]]
    w2 = [g[1],s[1],c[1]]
    for i in range(N):
        if i+w1[0]<=N:
            dp1[i+w1[0]] = max(dp1[i+w1[0]],dp1[i]+v1[0])
        if i+w1[1]<=N:
            dp1[i+w1[1]] = max(dp1[i+w1[1]],dp1[i]+v1[1])
        if i+w1[2]<=N:
            dp1[i+w1[2]] = max(dp1[i+w1[2]],dp1[i]+v1[2])
    newN = max(dp1)+N
#    print(newN)
    dp2 = [0]*(newN+1)
    for i in range(newN):
        if v2[0]>0 and i+w2[0]<=newN:
            dp2[i+w2[0]] = max(dp2[i+w2[0]],dp2[i]+v2[0])
        if v2[1]>0 and i+w2[1]<=newN:
            dp2[i+w2[1]] = max(dp2[i+w2[1]],dp2[i]+v2[1])
        if v2[2]>0 and i+w2[2]<=newN:
            dp2[i+w2[2]] = max(dp2[i+w2[2]],dp2[i]+v2[2])
    ans = dp2[newN]+newN
    print(ans)

from string import digits
import sys,copy,bisect,itertools,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()
### BUGGY CODE ###

N = int(input())
S = input()

counter = 0
for k in range(N):
    for j in range(k):
        for i in range(j):
            if (not S[i]==S[j]) and (not S[i]==S[k]) and (not S[j]==S[k]) and not(j-i==k-j):
                counter += 1
print(counter)

### FIXED CODE ###

N = int(input())
S = input()
counter = 0

for i in range(N-2):
    for j in range(i+1,(N+i-1)//2+1):
        k = 2*j-i
        if not S[i]==S[j] and  not S[j]==S[k] and not S[i]==S[k]:
            counter += 1

rgb = S.count("R")*S.count("G")*S.count("B")
print(rgb-counter)
### BUGGY CODE ###

import collections
import numpy as np

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

N =int(input())

a = [int(i) for i in input().split()]

ans_array = np.zeros(N)

for i in range(N):
    dummy = prime_factorize(a[i])
    if collections.Counter(dummy).get(2) is not None:
        ans_array[i] = collections.Counter(dummy)[2]
ans = int(sum(ans_array))
print(ans)

### FIXED CODE ###

import collections
import numpy as np

def prime_factorize(n):
	a = 0   
	while n % 2 == 0:
		a+=1
		n //= 2
	return a

N =int(input())

a = [int(i) for i in input().split()]

ans_array = np.zeros(N)

for i in range(N):
    dummy = prime_factorize(a[i])
  
    ans_array[i] = dummy
ans = int(sum(ans_array))
print(ans)
### BUGGY CODE ###

string = input()
kai = int(input())
data = [input().split(' ') for i in range(kai)]
key = 0  #0 start

for i in range(kai):
    if(data[i][0] == '1'):
        key = (key + 1) % 2
    elif(data[i][1] == '1'):
        if(key == 0):
            string = data[i][2] + string
        else:
            string = string + data[i][2]
    elif(key == 0):
        string = string + data[i][2]
    else:
        string = data[i][2] + string
if(key == 0):
    print(string)
else:
    print(string[::-1])


### FIXED CODE ###

string = input()
kai = int(input())
data = [input().split(' ') for i in range(kai)]
key = 0  #0 start
former = []
latter = []

for i in range(kai):
    if(data[i][0] == '1'):
        key = (key + 1) % 2
    elif((int(data[i][1]) + key) % 2 == 1):
        former.append(data[i][2])
    else:
        latter.append(data[i][2])

string = ''.join(former[::-1]) + string + ''.join(latter)
if(key == 0):
    print(string)
else:
    print(string[::-1])
### BUGGY CODE ###

def encode(s):
  r = [0]*26
  for n in range(len(s)):
    r[ord(s[n]) - ord('a')] += 1
  return r

N = int(input())

S = []

for n in range(N):
  s = str(input())
  S = S + [encode(s)]

S.sort()

ct = 0
M=1
ps=""
for cs in S:
  if cs==ps:
    M+=1
  else:
    ct += int((M**2-M)/2)
    M=1
    ps=cs
ct += int((M**2-M)/2)

print(ct)
      
  

### FIXED CODE ###

def encode(s):
#  r = [0]*26
#  for n in range(len(s)):
#    r[ord(s[n]) - ord('a')] += 1
#  return r
#  r = list(s)
#  r.sort()
#  return r
  r = 0
  for n in range(len(s)):
    so = ord(s[n]) - ord('a')
    r += 11**so
  return r

N = int(input())

S = [0]*N

for n in range(N):
  s = str(input())
  S[n] = encode(s)

S.sort()

ct = 0
M=1
ps=""
for cs in S:
  if cs==ps:
    M+=1
  else:
    ct += int((M**2-M)/2)
    M=1
    ps=cs
ct += int((M**2-M)/2)

print(ct)
### BUGGY CODE ###

def z(z_dic, v: int):
    if v in z_dic:
        return z_dic[v]
    z = 0
    if v == 2:
        z = 1
    elif v > 2:
        z = int(v*(v-1)/2)
    z_dic.setdefault(v, z)
    return z


def main():
    s = input()
    q = int(input())

    reverse = False
    for _ in range(q):
        line_ls = input().split()
        # 長さが1ならTi=1
        if len(line_ls) == 1:
            reverse = not reverse
            continue

        fi = line_ls[1]
        ci = line_ls[2]
        if fi == "1":
            if not reverse:
                s = ci + s
            else:
                s += ci
        else:
            if not reverse:
                s += ci
            else:
                s = ci + s

    if reverse:
        s = s[::-1]

    print(s)




main()


### FIXED CODE ###

def main():
    s = input()
    q = int(input())

    reverse = False
    pre = ""
    post = ""
    for _ in range(q):
        line_ls = input().split()
        # 長さが1ならTi=1
        if len(line_ls) == 1:
            reverse = not reverse
            continue

        fi = line_ls[1]
        ci = line_ls[2]
        if fi == "1":
            if not reverse:
                pre += ci
            else:
                post += ci
        else:
            if not reverse:
                post += ci
            else:
                pre += ci

    if reverse:
        s = s[::-1]
        post = post[::-1]
        print(post + s + pre)
    else:
        pre = pre[::-1]
        print(pre + s + post)


main()
### BUGGY CODE ###

from operator import mul
from functools import reduce
def comb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
n, a, b = map(int, input().split())
print(int(pow(2, n) - 1 - comb(n, a) - comb(n, b)) % (10 ** 9 + 7))

### FIXED CODE ###

n, a, b = map(int, input().split())
mod = 10 ** 9 + 7
u, d, c = [1], [1], [1]
for i in range(1, b + 1):
    u.append(u[-1] * (n - i + 1) % mod)
    d.append(d[-1] * i % mod)
    c.append(u[i] * pow(d[i], mod - 2, mod) % mod)
print((pow(2, n, mod) - 1 - c[a] - c[b]) % mod)
### BUGGY CODE ###

T = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
if T[0]* A[0] + T[1] * A[1] == T[0] * B[0] + T[1] * B[1]:
    print('infinity')
else:
    ans = 0
    A_pos = 0
    B_pos = 0
    before_state = -1 # 0:A>B, 1:A < B, -1:A=B
    flag = True
    while flag:
        for i in range(2):
            A_pos += T[i]* A[i]
            B_pos += T[i]* B[i]
            if A_pos > B_pos:
                if before_state == 0:
                    ans += 1
                before_state = 1
                if A_pos - B_pos > T[(i+1)%2] * B[(i+1)%2]:
                    flag = False
                    break
            elif A_pos < B_pos:
                if before_state == 1:
                    ans += 1
                before_state = 0
                if B_pos - A_pos > T[(i+1)%2] * A[(i+1)%2]:
                    flag = False
                    break
            elif A_pos == B_pos:
                ans += 1
                before_state = -1
    print(ans)

### FIXED CODE ###

T = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
if T[0]* A[0] + T[1] * A[1] == T[0] * B[0] + T[1] * B[1]:
    print('infinity')
else:
    ans = 0
    A_pos = 0
    B_pos = 0
    before_state = -1 # 0:A>B, 1:A < B, -1:A=B
    flag = True
    diff = abs(T[0]* A[0] + T[1]* A[1] - (T[0]* B[0] + T[1]* B[1]))
    diff_max = max(abs(A[0] - B[0])*T[0],  abs(A[1] - B[1])*T[1])
    max_num = int(diff_max/diff)
    up_num_first = 0
    for i in range(2):
        A_pos += T[i]* A[i]
        B_pos += T[i]* B[i]
        if A_pos > B_pos:
            if before_state == 0:
                up_num_first += 1
            before_state = 1
        elif A_pos < B_pos:
            if before_state == 1:
                up_num_first += 1
            before_state = 0
        elif A_pos == B_pos:
            up_num_first += 1
            before_state = -1
    A_pos_first = A_pos
    B_pos_first = B_pos
            
    up_num_second = 0
    for i in range(2):
        A_pos += T[i]* A[i]
        B_pos += T[i]* B[i]
        if A_pos > B_pos:
            if before_state == 0:
                up_num_second += 1
            before_state = 1
        elif A_pos < B_pos:
            if before_state == 1:
                up_num_second += 1
            before_state = 0
        elif A_pos == B_pos:
            up_num_second += 1
            before_state = -1

    A_pos = A_pos_first * (max_num - 1)
    B_pos = B_pos_first * (max_num - 1)
    up_num_final = 0
    for i in range(2):
        A_pos += T[i]* A[i]
        B_pos += T[i]* B[i]
        if A_pos > B_pos:
            if before_state == 0:
                up_num_final += 1
            before_state = 1
        elif A_pos < B_pos:
            if before_state == 1:
                up_num_final += 1
            before_state = 0
        elif A_pos == B_pos:
            up_num_final += 1
            before_state = -1
    if max_num > 1:
        ans = up_num_first  + (max_num - 2) * up_num_second  + up_num_final
    else:
        ans = up_num_first  + (max_num - 1) * up_num_second
    print(ans)
### BUGGY CODE ###

ken_shi_list = input().split()
ken_num = int(ken_shi_list[0])
shi_num = int(ken_shi_list[1])

shi_list = []
nen_list = [[] for i in range(ken_num) ]


for i in range(shi_num):
    shi_list.append(input().split())
    nen_list[int(shi_list[i][0])-1].append( int(shi_list[i][1]) )


for i in range(ken_num):
   nen_list[i-1].sort()


for i in range(shi_num):
    ken = int(shi_list[i][0])
    nen = int(shi_list[i][1])
    for j in range( len(nen_list[ken-1]) ):
        if nen == nen_list[ken-1][j] :
            print( str(ken).zfill(6) + str(j+1).zfill(6) )    
            break



### FIXED CODE ###

ken_shi_list = input().split()
ken_num = int(ken_shi_list[0])
shi_num = int(ken_shi_list[1])
 
shi_list = []
nen_list = [[] for i in range(ken_num) ]
 
for i in range(shi_num):
    shi_list.append(input().split())
    nen_list[int(shi_list[i][0])-1].append( int(shi_list[i][1]) )
 
 
checker = {}
for i in range(ken_num):
   nen_list[i].sort()
   for j in range(len(nen_list[i])):
        checker[nen_list[i][j]] = j+1


for i in range(shi_num):
    ken = int(shi_list[i][0])
    nen = int(shi_list[i][1])
    print( str(ken).zfill(6) + str(checker[nen]).zfill(6) )