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

def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

from collections import defaultdict
n=n0()
a=[0]
a.extend(n1())

m1=[i+a[i] for i in range(n+1)]
m2=[j-a[j] for j in range(n+1)]

d1=defaultdict(list)
d2=defaultdict(list)
for i in range(1,n+1):
    d1[m1[i]].append(i)
    d2[m2[i]].append(i)

ans=0
for i in d1:
    if len(d2[i])>0:
        for k in d1[i]:
            ans+=len([h for h in d2[i] if h>k])
print(ans)

### FIXED CODE ###

def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

from collections import defaultdict
n=n0()
a=[0]
a.extend(n1())

m1=[i+a[i] for i in range(n+1)]
m2=[j-a[j] for j in range(n+1)]

d1=defaultdict(list)
d2=defaultdict(list)
for i in range(1,n+1):
    d1[m1[i]].append(i)
    d2[m2[i]].append(i)

ans=0
for i in d1:
    ans+=len(d1[i])*len(d2[i])
            
print(ans)
### BUGGY CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
b=[]
count=0

for i in a: 
    if i not in b:
        b.append(i)

for i in b:
    if a.count(i)%2==1:
        count=count+1

print(count)


### FIXED CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
b=[]

m=0
count=[0 for i in range(n)]
count[m]=1

ans_count=0
a.sort()

for i in range(n-1):
    if a[m]==a[i+1]:
        count[m]=count[m]+1
    else:
        m=i+1
        count[m]=1

for i in range(n):
     ans_count=ans_count+count[i]%2

print(ans_count)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
dup = [i for i in set(A) if A.count(i) > 1]
if dup:
  print("NO")
else:
  print("YES")

### FIXED CODE ###

def has_duplicates(seq):
    return len(seq) != len(set(seq))
    
N = map(int,input())
A = list(map(int,input().split()))
print("NO" if has_duplicates(A) else "YES")
### BUGGY CODE ###

k = int(input())

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

s = 0
for h in range(1, k+1):
    for j in range(1, k+1):
        for k in range(1, k+1):
            s = s + gcd(gcd(h, j), gcd(h, k))

print(s)

### FIXED CODE ###

k = int(input())
l = [1, 9, 30, 76, 141, 267, 400, 624, 885, 1249, 1590, 2208, 2689, 3411, 4248, 5248, 6081, 7485, 8530, 10248, 11889, 13687, 15228, 17988, 20053, 22569, 25242, 28588, 31053, 35463, 38284, 42540, 46581, 50893, 55362, 61824, 65857, 71247, 76884, 84388, 89349, 97881, 103342, 111528, 120141, 128047, 134580, 146316, 154177, 164817, 174438, 185836, 194157, 207927, 218812, 233268, 245277, 257857, 268182, 288216, 299257, 313635, 330204, 347836, 362973, 383709, 397042, 416448, 434025, 456967, 471948, 499740, 515581, 536073, 559758, 583960, 604833, 633651, 652216, 683712, 709065, 734233, 754734, 793188, 818917, 846603, 874512, 909496, 933081, 977145, 1006126, 1041504, 1073385, 1106467, 1138536, 1187112, 1215145, 1255101, 1295142, 1342852, 1373253, 1422195, 1453816, 1502376, 1553361, 1595437, 1629570, 1691292, 1726717, 1782111, 1827492, 1887772, 1925853, 1986837, 2033674, 2089776, 2145333, 2197483, 2246640, 2332104, 2379085, 2434833, 2490534, 2554600, 2609625, 2693919, 2742052, 2813988, 2875245, 2952085, 3003306, 3096024, 3157249, 3224511, 3306240, 3388576, 3444609, 3533637, 3591322, 3693924, 3767085, 3842623, 3912324, 4027884, 4102093, 4181949, 4270422, 4361548, 4427853, 4548003, 4616104, 4718640, 4812789, 4918561, 5003286, 5131848, 5205481, 5299011, 5392008, 5521384, 5610705, 5739009, 5818390, 5930196, 6052893, 6156139, 6239472, 6402720, 6493681, 6623853, 6741078, 6864016, 6953457, 7094451, 7215016, 7359936, 7475145, 7593865, 7689630, 7886244, 7984165, 8130747, 8253888, 8403448, 8523897, 8684853, 8802826, 8949612, 9105537, 9267595, 9376656, 9574704, 9686065, 9827097, 9997134, 10174780, 10290813, 10493367, 10611772, 10813692]
print(l[k-1])
### BUGGY CODE ###

