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

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

for i in range(Q):
    B, C = map(str, input().split())
    A = list(map(lambda x: int(str(x).replace(B, C)), A))
    print(sum(A))



### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
s = [0] * (10**5+5)
Q = int(input())
total = sum(A)

for i in A:
    s[i] += 1

for _ in range(Q):
    B, C = map(int, input().split())
    d = s[B]
    s[B] = 0
    s[C] += d
    total += (C-B) * d
    print(total)
### BUGGY CODE ###

import math
K=int(input())
sum=0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):           
            
            sum+=math.gcd(math.gcd(a,b),c)
print(sum)


### FIXED CODE ###

from math import gcd
K=int(input())
sum=0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):           
            
            sum+=gcd(gcd(a,b),c)
print(sum)
### BUGGY CODE ###

N = int(input())
m = []
for i in range(1, N):
    m.append( i % (i+1) )
print(sum(m))

### FIXED CODE ###

N = int(input())
ans = ((N - 1) * N ) // 2
print(ans)
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
m=max(A)+1
B=A[:]
C=[A.count(i)for i in range(m)]
for i in range(1,m):C[i]+=C[i-1]
for j in A[::-1]:B[C[j]-1]=j;C[j]-=1
print(*B)


### FIXED CODE ###

def s():
 input()
 C=[0]*10001
 for a in map(int,input().split()):C[a]+=1
 B=[];i=0
 for k in C:B+=[str(i)]*k;i+=1
 print(' '.join(B))
if'__main__'==__name__:s()
### BUGGY CODE ###

S = list(input())
N = len(S)
 
 
l = [0] * 2019
index = 0
temp = 0
for i in range(N-1, -1, -1):
    temp += int(S[i]) * 10**index
    l[temp%2019] += 1
    index += 1
 
ans = l[0]
 
for i in range(1, 2019):
    v = l[i]
    ans += v * (v-1) // 2
 
print(ans)

### FIXED CODE ###

S = list(input())
N = len(S)
S = [int(s) for s in S]
S = S[::-1]
l = [0] * 2019
index = 0
tmp = 0
z = 1
for i, s in enumerate(S):
    tmp += s * pow(10, i, 2019)
    l[tmp%2019] += 1

ans = l[0]

for v in l:
    ans += v * (v-1) // 2
print(ans)
### BUGGY CODE ###

from collections import deque
import copy

ADS = [(0, 1), (1, 0), (0, -1), (-1, 0)]

H, W = map(int, input().split(" "))
A = [list(input()) for _ in range(H)]

q = deque()

for y in range(H):
    for x in range(W):
        if A[y][x] == "#":
            q.append((x, y))

count = 0
while q: # 10**6
    r = copy.copy(q)
    q = deque()
    while r:
        this_pos = this_x, this_y = r.popleft()

        for ad_x, ad_y in ADS:
            x, y = this_x+ad_x, this_y+ad_y
            if not ((0 <= x < W) and (0 <= y < H)):
                continue
            if A[y][x] == "#":
                continue
            A[y][x] = "#"
            q.append((x, y))
    count += 1
    # print(A, q, count)

print(count-1)

### FIXED CODE ###

from collections import deque
from itertools import chain

INF = 10**18

H, W = map(int, input().split())
A = [input() for _ in range(H)]

q = deque([])
dist = [[INF for _ in range(W)]for _ in range(H)]
for y, A_line in enumerate(A):
    for x, a in enumerate(A_line):
        if a == "#":
            dist[y][x] = 0
            q.append((x, y))

while q:
    t_pos = tx, ty = q.popleft()
    dist_t = dist[ty][tx]

    for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        pos = x, y = tx+dx, ty+dy
        if not (0 <= x < W and 0 <= y < H):
            continue
        elif A[y][x] == "#":
            continue
        elif dist[y][x] <= dist_t + 1:
            continue
        dist[y][x] = dist_t + 1
        q.append(pos)
# print(dist)

r = max(chain(*dist))
print(r)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(200000)

