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

import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

S = input()
N = len(S)

# dp[i][k]: i桁目までのkで割った余りの数
dp = create_grid(N+1, 13)

dp[0][0] = 1 # 0桁目

mul = 1
for i in range(N):
    c = S[N-i-1]
    if c == "?":
        v = range(10)
    else:
        v = [int(c)]
    for vi in v:
        for j in range(13):
            amari = (vi*mul + j) % 13
            dp[i+1][amari] += dp[i][j]
    
    for j in range(13):
        dp[i+1][j] %= MOD

    mul *= 10

print(dp[N][5])



### FIXED CODE ###

import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# field[H][W]
def create_grid(H, W, value = 0):
    return [[ value for _ in range(W)] for _ in range(H)]

########

S = input()
N = len(S)

# dp[i][k]: i桁目までのkで割った余りの数
dp = create_grid(N+1, 13)

dp[0][0] = 1 # 0桁目

s = [1]
for i in range(N):
  s.append((s[-1]*10)%13)

for i in range(N):
    c = S[N-i-1]
    if c == "?":
        v = range(10)
    else:
        v = [int(c)]
    for vi in v:
        for j in range(13):
            amari = (vi*s[i] + j) % 13
            dp[i+1][amari] = (dp[i][j] + dp[i+1][amari]) % MOD

print(dp[N][5])
### BUGGY CODE ###

def main():
    N, M = map(int, input().split())
    g = [[] for _ in range(N)]

    A, B = [0]*M, [0]*M
    for i in range(M):
        A[i], B[i] = map(int, input().split())
        g[A[i]-1].append(B[i]-1)
        g[B[i]-1].append(A[i]-1)

    ans_list = [-1] * N

    queue = [0]
    seen = [False]*N

    while queue:
        qi = queue.pop(0)
        # qi から 1 遠い頂点が gi
        for gi in g[qi]:
            if seen[gi] == False:
                queue.append(gi)
                if ans_list[gi] == -1:
                    ans_list[gi] = qi
                    seen[gi] = True
        if len(set(seen)) == 1:
            break

    print("Yes")
    for ans in ans_list[1:]:
        print(ans+1)  # 1-index に直す

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N, M = map(int, input().split())
    g = [[] for _ in range(N)]

    A, B = [0]*M, [0]*M
    for i in range(M):
        A[i], B[i] = map(int, input().split())
        g[A[i]-1].append(B[i]-1)
        g[B[i]-1].append(A[i]-1)

    ans_list = [-1] * N

    queue = [0]
    seen = [False]*N

    while queue:
        qi = queue.pop(0)
        # qi から 1 遠い頂点が gi
        for gi in g[qi]:
            if seen[gi] == False:
                queue.append(gi)
                if ans_list[gi] == -1:
                    ans_list[gi] = qi
                    seen[gi] = True

    print("Yes")
    for ans in ans_list[1:]:
        print(ans+1)  # 1-index に直す

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

# -*- coding: utf-8 -*-
N = int(input())
S = str(input())

ans_all_black = 0   #全て黒くする方の解
ans_all_white = 0   #全て白くする方の解
ans_right_black = 100 #右をすべて黒くする解

#  #:黒
#  .:白
#黒の右隣に白が来ないようにしたい
#∴すべて黒
#　すべて白
#　白連続の後に黒連続
#のどれかが完成形

for i in range(N):
  if S[i]!="#":
    ans_all_black = ans_all_black + 1
  if S[i]!=".":
    ans_all_white = ans_all_white + 1
  
  #print(i,":",ans_all_white,":",end="")
  
  temp_right_black = 0
  
  if i+1 <N:
    for j in range(i+1,N,1):
      if S[j]==".":
         temp_right_black = temp_right_black+1

    #print(temp_right_black)

    if temp_right_black+ans_all_white<ans_right_black:
      ans_right_black = temp_right_black + ans_all_white
    
    

ans = min(ans_all_white,ans_all_black,ans_right_black)
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
N = int(input())
S = str(input())

ans_all_black = 0   #全て黒くする方の解
ans_all_white = 0   #全て白くする方の解
ans_right_black = 100 #右をすべて黒くする解

#  #:黒
#  .:白
#黒の右隣に白が来ないようにしたい
#∴すべて黒
#　すべて白
#　白連続の後に黒連続
#のどれかが完成形

#一度白の全数を調べる
all_white = 0
left_white=[]

for i in range(N):
  if S[i]==".":
    all_white  = all_white + 1
    if i==0:
      left_white.append(1) 
    else:
      left_white.append(left_white[i-1]+1) 
  else:
    if i==0:
      left_white.append(0) 
    else:
      left_white.append(left_white[i-1])
    