N=int(input())
A=[i for i in map(int,input().split())]
k=0
while len(A)!=1:
    if A[1]%A[0]!=0:
        A[1]=A[1]%A[0]
        k+=1
    else:
        A.remove(A[1])
    A.sort()
print(A[0])


### FIXED CODE ###

N = int(input())
A = [int(_) for _ in input().split()]
m = min(A)
while m > 0:
    for i in range(0,len(A)):
        if A[i] != m:
            A[i] = A[i]%m
    z = A.count(0)
    A = sorted(A)[z:]
    m = A[0]
    if m == 1:
        break
    else:
        if [_%m for _ in A] == [0]*len(A):
            break
print(m)
### BUGGY CODE ###

# AtCoder Beginner Contest 162: C (2020/04/12)
import math
K = int(input())
S = 0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            x = [a, b, c]
            ans = x[0]
            for i in range(1, 3):
                ans = math.gcd(ans, x[i])
            S = S + ans
print(S)

### FIXED CODE ###

# AtCoder Beginner Contest 162: C (2020/04/12)
import math
K = int(input())
S = 0
for a in range(1,K+1):
    for b in range(a,K+1):
        for c in range(b,K+1):
            x = [a, b, c]
            ans = x[0]
            for i in range(1, 3):
                ans = math.gcd(ans, x[i])
            if a == b and b == c:
                S = S + ans
            elif a == b or b == c:
                S = S + 3*ans
            else:
                S = S + 6*ans
print(S)
### BUGGY CODE ###

from copy import deepcopy
H, W, K = map(int, input().split())
board = [[0]*(W+1) for _ in range(H+1)]
for i in range(1,H+1):
    board[i] = list(map(int, list(input())))+[0]
def drop(board_copy):
    change = True
    score = 0
    p = 0
    while change:
        change = False
        for i in range(2,H+1):
            ser = 1
            for j in range(1,W+1):
                if board_copy[i][j]>0 and board_copy[i][j]==board_copy[i][j-1]:
                    ser += 1
                else:
                    if ser>=K:
                        score += 2**p*board_copy[i][j-1]*ser
                        change = True
                        for k in range(i,0,-1):
                            board_copy[k][j-ser:j] = board_copy[k-1][j-ser:j]
                    ser = 1
        p += 1
    return score
ans = 0
for h in range(2,H+1):
    for w in range(W):
        board_copy = deepcopy(board)
        for k in range(h,0,-1):
            board_copy[k][w] = board[k-1][w]
        ans = max(ans,drop(board_copy))
print(ans)

### FIXED CODE ###

h, w, k  = map(int, input().split())

puyo_orig = [list(map(int, list(input()))) for _ in range(h)]

import copy
mx = 0
for i1 in range(h):
    for i2 in range(w):
        puyo = copy.deepcopy(puyo_orig)
        puyo[i1][i2] = -1
        p = 0
        fin = 0
        turn = 0
        while fin==0:
            #[print(*puyo[i]) for i in range(h)]
            fin = 1
            
            for i in range(w):
                d_fin = 0
                while d_fin==0:
                    d_fin = 1
                    for j in range(h-1, 0, -1):
                        if puyo[j][i]==-1 and puyo[j-1][i]>0:
                            puyo[j][i] = puyo[j-1][i]
                            puyo[j-1][i] = -1
                            d_fin = 0
                            
            for i in range(h):
                cnt = 1
                for j in range(1, w):
                    if puyo[i][j-1] == puyo[i][j] and puyo[i][j]>0:
                        cnt += 1
                    else:
                        if cnt>=k:
                            p += cnt * puyo[i][j-1] * 2**turn
                            for k2 in range(cnt):
                                puyo[i][j-k2-1] = -1
                                fin = 0
                        cnt = 1
                    if j==w-1:
                        if cnt>=k:
                            p += cnt * puyo[i][j-1] * 2**turn
                            for k2 in range(cnt):
                                puyo[i][j-k2] = -1
                                fin = 0
            turn += 1
        if p>mx:
            mx=p
            