N, Q=map(int, input().split())
ab=[list(map(int, input().split())) for _ in range(N-1)]
px=[list(map(int, input().split())) for _ in range(Q)]
to=[[] for _ in range(N)]
co=[0 for _ in range(N)]

for a, b in ab:
    a-=1
    b-=1
    to[a].append(b)
    to[b].append(a)
for p, x in px:
    p-=1
    co[p]+=x

def dfs(v, p=-1):
    for u in to[v]:
        if u==p:
            continue
        co[u]+=co[v]
        dfs(u, v)

dfs(0)
print(*co)

### FIXED CODE ###

N,Q=map(int, input().split())
node_lst=[list(map(int, input().split())) for i in range(N-1)]
ope_lst=[list(map(int, input().split())) for i in range(Q)]
cnt_lst=[0 for i in range(N)]
for ope in ope_lst:
    p, x = ope[0], ope[1]
    cnt_lst[p-1]+=x
node_lst=sorted(node_lst, key=lambda x:x[0])
for l in node_lst:
    src, dst = l[0]-1, l[1]-1
    cnt_lst[dst]+=cnt_lst[src]
print(" ".join([str(c) for c in cnt_lst]))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import numpy as np
N,T=map(int, input().split())
val=[list(map(int, input().split())) for i in range(N)]
#import sys
#input = sys.stdin.readline
#val = list(input()) #abc
val=np.array(val)
index=np.argsort(val[:,0])
A=val[index,0]
B=val[index,1]

temp=[[0]*N for i in range(T+1)]
for jtemp in range(N-1):
    j=jtemp+1

    for itemp in range(T):
        i=itemp
        if i>=A[0]:
            temp[i][0]=B[0]
        if i>0:
            temp[i][j]=max(temp[i][j],temp[i-1][j])
            
        temp[i][j]=max(temp[i][j],temp[i][j-1])
        if A[j]<T-i:
            temp[i+A[j]][j]=max(temp[i][j-1]+B[j],temp[i+A[j]][j])
        else:
            temp[T][j]=max(temp[i][j-1]+B[j],temp[T][j])
print(max(temp[-1][:])) 

### FIXED CODE ###

# -*- coding: utf-8 -*-

N,T=map(int, input().split())
val=[list(map(int, input().split())) for i in range(N)]

#import sys
#input = sys.stdin.readline
#val = list(input()) #abc
#val=np.array(val)
#index=np.argsort(val[:,0])
#A=val[index,0].tolist()
#B=val[index,1].tolist()
val.sort()
A=[v[0] for v in val]
B=[v[1] for v in val]

#temp=np.zeros((T+1,N))
#Ts=T*np.ones(N-1)
#jun=np.arange(1,N)
#for itemp in range(T):
#    i=itemp
#    if i>=A[0]:
#        temp[i,0]=B[0]
#    if i>0:
#        temp[i,:]=np.amax([temp[i,:],temp[i-1,:]],0)
#    for jtemp in range(N-1):
#        j=jtemp+1
#        temp[i,j]=max(temp[i,j],temp[i,j-1])
#    jnext=np.amin([Ts,i+A[1:]],0)
#    jnext=[int(s) for s in jnext]
#    temp[jnext,jun]=np.amax([temp[i,:-1]+B[1:],temp[jnext,jun]],0)

temp=[[0]*N for i in range(T+1)]

for itemp in range(T):
    i=itemp
    if i>=A[0]:
        temp[i][0]=B[0]
    for jtemp in range(N-1):
        j=jtemp+1
        jbfo=temp[i][j-1]
        ijnow=temp[i][j]
        
        if i>0:
            temp[i][j]=max(ijnow,temp[i-1][j])
            
        temp[i][j]=max(ijnow,jbfo)
        if A[j]<T-i:
            temp[i+A[j]][j]=max(jbfo+B[j],temp[i+A[j]][j])
        else:
            temp[T][j]=max(jbfo+B[j],temp[T][j])
print(int(max(temp[-1][:])))
### BUGGY CODE ###

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

MOD = 10**9+7
ans = 0
for i in range(n-1):
    for j in range(i+1,n):
        ans += (a[i] * a[j]) % MOD
