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

n, k, q = map(int, input().split())
alist = [int(input()) for i in range(q)]

for i in range(1, n + 1):
    if k + (-1)*(q - alist.count(i)) <= 0:
        print('No')
    else:
        print('Yes')

### FIXED CODE ###

n, k, q = map(int, input().split())
alist = [int(input()) for i in range(q)]
ans = [k - q] * n

for Ai in alist:
    ans[Ai - 1] += 1

for Ai in ans:
    print('Yes') if Ai > 0 else print('No')
### BUGGY CODE ###

from collections import deque

X, Y = map(int, input().split())

mod = 10**9 + 7

stack = deque([(0, 0)])


def dfs(stack):
    ans = 0
    while len(stack) > 0:
        x, y = stack.pop()
        if x == X and y == Y:
            ans += 1
            ans %= mod
        for i, j in ((2, 1), (1, 2)):
            new_x, new_y = x+i, y+j
            if new_x > X or new_y > Y:
                continue
            stack.append((new_x, new_y))

    return ans


ans = dfs(stack)
print(ans)

### FIXED CODE ###

def cmb(n, k, mod, fac, ifac):
    """
    nCkを計算する
    """
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod


def make_tables(mod, n):
    """
    階乗テーブル、逆元の階乗テーブルを作成する
    """
    fac = [1, 1] # 階乗テーブル・・・(1)
    ifac = [1, 1] #逆元の階乗テーブル・・・(2)
    inverse = [0, 1] #逆元テーブル・・・(3)
    
    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    return fac, ifac


X, Y = map(int, input().split())
# 後の、n, mの大小を一定にするため
if X > Y:
    X, Y = Y, X
dist = X + Y
   
if dist % 3 != 0:
    print(0)
else:
    # (+1,+2) の移動の回数を n、(+2,+1) の移動の回数を m とする)
    # total = n + m
    # 以下の式は、2n + m = X, n + 2m = Y の連立方程式を解いた結果
    total = int((X+Y) / 3)
    n = X - total
    
    # n < 0 もしくは m < 0 の場合、たどり着けない
    # Y > X なので、m > n
    # n < 0 → 2X - Y < 0
    if Y > 2*X:
        print(0)
    else:
        MOD = 10**9 + 7

        fac, ifac = make_tables(MOD, total)
        ans = cmb(total, n, MOD, fac, ifac)
        print(ans)
### BUGGY CODE ###

a,b,k=map(int,input().split())
x=[]
y=[]
for i in range(a,b+1):
    x.append(i)
if len(x)<k:
    k=len(x)
for i in range(k):
    y.append(x[i])
for i in range(1,k+1):
    y.append(x[-i])
y=list(set(y))
y.sort()
for i in range(len(y)):
    print(y[i])

### FIXED CODE ###

a,b,k=map(int,input().split())
x=[]
y=[]
if b-a<k:
    k=b-a+1
for i in range(a,a+k):
    x.append(i)
for i in range(b-k+1,b+1):
    x.append(i)
x=list(set(x))
x.sort()
for i in range(len(x)):
    print(x[i])
### BUGGY CODE ###

def small(a, b):
    if a > b:
        return b
    else:
        return a


import numpy as np

n, k = map(int, input().split())
h = np.array(input().split(), np.int32)
INF = 10 ** 9
dp = [INF] * n
dp[0] = 0
for i in range(n):
    for j in range(1, k + 1):
        if i + j < n:
            dp[i + j] = small(dp[i + j], dp[i] + abs(h[i] - h[i + j]))
print(dp[-1])

### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    h = tuple(map(int, input().split()))
    INF = 10 ** 9
    dp = [INF] * n
    dp[0] = 0
    for i in range(n):
        for j in range(1, k + 1):
            i_j = i + j
            if i_j < n:
                x = dp[i] + abs(h[i] - h[i_j])
                if dp[i_j] > x:
                    dp[i_j] = x
    print(dp[-1])


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

n,m = map(int,input().split())
a=  list(map(int,input().split()))
for i in range(m):
    a[a.index(max(a))]=a[a.index(max(a))] //2