print(mx)
### BUGGY CODE ###

N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

if N == 1:
    print(K)
else:
    mod = 1000000007
    d = {i: set() for i in range(1, N+1)}
    for i, j in links:
        d[i].add(j)
        d[j].add(i)
    b = len(d[1])
    if K - 1 < b:
        print(0)
    else:
        ans = K * perm(K - 1, b)
        root = d[1]
        for i in d[1]:
            d[i].remove(1)
        a = K - 2
        while True:
            children = set()
            for i in list(root):
                for j in d[i]:
                    d[j].remove(i)
                b = len(d[i])
                if a < b:
                    print(0)
                    break
                if b == 0:
                    continue
                ans *= perm(a, b)
                children |= d[i]
            else:
                if len(children) == 0:
                    print(ans % mod)
                    break
                root = children
                continue
            break

### FIXED CODE ###

N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
A = max(a)
t = -1
tt = 0
for i in range(n):
    if t < a[i]:
        t = a[i]
        tt = i
a.pop(tt)
x = 0
y = A
z = 0
for i in range(1, A):
    x += 1
    y -= 1
    if x >= y:
        z = A - x
        break
d = float('INF')
da = 0
for i in range(n - 1):
    if d > abs(a[i] - z):
        da = a[i]
        d = da - z
print(A, da)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
A = max(a)
t = -1
tt = 0
for i in range(n):
    if t < a[i]:
        t = a[i]
        tt = i
a.pop(tt)
# print(a)
z = A / 2
d = float('INF')
da = 0
for i in range(n - 1):
    # print(d, abs(a[i] - z))
    if d > abs(a[i] - z):
        da = a[i]
        d = abs(da - z)
print(A, da)
### BUGGY CODE ###

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

N = int(input().strip())
A_list = list(map(int, input().rstrip().split()))
#-----

# A_index[i] = ( value of A , index of A)
A_index = [ (A_list[i], i) for i in range(len(A_list)) ]
A_index.sort(reverse=True)


# dp[left][right] = score
dp = [ [0]*(N+1) for _ in range(N+1) ]


for L in range(N):
    for R in range(N-L):
        i = L + R
        append_L = dp[L][R] + A_index[i][0] * abs(L - A_index[i][1])
        append_R = dp[L][R] + A_index[i][0] * abs((N-1-R) - A_index[i][1])
        
        dp[L+1][R] = max(dp[L+1][R], append_L)
        dp[L][R+1] = max(dp[L][R+1], append_R)


ans = max( [ dp[i][N-i] for i in range(N+1)] )
print(ans)


### FIXED CODE ###

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

N = int(input().strip())
A_list = list(map(int, input().rstrip().split()))
#-----

# A_index[i] = ( value of A , index of A)
A_index = [ (A_list[i], i) for i in range(len(A_list)) ]
A_index.sort(reverse=True)


# dp[left][right] = score
dp = [ [0]*(N+1) for _ in range(N+1) ]


for L in range(N):
    for R in range(N-L):
        i = L + R
        append_L = dp[L][R] + A_index[i][0] * abs(L - A_index[i][1])
        append_R = dp[L][R] + A_index[i][0] * abs((N-1-R) - A_index[i][1])
        
        dp[L+1][R] = max(dp[L+1][R], append_L)
        dp[L][R+1] = max(dp[L][R+1], append_R)


ans = max( [ dp[i][N-i] for i in range(N+1)] )
print(ans)
### BUGGY CODE ###