print(ans%MOD)

### FIXED CODE ###

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

A = [0]
for i in range(n):
    A.append(A[i] + a[i])

MOD = 10**9+7
ans = 0
for i in range(n-1):
    ans += (a[i] * (A[-1]-A[i+1])) % MOD

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

mod = 10 ** 9 + 7
N, K = map(int, input().split())

gcd1_tuples = [0] * (K+1)

for i in range(1, K+1):
    gcd1_tuples[i] = pow(i, N, mod)
    for j in range(2, i+1):
        gcd1_tuples[i] -= gcd1_tuples[i//j]
    gcd1_tuples[i] %= mod

s = 0
for i in range(1, K+1):
    s += gcd1_tuples[K//i] * i
    s %= mod

print(s)


### FIXED CODE ###

from functools import lru_cache


mod = 10 ** 9 + 7
N, K = map(int, input().split())

@lru_cache
def gcd1_tuples(k):
    if k == 1:
        return 1
    tmp = pow(k, N, mod)
    for j in range(2, k+1):
        tmp -= gcd1_tuples(k//j)
        tmp %= mod
    return tmp

s = 0
for i in range(1, K+1):
    s += gcd1_tuples(K//i) * i
    s %= mod

print(s)
### BUGGY CODE ###

# E
from fractions import gcd

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

value = 1
for a in A:
    value = value * a // gcd(value, a)

mod = 10**9+7

ans = 0
for i in A:
    ans += value * pow(i, mod-2,mod)
    ans = ans % mod

print(ans)


### FIXED CODE ###

# E
from fractions import gcd

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

value = 1
for a in A:
    value = value * a // gcd(value, a)

mod = 10**9+7

ans = 0
for i in A:
    ans += value // i

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

N = int(input())

mod = (N-1)*N/2
for i in range(1,N+1):
    if N%i == N:
        break

print(int(mod+N-i))


### FIXED CODE ###

n = int(input())
print(n*(n-1)//2)
### BUGGY CODE ###



N=int(input())
S=list(map(int,input().split()))
S.sort()
S.reverse()

count=0
le=len(S)
S.append(-100000)
for i in range(le-2):
    for j in range(i+1,le-1):
        if S[i]<S[j]+S[j+1]:
            left=j+1
            right=le
            while left<=right:
                mid=(left+right)//2
                if S[i]<S[j]+S[mid] and S[i]>=S[j]+S[mid+1]:
                    count+= mid-(j+1)+1
                    
                    break
                elif S[i]<S[j]+S[mid]:
                    left=mid+1
                elif S[i]>=S[j]+S[mid]:
                    right=mid-1
                else:
                    print("イレギュラーな例につかまりました")
                    exit()
                
print(count)


### FIXED CODE ###



N=int(input())
S=list(map(int,input().split()))
S.sort()
S.reverse()

count=0
le=len(S)
S.append(-100000)
for i in range(le-2):
    for j in range(i+1,le-1):
        if S[i]<S[j]+S[j+1]:
            left=j+1
            right=le
            while left<=right:
                mid=(left+right)//2
                if S[i]<S[j]+S[mid] and S[i]>=S[j]+S[mid+1]:
                    count+= mid-(j+1)+1
                    
                    break
                elif S[i]<S[j]+S[mid]:
                    left=mid+1
                elif S[i]>=S[j]+S[mid]:
                    right=mid-1
                else:
                    print("イレギュラーな例につかまりました")
                    exit()
                
print(count)
### BUGGY CODE ###

n=int(input())
a=[]
for i in range(n):
   a.append(int(input()))
temp=max(a)
for i in range(n):
    if a[i]<temp:
        print(temp)
    else:
        temp2=a.pop(i)
        print(max(a))
        a.insert(i,temp2)

### FIXED CODE ###

n=int(input())
a=[]
for i in range(n):
   a.append(int(input()))
b=sorted(a,reverse=True)
tempa=b[0]
tempb=b[1]
for i in range(n):
    if a[i]<tempa:
        print(tempa)
    else:
        print(tempb)
### BUGGY CODE ###

import heapq
 
# 1から初めて、xがあるとき10x、x+1のいずれかが行えるとしてqueue
 
K = int(input())
h = []
heapq.heappush(h,(1,1)) # 各桁の和、modulo K
visited = [False]*K
 
ans = 0
 
while ans == 0:
  s,x = heapq.heappop(h)
  visited[x] = True
  for ss,xx in [(s,(10*x)%K), (s+1,(x+1)%K)]:
    if visited[xx]:
      continue
    if xx == 0:
      ans = ss
      break
    heapq.heappush(h,(ss,xx))
  
print(ans)

### FIXED CODE ###

from collections import deque
 
# 1から初めて、xがあるとき10x、x+1のいずれかが行えるとしてqueue
 
K = int(input())
q = deque()
q.append((1,1)) # 各桁の和、modulo K
visited = [False]*K
 
ans = 0
 
while ans == 0:
  s,x = q.popleft()
  if visited[x]:
    continue
  visited[x] = True
  if x == 0:
    ans = s
    break
  q.appendleft((s,(10*x)%K))
  q.append((s+1,(x+1)%K))
 
print(ans)
### BUGGY CODE ###

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


def function(x, a=a, b=b):
    return int(a * x / b) - a * int(x / b)


ans = function(0)
for i in range(n):
    if i * b - 1 > n:
        ans = max(ans, function(n))
        break
    ans = max(ans, function(i * b - 1))

print(ans)

### FIXED CODE ###

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


def function(x, a=a, b=b):
    return int(a * x / b) - a * int(x / b)
    

ans = function(0)
for i in range(b):
    if i * b - 1 > n:
        ans = max(ans, function(n))
        break
    ans = max(ans, function(i * b - 1))

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

N,M = map(int, input().split())
q = [[int(j) for j in input().split()] for i in range(M)]
li = [[] for k in range(N+1)]

for i,j in sorted(q, key=lambda x:x[1]):
    li[i].append(j)

for p,y in q:
    print("{:0=6}".format(p) + "{:0=6}".format(li[p].index(y)+1))

### FIXED CODE ###

import bisect
N,M = map(int, input().split())
q = [[int(j) for j in input().split()] for i in range(M)]
li = [[] for k in range(N+1)]

for i,j in sorted(q):
    li[i].append(j)

for p,y in q:
    z = bisect.bisect(li[p],y)
    print("{:0=6}".format(p) + "{:0=6}".format(z))
### BUGGY CODE ###

from collections import Counter
n = int(input())
S = []
for _ in range(n):
    S.append(Counter(list(input())))

ans = 0
for i in range(n):
    for j in range(n):
        if i < j:
            c_i = S[i]
            c_j = S[j]
            f = 0
            for k_i, v_i in c_i.items():
                if c_j[k_i] != v_i:
                    f = 1
                    break
            if f == 0:
                ans += 1

print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
S = Counter()
ans = 0
for _ in range(n):
    s = "".join(sorted(input()))
    if S[s] > 0:
        ans += S[s]
    S[s] += 1

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

t = int(input())
ans = []
while t:
  s = input()
  if s not in ans:
    ans.append(s)
  t = t - 1
print(len(ans))
  

### FIXED CODE ###

t = int(input())
ans = []
while t:
  s = input()
  ans.append(s)
  t = t - 1
ans = set(ans)
print(len(ans))
### BUGGY CODE ###

R,C = map(int,input().split())
graph = [[i for i in input()] for j in range(R)]
visited = [[False for i in range(C)] for j in range(R)]

def dfs(start_y,start_x,goal_y,goal_x):
  queue = [[start_y,start_x,0]]
  while queue:
    now = queue.pop(0)
    visited[now[0]][now[1]] = True
    if now[0]==goal_y and now[1]==goal_x: return now[2]
    for next in [[1,0],[-1,0],[0,1],[0,-1]]:
      if now[0]+next[0] < 0 or now[1]+next[1] < 0: continue
      if now[0]+next[0] > R-1 or now[1]+next[1] > C-1: continue
      if visited[now[0]+next[0]][now[1]+next[1]]: continue
      if graph[now[0]+next[0]][now[1]+next[1]]=='#': continue
      queue.append([now[0]+next[0],now[1]+next[1],now[2]+1])
      visited[now[0]+next[0]][now[1]+next[1]] = True

ans = 0
for row_s in range(R):
  for column_s in range(C):
    for row_g in range(R):
      for column_g in range(C):
        if graph[row_s][column_s]=='#' or graph[row_g][column_g]=='#': continue
        visited = [[False for i in range(C)] for j in range(R)]
        ans = max(ans,dfs(row_s,column_s,row_g,column_g))
    
print(ans)

### FIXED CODE ###

R,C = map(int,input().split())
graph = [[i for i in input()] for j in range(R)]
visited = [[False for i in range(C)] for j in range(R)]

def dfs(start_y,start_x):
  queue = [[start_y,start_x,0]]
  while queue:
    now = queue.pop(0)
    visited[now[0]][now[1]] = True
    for next in [[1,0],[-1,0],[0,1],[0,-1]]:
      if now[0]+next[0] < 0 or now[1]+next[1] < 0: continue
      if now[0]+next[0] > R-1 or now[1]+next[1] > C-1: continue
      if visited[now[0]+next[0]][now[1]+next[1]]: continue
      if graph[now[0]+next[0]][now[1]+next[1]]=='#': continue
      queue.append([now[0]+next[0],now[1]+next[1],now[2]+1])
      visited[now[0]+next[0]][now[1]+next[1]] = True
  return now[2]

ans = 0
for row_s in range(R):
  for column_s in range(C):
      if graph[row_s][column_s]=='#': continue
      visited = [[False for i in range(C)] for j in range(R)]
      ans = max(ans,dfs(row_s,column_s))
    
print(ans)
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
b = []
n = 0
for i in a:
  if i in b:
    pass
  elif a.count(i) == i:
    b.append(i)
  elif a.count(i) < i:
    b.append(i)
    n += a.count(i)
  else:
    b.append(i)
    n += a.count(i) - i
print(n)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
dic = {}
for nums in A:
  if nums in dic:
    dic[nums] += 1
  else:
    dic[nums] = 1
a = list(dic.keys())
b = list(dic.values())
i = 0
ans = 0
while i < len(a):
  if a[i] > b[i]:
    ans += b[i]
    i += 1
  else:
    ans += b[i]-a[i]
    i += 1
print(ans)
### BUGGY CODE ###

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

cnt = 0
for i in set(A):
  I = A.count(i)
  if I == i:
    continue
  elif I > i:
    cnt += I - i
  else:
    cnt += I
  
print(cnt)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
C = Counter(A)

cnt = 0
for i in set(A):
  I = C[i]
  if I == i:
    continue
  elif I > i:
    cnt += I - i
  else :
    cnt += I
  
print(cnt)
### BUGGY CODE ###

import math
n=int(input())
b=1
a=list(map(int,input().split()))
x=1000000000000000000
for i in range(n):
    if(a[i]==0):
        print(0)
        exit(0);
    b=b*a[i]

if(b>x):
    b=-1
print(b);


### FIXED CODE ###

import math
n=int(input())
b=1
a=list(map(int,input().split()))
x=1000000000000000000
for i in range(n):
    if(a[i]==0):
        print(0)
        exit(0);

for i in range(n):
    b=b*a[i]
    if(b>x):
        print(-1)
        exit(0)

print(b);
### BUGGY CODE ###

s = input()
mod = 10 ** 9 + 7
dp = [[0 for _ in range(13)] for __ in range(len(s) + 1)]
dp[0][0] = 1
for i in range(len(s)):
    if s[-i-1] == '?':
        for n in range(10):
            a = n * (10 ** i) % 13
            for j in range(13):
                dp[i+1][(j + a) % 13] = (dp[i+1][(j + a) % 13] + dp[i][j]) % mod
    else:
        a = int(s[-i-1]) * (10 ** i) % 13
        for j in range(13):
            dp[i+1][(j + a) % 13] = (dp[i+1][(j + a) % 13] + dp[i][j]) % mod
print(dp[len(s)][5])


### FIXED CODE ###

s = input()
mod = 10 ** 9 + 7
memo = [0] * (len(s) + 1)
memo[0] = 1
dp = [[0 for _ in range(13)] for __ in range(len(s) + 1)]
dp[0][0] = 1
for i, si in enumerate(s[::-1]):
    memo[i+1] = memo[i] * 10 % 13
    if si == '?':
        for n in range(10):
            a = n * memo[i]
            for j in range(13):
                dp[i+1][(j + a) % 13] = (dp[i+1][(j + a) % 13] + dp[i][j]) % mod
    else:
        a = int(si) * memo[i]
        for j in range(13):
            dp[i+1][(j + a) % 13] = (dp[i+1][(j + a) % 13] + dp[i][j]) % mod
print(dp[len(s)][5])
### BUGGY CODE ###

N,M = (map(int, input().split()))
li = list((input().split()) for i in range(N))
for x in range(len(li)):
    li[x] = [int(i) for i in li[x]]

li.sort()

li2=[]
for i in range(len(li)):
    li2.append(li[i][0]*li[i][1])

li3 = []
for j in range(len(li)):
    for i in range(li[j][1]):
        li3.append(li[j][0])

print(sum(li3[0:M]))

### FIXED CODE ###

N,M = (map(int, input().split()))
li = [list(map(int,input().split())) for i in range(N)]

li.sort()

li3 = []
for j in range(len(li)):
    li3.extend([li[j][0]]*li[j][1])
    if len(li3)>M:
        break
print(sum(li3[0:M]))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

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

    for i in range(q):
        query = input().split()
        
        # query 1
        if query[0] == '1':
            s = s[::-1]
        
        # query 2
        else:
            # Fi = 1
            if query[1] == '1':
                s = query[2] + s
            # Fi = 2
            else:
                s = s + query[2]

    print(s)

if __name__ == "__main__":
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-

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

    for i in range(q):
        q_list.append(input())

    r_flg = True
    s_str = ''
    e_str = ''

    for query in q_list:
        # query 1
        if query[0] == '1':
            r_flg = not r_flg
        
        # query 2
        else:
            # Fi = 1
            if query[2] == '1':
                if r_flg:
                    s_str = query[4] + s_str
                else:
                    e_str = e_str + query[4]
            # Fi = 2
            else:
                if r_flg:
                    e_str = e_str + query[4]
                else:
                    s_str = query[4] + s_str

        # print('cont:{}, s:{}, r_flg:{}'.format(i, s, r_flg))

    s = s_str + s + e_str

    if not r_flg:
        s = ''.join(reversed(s))

    print(s)

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

from collections import deque
import collections

n,x,y = map(int,input().split()) 

connect=[[i-1,i+1] for i in range(1,n-1)]
connect.insert(0,[1])
connect.append([n-2])
connect[x-1].append(y-1)
connect[y-1].append(x-1)

dist_from_i = []

for i in range(0,n):
    
    d=0
    dist = [10**6]*n
    
    dq=deque()
    dq.append([i,d])
    dist[i]=d
    
    while len(dq):
        
        x,d = dq.popleft()
                
        for nextx in connect[x]:
            if d<dist[nextx]:
                dq.append([nextx,d+1])
                dist[nextx] = d+1
                
    dist_from_i.append(dist)
            
    c = collections.Counter(sum(dist_from_i,[]))

for k in range(1,n):
    print(c[k]//2)
    

### FIXED CODE ###

n,x,y = map(int,input().split()) 

dist = [0]*n

for i in range(0,n-1):
    for j in range(i,n):
        
        #xy使わない距離
        dist1 = j-i
        
        #xy使う距離
        dist2 = abs((x-1) - i) + 1 + abs((y-1) - j)
        
        
        # print(i,j,dist1,dist2)
        
        #最短距離
        dist_min = min(dist1,dist2)
        
        dist[dist_min] += 1
        
for k in range(1,n):
    print(dist[k])
### BUGGY CODE ###

from numpy import*
c=zeros((50,50),int_)
r=0
for a in[*open(0)][1:]:
  a=round(float(a)*1e9)
  y=0
  while a%5<1:
    a//=5
    y+=1
  x=int(log2(a&-a))
  r+=sum(c[max(0,18-x):,max(0,18-y):])
  c[x][y]+=1
print(r)

### FIXED CODE ###

c=[[0]*50for _ in range(50)]
r=0
for a in[*open(0)][1:]:
  a=round(float(a)*10**9)
  x=y=0
  while a%2<1:
    a//=2
    x+=1
  while a%5<1:
    a//=5
    y+=1
  r+=sum(sum(d[max(0,18-y):])for d in c[max(0,18-x):])
  c[x][y]+=1
print(r)
### BUGGY CODE ###

import numpy as np

h, w, k = map(int, input().split())
s = []
for i in range(h):
    string = input()
    temp = []
    for j in range(w):
        temp.append(int(string[j]))
    s.append(temp)

s_arr = np.array(s)

ans = 10**9
for i in range(2**(h-1)):
    bin_str = format(i, '0'+str(h-1)+'b')
    kouryo = np.array([[0 for _ in range(w)]])
    cnt = 0
    start = 0
    for j in range(h-1):
        if bin_str[j] == '1':
            cnt += 1
            kouryo = np.concatenate((kouryo, s_arr[start:j+1].sum(axis=0, keepdims=True)), axis=0)
            start=j+1
    kouryo = np.concatenate((kouryo, s_arr[start:].sum(axis=0, keepdims=True)), axis=0)

    if np.any(kouryo>k): continue

    wa = np.array([0 for _ in range(len(kouryo))])
    for j in range(w):
        wa = wa + kouryo[:, j]
        if np.any(wa>k):
            cnt += 1
            wa = kouryo[:, j]
    ans = min(ans, cnt)
print(ans)

### FIXED CODE ###

import numpy as np

h, w, k = map(int, input().split())
s = []
for i in range(h):
    string = input()
    temp = []
    for j in range(w):
        temp.append(int(string[j]))
    s.append(temp)

s_arr = np.array(s)

ans = 10**9
for i in range(2**(h-1)):
    bin_str = format(i, '0'+str(h-1)+'b')
    kouryo = np.array([[0 for _ in range(w)]])
    cnt = 0
    start = 0
    for j in range(h-1):
        if bin_str[j] == '1':
            cnt += 1
            kouryo = np.concatenate((kouryo, s_arr[start:j+1].sum(axis=0, keepdims=True)), axis=0)
            start=j+1
    kouryo = np.concatenate((kouryo, s_arr[start:].sum(axis=0, keepdims=True)), axis=0)

    if cnt > ans: continue
    if np.any(kouryo>k): continue

    wa = np.array([0 for _ in range(len(kouryo))])
    for j in range(w):
        wa += kouryo[:, j]
        if np.max(wa)>k:
            cnt += 1
            if cnt > ans: break
            wa = kouryo[:, j]
    ans = min(ans, cnt)
print(ans)
### BUGGY CODE ###

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

in_p = []
in_y = []
p = []

for i in range(n):
    p.append([])

for i in range(m):
    a,b = map(int,input().split())
    in_p.append(a)
    in_y.append(b)
    p[a-1].append(b)  

for i in range(n):
    p[i].sort()

for i in range(m):
    year=str(in_p[i]).zfill(6)
    a = p[in_p[i]-1].index(in_y[i]) + 1
    num=str(a).zfill(6)
    print("{0}{1}".format(year,num))



### FIXED CODE ###

import copy

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

cnt = [0]*(10**5+4)

yy = []
yp = []
for _ in range(m):
    a,b = map(int,input().split())
    a,b = b,a
    yy.append([a,0])
    yp.append([a,b])

inlist = copy.deepcopy(yp)
yp.sort()
yy = dict(yy)

for i in range(m):
    cnt[yp[i][1]]+=1
    yy[yp[i][0]] = cnt[yp[i][1]]

for key,value in inlist:
    print("{:06}{:06}".format(value,yy[key]))