print(sum(a))

### FIXED CODE ###

import heapq
n,m = map(int,input().split())
a=  list(map(int,input().split()))
h = list(map(lambda x:-1*x,a))
heapq.heapify(h)
for i in range(m):
    heapq.heapreplace(h,-(-h[0]//2))
print(-1*sum(h))
### BUGGY CODE ###

import sys
import math
H,W=map(int, input().split())
Ch, Cw=map(int, input().split())
Dh, Dw=map(int, input().split())
maze=[]
for _ in range(H):
    RRR=(input().replace(".","0")).replace("#","1")
    maze.append(list(map(int, RRR)))
#print(maze)
dis=[[H**2*W**2 for _ in range(W+1)]for _ in range(H+1)]
start=(Ch,Cw,0)
goal=(Dh,Dw)
walk=[(1,0),(-1,0),(0,1),(0,-1)]
wap=[(2,0),(2,1),(2,2),(2,-1),(2,-2),(1,-2),(1,2),(0,2),(0,-2),(-1,2),(-1,-2),(-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2)]
cand=[start]
dis[start[0]][start[1]]=0
done=[]
flag=False
while len(cand)>0:
    #print(cand)
    place=cand.pop()
    hh,ww,cost=place
    if hh==Dh and ww==Dw:
        flag=True
    for each in walk:
        h1,w1=hh+each[0],ww+each[1]
        if h1>=1 and w1>=1 and h1<=H and w1<=W and maze[h1-1][w1-1]==0 and dis[h1][w1]>cost:
            dis[h1][w1]=cost
            cand.append((h1,w1,cost))
    for each in wap:
        h1,w1=hh+each[0],ww+each[1]
        if h1>=1 and w1>=1 and h1<=H and w1<=W and maze[h1-1][w1-1]==0 and dis[h1][w1]>cost+1:
            dis[h1][w1]=cost+1
            cand.append((h1,w1,cost+1))
if flag:
    print(dis[Dh][Dw])
else:
    print(-1)


### FIXED CODE ###

import sys
import math
H,W=map(int, input().split())
Ch, Cw=map(int, input().split())
Dh, Dw=map(int, input().split())
maze=[]
for _ in range(H):
    RRR=(input().replace(".","0")).replace("#","1")
    maze.append(list(map(int, RRR)))
#print(maze)
dis=[[H**2*W**2 for _ in range(W+1)]for _ in range(H+1)]
Es=[[H**2*W**2 for _ in range(W+1)]for _ in range(H+1)]
start=(Ch,Cw,0)
goal=(Dh,Dw)
walk=[(1,0),(-1,0),(0,1),(0,-1)]
wap=[]
for i in range(-2,3):
    for j in range(-2,3):
        wap.append((i,j))
wap.remove((0,0))
for each in walk:
    wap.remove(each)
cand=[start]
dis[start[0]][start[1]]=0
flag=False
edge=[]
while len(cand)>0:
    #print(dis)
    place=cand.pop()
    hh,ww,cost=place
    if hh==Dh and ww==Dw:
        flag=True
    for each in walk:
        h1,w1=hh+each[0],ww+each[1]
        if h1>=1 and w1>=1 and h1<=H and w1<=W and maze[h1-1][w1-1]==0 and dis[h1][w1]>cost:
            dis[h1][w1]=cost
            cand.append((h1,w1,cost))
        elif h1>=1 and w1>=1 and h1<=H and w1<=W and maze[h1-1][w1-1]==1 and Es[hh][ww]>cost:
            Es[hh][ww]=cost
            edge.append((hh,ww,cost))
            #print(edge)
    if len(cand)==0:
        for place in edge:
            hh,ww,cost=place
            for each in wap:
                h1,w1=hh+each[0],ww+each[1]
                #print(h1,w1)
                if h1>=1 and w1>=1 and h1<=H and w1<=W and maze[h1-1][w1-1]==0 and dis[h1][w1]>cost+1:
                    dis[h1][w1]=cost+1
                    cand.append((h1,w1,cost+1))
        edge=[]
        #print(cand)
if flag:
    print(dis[Dh][Dw])
else:
    print(-1)
### BUGGY CODE ###

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

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

i=m
while i>0:
    ma=max(c)
    ind=c.index(ma)
    c[ind]=ma//2
    
    i-=1
    
print(sum(c))

### FIXED CODE ###

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

c=list(map(lambda x: int(x)*-1,input().split()))
#heapqでは最小値しか取り出せないので最大値をとるばあには－１をかけておく

heapq.heapify(c)  #リストを優先度付きキューに
for i in range(m):
    cmin=heapq.heappop(c)  #最小値の取り出し
    heapq.heappush(c,(-1)*(-cmin//2))#最小値を2で割った商をリストに追加

print(-sum(c))
### BUGGY CODE ###

s=input()

ans=0

while(True):

    if(s.find('BW')== -1):
        break

    ind=-1
    while(True):
        ind=s.find('BW',ind+1)
        if(ind==-1):
            break
        else:
            ans+=1

    s=s.replace('BW', 'WB')
print(ans)

### FIXED CODE ###

s=input()

ans=0
b_count=0
for i in range(len(s)):
    if(s[i]=='W'):
        ans+=b_count
    else:
        b_count+=1
print(ans)
### BUGGY CODE ###

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

for i in range(1, n+1):
    if i == 1:
        distance = k - (a[0] + (k - a[-1]))
        mindistance = distance
        a.append(a[0])
        a.pop(0)
    else:
        distance = k - (a[0] - a[-1])
        if distance < mindistance:
            mindistance = distance
        a.append(a[0])
        a.pop(0)

print(mindistance)

### FIXED CODE ###

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

a.append(a[0] + k)

distance = []

for i in range(len(a) - 1):
    distance.append(a[i+1] - a[i])

mindistance = 0
for j in distance:
    mindistance += j

print(mindistance - max(distance))
### BUGGY CODE ###

r,g,b,n=map(int,input().split())
count=0
for x in range(n+1):
    for y in range(n-x+1):
        z=(n-r*x-g*y)//b
        if 0<=z<=3000 and r*x+g*y+z*b==n:count+=1
print(count)

### FIXED CODE ###

r,g,b,n=map(int,input().split())
count=0
for x in range(n+1):
    for y in range(n-x+1):
        z=(n-r*x-g*y)//b
        if 0<=z<=3000:
            if r*x+g*y+z*b==n:count+=1
print(count)
### BUGGY CODE ###


def count(P, idx, score, G, mn, cnt):
    # print(idx, score, mn, cnt)
    if score >= G and mn > cnt:
        return cnt
    if idx == 0:
        return mn
    for i in range(P[idx][0]+1):
        tmp = P[idx][1] if i == P[idx][0] else 0
        # print(idx, i)
        mn = count(P, idx-1, score+idx*100*i+tmp, G, mn, cnt+i)
    return mn

D,G = map(int, input().split())
P = [0]
for i in range(D):
    p,c = map(int, input().split())
    P.append([p,c])
print(count(P, D, 0, G, 10**9, 0))


### FIXED CODE ###

from math import ceil
d,g = map(int, input().split())
pc = [list(map(int, input().split())) for i in range(d)]

ans = float('INF')
inf = float('INF')
for i in range(2**d):
    tmp = 0
    cnt = 0
    for j in range(d):
        p,c = pc[j]
        if i & (1 << j):
            tmp += p * (j+1) * 100 + c
            cnt += p
    if g <= tmp and cnt < ans:
        ans = cnt
    if g > tmp:
        tmp_cnt = inf 
        tmp_ = 0
        gg = (g - tmp) / 100
        for j in range(d):
            p,c = pc[j]
            if i & (1 << j):
                continue
            if ceil(gg / (j+1)) < min(p,tmp_cnt):
                cc = ceil(gg / (j+1))
                tmp_ = cc * (j+1) * 100
                tmp_cnt = cc
            elif gg - c / 100 <= p * (j+1) and p < tmp_cnt:
                tmp_ = p * (j+1) * 100 + c
                tmp_cnt = p
        if g <= tmp + tmp_ and cnt + tmp_cnt < ans:
            ans = cnt + tmp_cnt

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

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

a.sort()
def Eratosthenes(x):
    cnt = 0
    nmax = x[-1]
    is_prime = [True] * (nmax+1)
    for i in range(1, nmax+1):
        if not is_prime[i]:
            continue
        if i in x:
            for j in range(i*2, nmax+1, i):
                is_prime[j] = False
    for i in x:
        if x.count(i) > 1:
            continue
        if is_prime[i] == True:
            cnt += 1
    print(cnt)

Eratosthenes(a)

### FIXED CODE ###

from collections import Counter

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

a.sort()
cnt = 0
nmax = a[-1]
table = [True] * (nmax+1)
c = Counter(a)

duplicate = []
for i in c.keys():
    if c[i] > 1:
        duplicate.append(i)
for i in a:
    if not table[i]:
        continue
    if not i in duplicate:
        cnt += 1
    for j in range(i*2, nmax+1, i):
        table[j] = False
print(cnt)
### BUGGY CODE ###

import sys
import numpy as np

n, k, q = [int(nkq) for nkq in input().split()]
sys.stderr.write(str(n)+' '+str(k)+' '+str(q)+'\n')

arr = np.full(n, k, dtype=np.int64)

for i in range(q):
  a_i = int(input())
  
  for j in range(n):
    if j+1 != a_i:
      arr[j] -= 1

#  sys.stderr.write(str(i+1)+': ')
#  for j in range(n):
#    sys.stderr.write(str(arr[j])+' ')
#  sys.stderr.write('\n')

for j in range(n):
  if arr[j] > 0:
    print("Yes")
  else:
    print("No")


### FIXED CODE ###

import numpy as np

n, k, q = [int(nkq) for nkq in input().split()]
arr = np.full(n, k-q, dtype=np.int64)

for i in range(q):
  a_i = int(input()) 
  arr[a_i-1] += 1

for j in range(n):
  if arr[j] > 0:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

#AGC005A

x=raw_input()
while x.count('ST')!=0:
 x=x.replace('ST','')
print len(x)


### FIXED CODE ###

#AGC005A

s=raw_input()
res=0
for c in s:
 if c=='S':
  res+=1
 elif c=='T' and res>0:
  res-=1
print res*2
### BUGGY CODE ###

import numpy as np

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

A = np.array(A_)

ans = 0
for X in range(np.min(A),np.max(A)+1):
    tmp = 0
    for a in A:
        if X-1 <= a <= X+1:
            tmp += 1
    ans = max(tmp,ans)
print(ans)


### FIXED CODE ###

import collections

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

dic = collections.Counter(A)
tmp = [0 for _ in range(A[-1]+1)]


for X in dic.keys():
    tmp[X] = dic[X]

ans = 0
for i in range(len(tmp)):
    ans = max(ans,sum(tmp[i:i+3]))

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

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

cnt = 0
check = []
kouho = list(range(1,n+1))
play = 0

while play < n*(n-1) // 2:
    s = play
    for i in kouho:
        if i in check or len(li[i-1]) == 0:
            continue
        temp = li[i-1][0]
        if li[temp-1][0] == i and temp not in check:
            del li[i-1][0]
            del li[temp-1][0]
            play += 1
            check.append(i)
            check.append(temp)
    cnt += 1
    kouho = check.copy()
    check = []
    
    if s == play:
        print(-1)
        exit()

print(cnt)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
 
N = int(input())
A = [[-1] + [int(x)-1 for x in row.split()][::-1] for row in sys.stdin.readlines()]
 
A.append([-1])

def f(cand):
    cand1 = set()
    can_use = []
    for n in cand:
        if A[A[n][-1]][-1] == n:
            can_use.append(n)
    for n in can_use:
        A[n].pop()
        cand1.add(n)
        if A[n][-1] != -1:
            cand1.add(A[n][-1])
    return len(can_use), cand1
    
answer = 0
rest = N*(N-1)
cand = set(range(N))
while True:
    answer += 1
    x,cand = f(cand)
    if x == 0:
        answer = -1
        break
    rest -= x
    if rest == 0:
        break
    
print(answer)
### BUGGY CODE ###

x, k, d = [int(i) for i in input().split()]
for _ in range(k):
  if abs(x - d) >= abs(x + d):
    x += d
  else:
    x -= d
print(abs(x))

### FIXED CODE ###

x, k, d = [int(i) for i in input().split()]
if x < 0:
  x = -x
l = min(k, x // d)
k -= l
x -= l * d
if k % 2 == 0:
  print(x)
else:
  print(d - x)
### BUGGY CODE ###

s=input()
K=int(input())

ch={}
for S in s:
    if S not in ch:
        ch[S]=1

ch=list(ch.keys())

cand=[]
CAND={}
leng=0
for c in ch:
    for i in range(len(s)):
        if s[i]==c:
            for j in range(len(s)-i):
                if s[i:i+j+1] not in CAND:
                    cand.append(s[i:i+j+1])
                    CAND[s[i:i+j+1]]=1
                    leng+=1
    if leng>=K:
        break

cand.sort()
print(cand[K-1])

### FIXED CODE ###

S=list(input())
K=int(input())
N=len(S)

L=[]
for i in range(K):
    for j in range(N-i):
        if S[j:j+i+1] not in L:
            L.append(S[j:j+i+1])

L.sort()
ans=""
for l in L[K-1]:
    ans+=l
print(ans)
### BUGGY CODE ###

def main():
    import sys
    N = int(input())
    A = []
    for i in range(N):
        row = list(map(int, sys.stdin.readline().split()))
        row = [r - 1 for r in row]
        A.append(row)

    counter = [0] * (N + 1)
    finish = 0

    ans = 0
    check_done = set()
    while finish < N * (N - 1) // 2:
        checked = set()
        ans += 1

        exit_flg = True
        for n in range(N):
            # ある日程ですでにnは戦っている
            if n in checked:
                continue
            checked.add(n)

            # nの対戦は終了
            if counter[n] == N - 1:
                continue

            n_match = A[n][counter[n]]  # nの対戦相手
            n_match_match = A[n_match][counter[n_match]]  # nの対戦相手の対戦相

            # nの対戦相手はある日の試合をすでに終えている
            if n_match in checked:
                continue

            # マッチング成立
            if n == n_match_match:
                exit_flg = False

                checked.add(n_match)

                finish += 1
                counter[n] += 1
                counter[n_match] += 1

        # 一つも組み合わせられなかった
        if exit_flg:
            print(-1)
            exit()

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

N = int(input())

# 初期化
G = [None] * (10 ** 6 + 1)  # グラフ
for i in range(10 ** 6 + 1):
    G[i] = set()
U = [None] * (10 ** 6 + 1)  # 入次数
D = [0] * (10 ** 6 + 1)  # 根からの距離


# 変換用
def x(i, j):
    return j + 1000 * i


# グラフを構築
for i in range(1, N + 1):
    A = list(map(int, input().split()))
    for j in range(N - 2):
        fv1, fv2 = min(i, A[j]), max(i, A[j])
        tv1, tv2 = min(i, A[j + 1]), max(i, A[j + 1])
        G[x(fv1, fv2)].add(x(tv1, tv2))
        U[x(fv1, fv2)] = 0
        U[x(tv1, tv2)] = 0


# 入次数をカウント
for i in range(10 ** 6 + 1):
    for v in G[i]:
        U[v] += 1

        
# トポロジカルソート
U_zero_nodes = []
for i in range(10 ** 6 + 1):
    if U[i] is None:
        continue

    if U[i] == 0:
        U_zero_nodes.append(i)


topological_order = []
while U_zero_nodes:
    n = U_zero_nodes.pop()
    topological_order.append(n)

    for v in G[n]:
        U[v] -= 1
        if U[v] == 0:
            U_zero_nodes.append(v)


# 不可能判定
if len(topological_order) != N * (N - 1) // 2:
    print(-1)
    exit()


# 最長経路を計算
for t_n in topological_order:
    for v in G[t_n]:
        D[v] = max(D[v], D[t_n] + 1)
print(max(D) + 1)
### BUGGY CODE ###

L,R = map(int,input().split())

if L-R > 672:
    print(0)
else:
    minMod = 2019
    for i in range(L,R):
        for j in range(i+1,R+1):
            tmp = (i*j)%2019
            if tmp == 0:
                minMod = 0
                break
            minMod = min(tmp,minMod)
    print(minMod)
    

### FIXED CODE ###

L,R = map(int,input().split())

if R-L > 672:
    print(0)
else:
    minMod = 2019
    for i in range(L,R):
        for j in range(i+1,R+1):
            tmp = (i*j)%2019
            if tmp == 0:
                minMod = 0
                break
            minMod = min(tmp,minMod)
    print(minMod)
### BUGGY CODE ###

from collections import deque
H, W = [int(i) for i in input().split()]
A = [list(input()) for _ in range(H)]

Q = deque()
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            Q.append((i, j, 0))

memo = [[1e10 for _ in range(W)] for _ in range(H)]
ans = 0
while Q:
    i, j, dist = Q.popleft()
    if memo[i][j] <= dist:
        continue
    memo[i][j] = dist
    ans = max(ans, dist)
    for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and A[ni][nj] == "." and dist + 1 < memo[ni][nj]:
            Q.append((ni, nj, dist + 1))

print(ans)


### FIXED CODE ###

from collections import deque
H, W = [int(i) for i in input().split()]
A = [list(input()) for _ in range(H)]

Q = deque()
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            Q.append((i, j, 0))

ans = 0
while Q:
    i, j, dist = Q.popleft()
    ans = max(ans, dist)
    for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and A[ni][nj] == ".":
            A[ni][nj] = "#"
            Q.append((ni, nj, dist + 1))

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

N, M = map(int, input().split())
LR = [tuple(map(int, input().split())) for _ in range(M)]

count_dict = {}

gate = set(range(10**5 + 1))

for i in range (M):
    l = LR[i][0]
    r = LR[i][1]
    temp = set(range(l, r+1))

    gate = gate & temp

print(len(gate))


### FIXED CODE ###

N, M = map(int, input().split())
LR = [tuple(map(int, input().split())) for _ in range(M)]

count_dict = {}

gate = set(range(10**5 + 1))

L = 1
R = 10**5

for i in range (M):
    l = LR[i][0]
    r = LR[i][1]

    if l > L:
        L = l
    if r < R:
        R = r

print(len(range(L, R+1)))
### BUGGY CODE ###

#b
#naive (TLE)

n,m = [int(i) for i in input().split()]
edges = [[] for _ in range(n)]
colors = [0]*n

for _ in range(m):
    a,b = [int(i) for i in input().split()]
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
    
q = int(input())
info = []
for _ in range(q):
    v,d,c = [int(i) for i in input().split()]
    info.append((v,d,c))
    
info.reverse()
for tupple in info:
    v,d,c = tupple
    
    #bfs
    queue = [v-1]
    while(d>=0):
        next_queue = []
        for p in queue:
            if colors[p]==0:
                colors[p] = c
            nodes = edges[p]
            next_queue += nodes
        d -= 1
        queue = next_queue

for i in range(n):
    print(colors[i])


### FIXED CODE ###

#b
#上で再起の代わりにナイーブに配列内の値を埋めていく。
#aこのほうがちょい早い。

#b
#by using the condition d<=10, we should memorize V*d whether the pair is already searched.
#if searched, we can stop.
#まだ遅い。TLE.

n,m = [int(i) for i in input().split()]
edges = [[] for _ in range(n)]
colors = [0]*n

checker = [[0 for _ in range(11)] for _ in range(n)]        

for _ in range(m):
    a,b = [int(i) for i in input().split()]
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
    

def dfs(d,v,c):
    if checker[v][d] != 0 or d<0:
        return
    #d>=0 and (v,d) is not checked
    if colors[v]==0: #not colored yet
        colors[v] = c
        
    #ここよ
    for j in range(d+1):
        checker[v][j] = 1
        
        
    nodes=edges[v]
    for u in nodes:
        dfs(d-1, u, c)

    
q = int(input())
info = []
for _ in range(q):
    v,d,c = [int(i) for i in input().split()]
    info.append((v-1,d,c))
    
info.reverse()
for tupple in info:
    v,d,c = tupple
    
    #not bfs but dfs
    dfs(d,v,c)
    
for i in range(n):
    print(colors[i])
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
dp=[[0 for i in range(m)]for i in range(m)]
s=[a[i]-a[i-1] if i!=0 else 0 for i in range(1,m) ]
s.sort()
if n!=1:
    print(sum(s[:-n+1]))
else:
    print(sum(s))



### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
s=[a[i]-a[i-1] if i!=0 else 0 for i in range(1,m) ]
s.sort()
if n!=1:
    print(sum(s[:-n+1]))
else:
    print(sum(s))
### BUGGY CODE ###

n=int(input())
s=input()
m=len(s)
mod=10**9+7
dp=[[0]*(n+1) for i in range(n+1)]
dp[0][0]=1
for i in range(1,n+1):
    for j in range(n+1):
        if j==0:
            dp[i][j]+=dp[i-1][j]*2**j+dp[i-1][j+1]*2**(j+1)
        elif j==n:
            dp[i][j]+=dp[i-1][j-1]*2*2**(j-1)
        else:
            dp[i][j]+=dp[i-1][j-1]*2*2**(j-1)+dp[i-1][j+1]*2**(j+1)
        dp[i][j]//=2**j
        dp[i][j]%=mod

print(dp[n][m]%mod)
#print((dp[n][m]//(pow(2,m)))%mod)






### FIXED CODE ###

n=int(input())
s=input()
m=len(s)
mod=10**9+7
dp=[[0]*(n+1) for i in range(n+1)]
dp[0][0]=1
for i in range(1,n+1):
    for j in range(n+1):
        if j==0:
            dp[i][j]+=dp[i-1][j]+dp[i-1][j+1]
        elif j==n:
            dp[i][j]+=dp[i-1][j-1]*2
        else:
            dp[i][j]+=dp[i-1][j-1]*2+dp[i-1][j+1]
        dp[i][j]%=mod
def div(a,b):
    return (a*pow(b,mod-2,mod))%mod
print(div(dp[n][m],pow(2,m)))
### BUGGY CODE ###

n=int(input())
s=[''.join(sorted(input())) for i in range(n)]
ans=0
#dict={}
s_list = []
# for i in s:
#   if i in dict:
#     ans+=dict[i]
#     dict[i]+=1
#   else:
#     dict[i]=1

# print(dict)
for i in range(n):
  check = 0
  for j in s_list:
    if s[i] == j:
      check = 1
      ans += 1
  s_list.append(s[i])

print(ans)


### FIXED CODE ###

n = int(input())
s = ["".join(sorted(str(input()))) for i in range(n)]
d = {}
ans = 0
for i in s:
    if i not in d:
        d[i] = 0
    else:
        d[i] += 1
        ans += d[i]
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
 
for i in range(1,n+1):
	print(a.count(i))

### FIXED CODE ###

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

ans = [0] * n

for i in a:
    ans[i - 1] += 1

for i in ans:
    print(i)
### BUGGY CODE ###

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

K, S = map(int, input().split())

# 絶対TLE…
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 ###

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

K, S = map(int, input().split())

ans = 0
for x in range(K+1):
    for y in range(K+1):
        # zは全部回さないで、Sを満たすようなものだけ用意する
        z = S - x - y
        # 候補となるzがKの範囲内であれば有効
        if 0 <= z <= K:
            ans += 1
print(ans)