def f(x):
    return ord(x) - ord('a')


N = int(input())
cnts = [[0] * 26 for _ in range(N)]

for i in range(N):
    for c in input():
        cnts[i][f(c)] += 1

res = 0
for i in range(N):
    for j in range(i + 1, N):
        chk = 1
        for k in range(26):
            if cnts[i][k] != cnts[j][k]:
                chk = 0
                break
        res += chk
print(res)

### FIXED CODE ###

def f(x):
    return 10 ** (ord(x) - ord('a') + 1)


import math


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


from collections import Counter

N = int(input())
counter = Counter()
for i in range(N):
    counter[sum([f(i) for i in input()])] += 1
res = 0
for v in counter.values():
    if v > 1:
        res += combinations_count(v, 2)
print(res)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(N: int):
    p = 1
    for i in range(1,N+1):
        p *= i
    print(p % MOD)

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    solve(N)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(N: int):
    p = 1
    for i in range(1,N+1):
        p = p * i % MOD
    print(p)

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    solve(N)

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

#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

def func():
    N = int(input())

    A = list(map(int, input().split()))
    P = [[(A[0], 0), (0, 0)] for i in range(2 ** N)]

    for i in range(1, 2 ** N):
        if (A[i], i) > P[i][0]:
            P[i][1] = P[i][0]
            P[i][0] = (A[i], i)
        elif (A[i], i) > P[i][1]:
            P[i][1] = (A[i], i)
        for j in range(N):
            if (i & (1 << j)) == 0:
                index = i + (1 << j)
                for k in range(2):
                    if P[i][k] in P[index]:
                        continue
                    if P[i][k] > P[index][0]:
                        P[index][1] = P[index][0]
                        P[index][0] = P[i][k]
                    elif P[i][k] > P[index][1]:
                        P[index][1] = P[i][k]
    ans = 0
    for i in range(1, 2 ** N):
        ans = max(ans, P[i][0][0] + P[i][1][0])
        print(ans)
    #print(P)

func()

### FIXED CODE ###

#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

def func():
    N = int(input())

    A = list(map(int, input().split()))
    P = [[(A[0], 0), (0, 0)] for i in range(2 ** N)]

    for i in range(1, 2 ** N):
        Ai = A[i]
        Pi = P[i]
        if (Ai, i) > Pi[0]:
            Pi[1] = Pi[0]
            Pi[0] = (Ai, i)
        elif (Ai, i) > Pi[1]:
            Pi[1] = (Ai, i)
        for j in range(N):
            if (i & (1 << j)) == 0:
                Pindex = P[i + (1 << j)]
                for k in range(2):
                    if Pi[k] > Pindex[0]:
                        Pindex[1] = Pindex[0]
                        Pindex[0] = Pi[k]
                    elif Pi[k] > Pindex[1] and Pi[k] != Pindex[0]:
                        Pindex[1] = Pi[k]
    ans = 0
    for i in range(1, 2 ** N):
        ans = max(ans, P[i][0][0] + P[i][1][0])
        print(ans)
    #print(P)

func()
### BUGGY CODE ###

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


x = int(input().strip())
abs_x = abs(x)

def X(a, b):
    return a**5 - b**5

def X_plus(a, b):
    return a**5 + b**5

a = 2
b = 1

while True:
    #print(a, b)
    if X(a, b) == abs_x:
        if x < 0:
            a = -a
            b = -b
        print(a,b)
        exit()

    if (a-b) > 1:
        b += 1
    elif a-b == 1:
        if X(a, b) < abs_x:
            a += 1
        else:
            #print("引き算では無理")
            break
    else:
        print("Error")
        exit()

#print("足し算を判定")

a = 0
b = 0

while True:
    if X_plus(a, b) == abs_x:
        b = -b
        if x < 0:
            a = -a
            b = -b
        print(a, b)
        exit()

    if X_plus(a+1, b) <= abs_x:
        a += 1
        b = 0
    else:
        if X_plus(a, b+1) <= abs_x:
            b += 1
        else:
            a -= 1
            b -= 1