ans_all_black = all_white     #全数黒にするには白をすべてひっくり返す
ans_all_white = N - all_white #全数白にするには黒をすべてひっくり返す＝すべての中で白出ないものをひっくり返す

#print("all_black:",ans_all_black)
#print("all_white:",ans_all_white)

ans_right_black = N

#右側全黒
for i in range(N):
  #print(i,":",i + 1 - left_white[i],":",ans_all_black - left_white[i])
  #i+1文字目において:左を全部白にするのに必要な塗り数:右を全部黒にするのに必要な塗り数
  ans_right_black = min(i + 1 - left_white[i] + ans_all_black - left_white[i] , ans_right_black)
  
ans = min(ans_all_white,ans_all_black,ans_right_black)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []
    for _ in range(n):
        v, w = LI()
        V.append(v)
        W.append(w)
    
    q = I()
    vl = []
    maxL = 0
    for _ in range(q):
        v, l = LI()
        maxL = max(maxL, l)
        vl.append([v,l])
    
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1) for _ in range(m + 1)]
    
    for i in range(1, m+1):
        v, w = V[i-1], W[i-1]
        for j in range(maxL+1):
            if j < w:
                dp[i][j] = dp[i>>1][j]
            else:
                dp[i][j] = max(dp[i>>1][j], dp[i>>1][j - w] + v)
    
    for i in range(q):
        v, L = vl[i]
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        tmp = v
        v_ = []
        w_ = []
        while tmp > m:
            v_.append(V[tmp-1])
            w_.append(W[tmp-1])
            tmp >>= 1
            cnt += 1
        ret = dp[tmp][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_tmp[b] = w_tmp[b - lsb] + w_[l-1]
            if w_tmp[b] <= L:
                v_tmp[b] = v_tmp[b - lsb] + v_[l-1]
                ret = max(ret, v_tmp[b] + dp[tmp][L - w_tmp[b]])
        print(ret)
    return

if __name__ == "__main__":
    main()

### FIXED CODE ###

#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []

    maxL = 10**5
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1)]
    
    for i in range(n):
        v, w = LI()
        if i <= m:
            d_ = dp[(i+1)>>1][:]
            for j in range(w, maxL+1)[::-1]:
                d_[j] = max(d_[j], d_[j - w] + v)
            dp.append(d_)
        V.append(v)
        W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        v_ = []
        w_ = []
        while v > m:
            v_.append(V[v-1])
            w_.append(W[v-1])
            v >>= 1
            cnt += 1
        ret = dp[v][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_t = w_tmp[b - lsb] + w_[l-1]
            w_tmp[b] = w_t
            if w_t <= L:
                v_t = v_tmp[b - lsb] + v_[l-1]
                v_tmp[b] = v_t
                ret = max(ret, v_t + dp[v][L - w_t])
        print(ret)
    return

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

from bisect import bisect_left, bisect_right

def solve():
    N, M = map(int, input().split())
    As = list(map(int, input().split()))

    As.sort()

    def isOK(x):
        num = 0
        for k, A in enumerate(As, start=1):
            i = bisect_left(As, x-A)
            num += N-i
            if num >= M:
                return True
            elif num + (N-k)*N < M:
                return False
        return num >= M

    ng, ok = 2*10**5+1, 0
    while abs(ok-ng) > 1:
        mid = (ng+ok) // 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid
#    print('ok:', ok)

    scores = []
    for A in As:
        i = bisect_right(As, ok-A)
        for B in As[i:]:
            scores.append(A+B)
#    print('scores:', scores, len(scores))

    ans = sum(scores) + ok*(M-len(scores))
    print(ans)


solve()


### FIXED CODE ###

from bisect import bisect_left, bisect_right

maxA = 10**5

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

As.sort()

def isOK(v):
    num = 0
    for A in As:
        i = bisect_left(As, v-A)
        num += N-i
    return num >= M

ng, ok = 2*maxA+1, 0
while abs(ok-ng) > 1:
    mid = (ng+ok) // 2
    if isOK(mid):
        ok = mid
    else:
        ng = mid

accRevAs = [As[-1]]
for A in reversed(As[:-1]):
    accRevAs.append(accRevAs[-1]+A)
accRevAs.reverse()

v = ok
ans = 0
numGt = 0
#numEq = 0
for A in As:
#    iL = bisect_left(As, v-A)
    iR = bisect_right(As, v-A)
    if iR < N:
        ans += accRevAs[iR] + A*(N-iR)
    numGt += N-iR
#    numEq += iR-iL

ans += v * (M-numGt)
print(ans)
### BUGGY CODE ###

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

ans = 0
for i in range(n-1):
    count = 0
    j = i+1
    while True:
        if j==n:
            break
        elif lst[j-1]>=lst[j]:
            count += 1
            j += 1
        else:
            break
    ans = max(ans, count)

print(ans)


### FIXED CODE ###

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

ans = 0

i = 0
count = 0
ans = 0
while i != n-1:
    if lst[i]>=lst[i+1]:
        count += 1
        ans = max(ans, count)
    else:
        count = 0
    i += 1

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

k,s = map(int, input().split())
ans = 0

for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z == s:
                ans += 1
print(ans)


### FIXED CODE ###

k,s = map(int, input().split())
ans = 0

for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if 0 <= z <= k:
            ans += 1
print(ans)
### BUGGY CODE ###

(D,),C,*I=[[*map(int,t.split())]for t in open(0)]
s=sum(C)
for d,q in I[D-~D:]:I[d-1+D][0]=q;i,R,P,*L=[0]*29;exec('t=I[i+D][0]-1;P+=s+(~i+L[t])*C[t];R+=I[i][t]-P;i+=1;L[t]=i;'*D);print(R)

### FIXED CODE ###

from numba import njit
from numpy import int64
@njit('i8(i8[:],i8[:])',cache=True)
def func(s,x):
    last=[0]*26
    score=0
    for i,v in enumerate(x,1):
        last[v]=i
        c=0
        for j in range(26):
            c+=s[j]*(i-last[j])
        score=score+s[i*26+v]-c
    return score
def main():
    d,*s=map(int,open(0).read().split())
    s=int64(s)
    x=s[26*-~d:d*27+26]-1
    for d,q in s[27*-~d:].reshape(-1,2):
        x[d-1]=q-1
        print(func(s,x))
main()
### BUGGY CODE ###

import sys


def LS():
    return list(input().split())


S = input()
Q = int(input())
rev = 0
for i in range(Q):
    A = LS()
    if A[0] == "1":
        rev += 1
        rev %= 2
    else:
        if A[1] == "1":
            if rev == 0:
                S = A[2]+S
            else:
                S = S+A[2]
        else:
            if rev == 0:
                S = S+A[2]
            else:
                S = A[2]+S
if rev == 0:
    print(S)
    sys.exit()
else:
    S = list(S)
    S.reverse()
for i in range(len(S)):
    print(S[i], end="")


### FIXED CODE ###

from collections import deque
S = deque(input())
Q = int(input())
reverse = 0
Tlist = []
for i in range(Q):
    Tlist.append(list(input().split()))
    if Tlist[i][0] == str(2):
        if (int(Tlist[i][1])+reverse) % 2 == 0:
            S.append(Tlist[i][2])
        else:
            S.appendleft(Tlist[i][2])
    else:
        if reverse == 1:
            reverse = 0
        else:
            reverse = 1
if reverse == 0:
    print(''.join(S))
else:
    S.reverse()
    print(''.join(S))
### BUGGY CODE ###

from functools import reduce

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
def lcm(a, b): return a * b // gcd(a, b)
def lcm_list(A): return reduce(lcm, A)

MOD = 10**9 + 7

N = int(input())
*A, = map(int, input().split())
L = lcm_list(A)
ans = 0
for a in A:
    ans = (ans + L // a) % MOD
print(ans)

### FIXED CODE ###

from collections import Counter

def extended_euclid(a, b):
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q, r = divmod(m, n)
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, r
    return (x2, y2, n)

def modular_inverse(a, mod):
    x, _, g = extended_euclid(a, mod)
    if g != 1:
        return None # Modular inverse of a does not exist
    else:
        return x % mod

def prime_factorization(n):
    '''
    Trial division.
    Input: 
        n : a positive integer
    Output:
        a dictionary of #(each prime factors) of n,
    '''
    result = []
    app = result.append
    if n < 2:
        return Counter()
    while n % 2 == 0:
        app(2)
        n //= 2
    p = 3
    while p*p <= n:
        while n % p == 0:
            app(p)
            n //= p
        p += 2
    if n > 1:
        app(n)
    return Counter(result)

MOD = 10**9 + 7

N = int(input())
*A, = map(int, input().split())
ans = 0
lcm = {}
for a in A:
    for x, y in prime_factorization(a).items():
        if x not in lcm.keys():
            lcm[x] = y
        else:
            lcm[x] = max(lcm[x], y)
L = 1
for x, y in lcm.items():
    L *= pow(x, y, MOD)
    L %= MOD
for a in A:
    ans += L * modular_inverse(a, MOD)
    ans %= MOD
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

ABS=[abs(a) for a in A]
OK=-max(ABS)**2-1
NG=max(ABS)**2+1

import bisect

while NG-OK>1:
    mid=(OK+NG)//2
    SC=0
    for i in range(N):
        if A[i]>0:
            x=bisect.bisect_left(A,-(-mid//A[i]))
            SC+=max(0,x-i-1)

        elif A[i]<0:
            x=bisect.bisect_right(A,mid//A[i])
            SC+=min(N-i-1,N-x)
        else:
            if mid>0:
                SC+=N-i-1
            else:
                SC+=0

    #print(OK,NG,mid,SC)

    if SC<=K-1:
        OK=mid
    else:
        NG=mid
        
print(OK)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

M=[]
Z=[]
P=[]

for a in A:
    if a<0:
        M.append(-a)
    elif a==0:
        Z.append(a)
    else:
        P.append(a)

M.reverse()

MINUS=len(M)*len(P)
PLUS=len(P)*(len(P)-1)//2+len(M)*(len(M)-1)//2
ZERO=N*(N-1)//2-PLUS-MINUS

if MINUS<K and K<=MINUS+ZERO:
    print(0)
    sys.exit()

if K<=MINUS:
    OK=10**18
    NG=0

    while OK-NG>1:
        mid=(OK+NG)//2

        ANS=0
        NOW=len(P)-1

        for i in range(len(M)):
            while NOW>=0 and mid<M[i]*P[NOW]:
                NOW-=1
            ANS+=len(P)-NOW-1

        if ANS>=K:
            NG=mid

        else:
            OK=mid

    print(-OK)

else:
    OK=0
    NG=10**18
    K-=MINUS+ZERO

    while NG-OK>1:
        mid=(OK+NG)//2

        ANS=0
        NOW=len(P)-1

        for i in range(len(P)):
            while NOW>0 and mid<=P[i]*P[NOW]:
                NOW-=1
            ANS+=max(0,NOW-i)

        NOW=len(M)-1

        for i in range(len(M)):
            while NOW>0 and mid<=M[i]*M[NOW]:
                NOW-=1
            ANS+=max(0,NOW-i)

        if ANS>=K:
            NG=mid

        else:
            OK=mid

    print(OK)
### BUGGY CODE ###

from copy import deepcopy
from operator import mul
from functools import reduce


def cmb(n, r):
    r = min(n - r, r)
    if r == 0:
        return 1
    elif r < 0:
        return 0
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


def main():
    n = int(input())
    As = list(map(int, input().split()))

    for a in As:
        Bs = deepcopy(As)
        Bs.remove(a)
        b_set = set(Bs)
        ans = 0
        for b in b_set:
            a = cmb(Bs.count(b), 2)
            ans += a
        print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import Counter


def main():
    n = int(input())
    arr = list(map(int, input().split()))

    cnt = Counter(arr)
    total = 0
    for key in cnt.keys():
        total += cnt[key]*(cnt[key]-1)//2

    for i in range(n):
        tmp = total
        tmp -= cnt[arr[i]]*(cnt[arr[i]]-1)//2
        tmp += (cnt[arr[i]]-1)*(cnt[arr[i]]-2)//2
        print(tmp)


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

import heapq

N, M = map(int, input().split())
AB = [False]*N
for i in range(N):
    A, B = map(int, input().split())
    AB[i] = (-B, A)

AB.sort(key=lambda x: x[1])
hq = []

ans, ct, idx = 0, 0, 0
for i in range(1, M+1):
    for j in AB[idx:]:
        if j[1] == i:
            heapq.heappush(hq, j)
            ct += 1
        else:
            idx = ct
            break
    if hq:
        B, A = heapq.heappop(hq)
        ans -= B
print(ans)


### FIXED CODE ###

import heapq

N, M = map(int, input().split())
W = [[] for _ in range(100005)]
for i in range(N):
    A, B = map(int, input().split())
    W[A].append(B)

hq = []

ans, ct, idx = 0, 0, 0
for A in range(1, M+1):
    for B in W[A]:
        heapq.heappush(hq, -B)
    if hq:
        B = heapq.heappop(hq)
        ans -= B
print(ans)
### BUGGY CODE ###

n=int(input())
a,b,c=map(int,input().split())
d,e,f=list(map(int,input().split()))
s=[0]*(n+1)
for i in range(a,n+1):
    s[i]=max(s[i],s[i-a]+d-a)
for i in range(b,n+1):
    s[i]=max(s[i],s[i-b]+e-b)
for i in range(c,n+1):
    s[i]=max(s[i],s[i-c]+f-c)
n+=s[-1]
s=[0]*(n+1)
for i in range(d,n+1):
    s[i]=max(s[i],s[i-d]+a-d)
for i in range(e,n+1):
    s[i]=max(s[i],s[i-e]+b-e)
for i in range(f,n+1):
    s[i]=max(s[i],s[i-f]+c-f)
print(s[-1]+n)

### FIXED CODE ###

n=int(input())
a,b,c=map(int,input().split())
d,e,f=list(map(int,input().split()))
s=[0]*(n+1)
for i in range(a,n+1):
    s[i]=max(s[i],s[i-a]+d-a)
for i in range(b,n+1):
    s[i]=max(s[i],s[i-b]+e-b)
for i in range(c,n+1):
    s[i]=max(s[i],s[i-c]+f-c)
n+=s[-1]
s=[0]*(n+1)
for i in range(d,n+1):
    s[i]=max(s[i],s[i-d]+a-d)
for i in range(e,n+1):
    s[i]=max(s[i],s[i-e]+b-e)
for i in range(f,n+1):
    s[i]=max(s[i],s[i-f]+c-f)
print(s[-1]+n)
### BUGGY CODE ###

import numpy as np

def dp(v, d, c):
    if res[v-1] == 0:
        res[v-1] = c

    if d == 0:
        return None

    if np.all(res > 0):
        return None

    for e in dic.get(v, []):
        dp(e, d-1, c)


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

dic = {}

for m in range(M):
    a, b = tuple(map(int, input().split(' ')))
    dic[a] = dic.get(a, []) + [b]
    dic[b] = dic.get(b, []) + [a]

Q = int(input())

vdc = []

for q in range(Q):
    vdc.append(tuple(map(int, input().split(' '))))

res = np.zeros(N)

for q in range(Q-1, -1, -1):
    v, d, c = vdc[q]
    dp(v, d, c)


for i in range(N):
    print(int(res[i]))


### FIXED CODE ###

import numpy as np

def dp(v, d, c):
    if memo[v-1][d]:
        return

    memo[v-1][d] = True
    if d == 0:
        res[v-1] = str(c)
        return

    dp(v, d-1, c)
    for e in dic[v-1]:
        dp(e, d-1, c)


N, M = [int(e) for e in input().split(' ')]

dic = [[] for _ in range(N)]
memo = [[False]*11 for _ in range(N)]

for m in range(M):
    a, b = [int(e) for e in input().split(' ')]
    dic[a-1].append(b)
    dic[b-1].append(a)

Q = int(input())


vdc = [[int(e) for e in input().split(' ')] for _ in range(Q)]

res = ['0']*N

[dp(v, d, c) for v, d, c in vdc[::-1]]


print('\n'.join(res))
### BUGGY CODE ###

def merge(A, l, m, r):
  n1 = m - l
  n2 = r - m
  L = [0] * (n1 + 1)
  R = [0] * (n2 + 1)

  for i in range(n1): L[i] = A[l + i]
  for i in range(n2): R[i] = A[m + i]
  L[n1] = float('inf')
  R[n2] = float('inf')

  i = 0
  j = 0
  count = 0
  for k in range(l, r):
    count += 1
    if L[i] <= R[j]:
      A[k] = L[i]
      i += 1
    else:
      A[k] = R[j]
      j += 1
  return count

def merge_sort(A, l, r):
  count = 0
  if l + 1 < r:
    m = (l + r) // 2
    count += merge_sort(A, l, m)
    count += merge_sort(A, m, r)
    count += merge(A, l, m, r)
  return count

n = int(input())
A = list(map(int, input().split()))
count = merge_sort(A, 0, len(A))
print(" ".join(map(str, A)))
print(count)

### FIXED CODE ###

def merge(A, l, m, r):
  L = A[l:m] + [SENTINEL]
  R = A[m:r] + [SENTINEL]

  i = 0
  j = 0
  for k in range(l, r):
    if L[i] <= R[j]:
      A[k] = L[i]
      i += 1
    else:
      A[k] = R[j]
      j += 1
  global count
  count += r - l

def merge_sort(A, l, r):
  if l + 1 < r:
    m = (l + r) // 2
    merge_sort(A, l, m)
    merge_sort(A, m, r)
    merge(A, l, m, r)

SENTINEL = float('inf')
n = int(input())
A = list(map(int, input().split()))
count = 0
merge_sort(A, 0, len(A))
print(" ".join(map(str, A)))
print(count)