### FIXED CODE ###

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


x = int(input().strip())
abs_x = abs(x)

def X(a, b):
    return a**5 - b**5

def X_plus(a, b):
    return a**5 + b**5

a = -118
b = -119


for a in range(-118, 119):
    #print(a)
    for b in range(-119, 118):
        #print(b)
        if X(a,b) == x:
            print(a,b)
            exit()

#print("not found")
### BUGGY CODE ###

N = int(input())
x=0
t=0
n=0
pre_t=0
pre_n=0
for i in range(N):
    now_t,now_n = map(int,input().split())
    t = now_t
    n = now_n
    while(pre_t > t or pre_n > n):
        t += now_t
        n += now_n
    pre_t = t
    pre_n = n
    x = t+n
print(x)

### FIXED CODE ###

import math
N = int(input())
x=0
t=0
n=0
pre_t=1
pre_n=1
for i in range(N):
    t,n = map(int,input().split())
    if(pre_t > t or pre_n > n):
        mul = max(-(-pre_t//t),-(-pre_n//n))
        t *= mul
        n *= mul
    pre_t = t
    pre_n = n
    x = t+n
print(x)
### BUGGY CODE ###

import numpy as np

N, K, Q=list(map(int,input().split()))
points = K * np.ones(N)
for i in range(Q):
    A = int(input()) - 1
    points -= 1
    points[A] += 1
for i in range(N):
    if points[i] > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

import numpy as np

N, K, Q=list(map(int,input().split()))
points = K * np.ones(N)
A_list = np.zeros(Q)

for i in range(Q):
    A = int(input()) - 1
    A_list[i] = A

points = points - Q
for i in A_list:
    points[int(i)] += 1

for i in range(N):
    if points[i] > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n=int(input())
a=[]
b=[]
ans=0
for i in range(n):
  s=list(input())
  s.sort()
  a.append(str(s))
b=set(a)
for x in b:
  c=a.count(x)
  if c>1:
    ans+=c*(c-1)//2
print(ans)

### FIXED CODE ###

n=int(input())
a=[]
ans=0
for i in range(n):
  s=list(input())
  s.sort()
  a.append(str(s))
a.sort()
y=''
w=0
c=[]
for x in a:
  if y==x:
    w+=1
  else:
    c.append(w)
    w=1
  y=x
c.append(w)
c=c[1:]
for x in c:
  ans+=x*(x-1)//2
print(ans)
### BUGGY CODE ###

n = int(input())
a = tuple(int(x) for x in input().split())

def fac(x):
 fact = 1
 for f in range(1, x+1):
  fact *= f
 return fact

def comb(n, r):
 return fac(n) // (fac(r) * fac(n-r))

maxi = a[:2]
for i in a:
 for j in a:
  if i < j: continue
  maxi = (i, j) if comb(*maxi) < comb(i, j) else maxi
print(*maxi)


### FIXED CODE ###

N = int(input())
a = sorted(int(x) for x in input().split())

def hoge(n, r):
 return n * (min(n-r, r))

n = max(a)
ans = (n, a[0])
for i in a[1:]:
 ans = (n, i) if hoge(*ans) < hoge(n, i) else ans
print(*ans)
### BUGGY CODE ###

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

score = 1
for i in range(k):
    score *= a[i]
ans = [score]

for i in range(k, n):
    score = score * a[i] // a[i-k]
    ans.append(score)

for i in range(n-k):
    if ans[i] < ans[i+1]:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

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

for i in range(k, n):
    if a[i-k] < a[i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import numpy as np
N,Q = (int(X) for X in input().split())
S = input()
AIndex = np.array([Ind for Ind,Str in enumerate(S) if S[Ind:Ind+2]=='AC'])
if len(AIndex)==0:
    print('\n'.join(['0']*Q))
else:
    for T in range(0,Q):
        L,R = (int(X) for X in input().split())
        print(sum(((L-1)<=AIndex)&((R-1)>=AIndex+1)))

### FIXED CODE ###

N,Q = (int(X) for X in input().split())
S = input()
T = [0]*(N+1)
for I in range(0,N):
     T[I+1] = T[I] + (S[I:I+2]=='AC')
for J in range(0,Q):
    L,R = (int(X)-1 for X in input().split())
    print(T[R]-T[L])
### BUGGY CODE ###

def solve(Mi,i):
	if Mi == 0: return True
	if i < n and Mi > 0:
		r1 = solve(Mi-A[i],i+1)
		r2 = solve(Mi,i+1)
		if r1: return r1
		if r2: return r2
n = input()
A = map(int,raw_input().split())
q = input()
M = map(int,raw_input().split())
for Mi in M:
	print "yes" if solve(Mi,0) else "no"

### FIXED CODE ###

def solve(Mi,i):
	if Mi == 0: return True
	if i < n and A[i] <= Mi <= sum(A[i:]):
		r1 = solve(Mi-A[i],i+1)
		if r1: return r1
		r2 = solve(Mi,i+1)
		if r2: return r2
n = input()
A = sorted(map(int,raw_input().split()))
q = input()
M = map(int,raw_input().split())
for Mi in M:
	print "yes" if solve(Mi,0) else "no"
### BUGGY CODE ###

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

l = []
AA = A.copy()

for k in range(N):
    Amin = min(AA)
    #print(Amin)
    a = A.index(Amin)
    l.append(a + 1)
    AA.remove(Amin)
print(*l)

### FIXED CODE ###

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

l = [0] * N

for i, a in enumerate(A):
    l[int(a - 1)] = str(i + 1)
print(*l)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import deque
N,M=map(int,input().split())
table=[[] for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    table[a].append(b)
    table[b].append(a)
Q=int(input())
X=[[int(i) for i in input().split()] for i in range(Q)]
color=[0]*N
def f(s,d,v):
    H=deque()
    H.append((0,s))
    color[s]=v
    visit=[False]*N
    visit[s]=True
    while H:
        dis,pt=H.popleft()
        if dis>=d:
            continue
        for x in table[pt]:
            if not visit[x]:
                color[x]=v
                visit[x]=True
                H.append((dis+1,x))
    return
for v,d,c in X:
    v=v-1
    f(v,d,c)
    #print(color)
for i in color:
    print(i)



### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque
N,M=map(int,input().split())
table=[[] for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    table[a].append(b)
    table[b].append(a)
Q=int(input())
X=[[int(i) for i in input().split()] for i in range(Q)]
color=[0]*Q
dp=[[-1]*N for i in range(11)]
for i in range(Q-1,-1,-1):
    v, d, c=X[i]
    v=v-1
    color[i]=c
    dp[d][v]=max(dp[d][v],i)

for d in range(10,0,-1):
    for x in range(N):
        for y in table[x]:
            dp[d-1][y]=max(dp[d][x],dp[d-1][y])
for i in range(N):
    s=-1
    for d in range(11):
        s=max(s,dp[d][i])
    if s==-1:
        print(0)
    else:
        print(color[s])
### BUGGY CODE ###

n, m = map(int, input().split())
cs = []
ps = {}
for _ in range(m):
  p, y = map(int, input().split())
  cs.append([y, p])
css = sorted(cs)
for c in css:
  if c[1] in ps:
    ps[c[1]].append(c[0])
  else:
    ps[c[1]] = [c[0]]
[print('{:06}{:06}'.format(c[1], ps[c[1]].index(c[0])+1))for c in cs]

 
  
  


### FIXED CODE ###

n, m = map(int, input().split())
cs = []
cd = {}
ps = {}
for _ in range(m):
  p, y = map(int, input().split())
  cs.append([p, y])
  if p in ps:
    ps[p].append(y)
  else:
    ps[p] = [y]
    
for p in ps:
  v = sorted(ps[p])
  for i, y in enumerate(v):
    cd[y] = i + 1
[print('{:06}{:06}'.format(c[0], cd[c[1]])) for c in cs]