Harryxun/stf_run huggingface dataset:
# -*- coding: utf-8 -*-
import collections
h, w = map(int,input().split())
a = []
for i in range(h):
    a.append(list(input()))

tmp = []
for i in range(h):
    for j in a[i]:
        tmp.append(j)
#print(tmp)
c = collections.Counter(tmp)
tmp2 = set(tmp)
four = 0
two = 0
odd = 0
for i in tmp2:
    if c[i] % 4 == 0:
        four += 1
    elif c[i] % 2 == 0:
        two += 1
    else:
        odd += 1

if h % 2 == 1 and w % 2 == 1:
    if odd == 1 and (two == 2 or two == 0):
        ans = "Yes"
    else:
        ans == "No"
elif h % 2 == 0 and w % 2 == 0:
    if two == 0 and odd == 0:
        ans = "Yes"
    else:
        ans = "No"
else:
    if (odd == 0 and two == 0) or (two == 2 and odd == 0):
        ans = "Yes"
    else:
        ans = "No"
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import collections
h, w = map(int,input().split())
a = []
for i in range(h):
    a.append(list(input()))

tmp = []
for i in range(h):
    for j in a[i]:
        tmp.append(j)
#print(tmp)
c = collections.Counter(tmp)
tmp2 = list(set(tmp))
four = 0
two = 0
odd = 0
for i in tmp2:
    if c[i] % 4 == 0:
        four += 1
    elif c[i] % 2 == 0:
        two += 1
    else:
        odd += 1

if h % 2 == 1 and w % 2 == 1:
    if odd == 1 and two <= (h // 2 + w // 2):
        ans = "Yes"
    else:
        ans = "No"
elif h % 2 == 0 and w % 2 == 0:
    if two == 0 and odd == 0:
        ans = "Yes"
    else:
        ans = "No"
elif h % 2 == 0 and w % 2 == 1:
    if odd == 0 and two <= h // 2:
        ans = "Yes"
    else:
        ans = "No"
elif h % 2 == 1 and w % 2 == 0:
    if odd == 0 and two <= w // 2:
        ans = "Yes"
    else:
        ans = "No"
print(ans)
from decimal import Decimal
import fractions


N = int(input())

now = Decimal("1")

for i in range(N):

    T = Decimal(input())

    now = now * T / fractions.gcd(now,T)

print("{:.0f}".format(now))


### FIXED CODE ###

import fractions

N = int(input())

now = 1

for i in range(N):

    T = int(input())

    now = now * T // fractions.gcd(now , T)

print (now)
n,x,y = map(int,input().split())
cnt_l = [0]*n
from collections import deque
# 幅優先探索
def bfs(start):  
  queue = deque()
  queue.append(start)
  step_counts = [-1]*(n+1)
  step_counts[start] = 0
  while(queue):
    i = queue.popleft()
    cnt = step_counts[i]
    # 隣のグラフを取得
    if(i==x):
      nex_l = (i-1,y,i+1)
      elif(i==y):
        nex_l = (i-1,x,i+1)
      else:
        nex_l = (i-1,i+1)

      cnt += 1
      for j in nex_l:
        # 端より先だと止める
        if(j < 1 or n < j):
          continue
          # 訪問済みだと止める
          if(step_counts[j]!=-1):
            continue
            queue.append(j)
            step_counts[j] = cnt
            cnt_l[cnt] += 1


for i in range(1,n+1):
  bfs(i)
 
for i in range(1,n):
  # (a,b),(b,a)のペアがあるため//2
  print(cnt_l[i]//2)


### FIXED CODE ###

n,x,y = map(int,input().split())
cnt_l = [0]*n
from collections import deque
# 幅優先探索
def bfs(start):
    queue = deque()
    queue.append(start)
    step_counts = [-1]*(n+1)
    step_counts[start] = 0
    while(queue):
        i = queue.popleft()
        cnt = step_counts[i]
        # 隣のグラフを取得
        if(i==x):
            nex_l = (i-1,y,i+1)
        elif(i==y):
            nex_l = (i-1,x,i+1)
        else:
            nex_l = (i-1,i+1)

        cnt += 1
        for j in nex_l:
            # 端より先だと止める
            if(j < 1 or n < j):
                continue
            # 訪問済みだと止める
            if(step_counts[j]!=-1):
                continue
            queue.append(j)
            step_counts[j] = cnt
            cnt_l[cnt] += 1

for i in range(1,n+1):
    bfs(i)

for i in range(1,n):
    # (a,b),(b,a)のペアがあるため//2
    print(cnt_l[i]//2)
# coding: UTF-8
import sys
sys.setrecursionlimit(10**5)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

R, G, B, N = map(int, input().split())
count = 0
for i in range(1, N + 1):
    j i n range(1, N + 1):
        t = N - (i * R + G * j)
        if t < 0:
            break
        if t % B == 0:
            count += 1
print(count)

### FIXED CODE ###

# coding: UTF-8
import sys
sys.setrecursionlimit(10**5)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

R, G, B, N = map(int, input().split())
count = 0
for i in range(N + 1):
    for j in range(N + 1):
        t = N - (i * R + G * j)
        if t < 0:
            break
        if t % B == 0:
            count += 1
print(count)
import math
N=int(input())
N=math.factorial(N)
r=math.sqrt(N)
count=0
if r%1==0:
  count-=1
for i in range(int(r)):
  if N%(1+i)==0:
    count+=2
print(count)

### FIXED CODE ###

N=int(input())
R=[0]*(N-1)
for i in range(1,N+1):
  for r in range (2,N+1):
    count=0
    while i%r==0:
      i=i/r
      count+=1
    R[r-2]+=count

count=1
for r in range(N-1):
  count=count*(R[r]+1)
print(count%(10**9+7))
k = int(input())
x, y = [int(i) for i in raw_input().split()]
 
def solve(k, x, y):
    if x < 0:
        x = -x
    if y < 0:
        y = -y
 
    if x==0 and y==0:
        print 0
        return
 
    if (x-y)%2==1 and k%2==0:
        print -1
        return
 
    output = [(x,y)]
    while True:
        # print 'while', x,y
        if x+y == k:
            break
        if x==0 and y == 0:
            break
        if x+y<k:
            output.append((abs((x-y)/2), k - abs((x-y)/2)))
            x, y = abs((x-y)/2), k - abs((x-y)/2)
 
        elif x+y <2*k:
            output.append((abs((x-y)/2), k - abs((x-y)/2)))
            x, y = abs((x-y)/2), k - abs((x-y)/2)
            # print 'x,y',x,y
        elif x > k:
            x -= k
            output.append((x,y))
        elif y > k:
            y -= k
            output.append((x,y))
        else:
            x = 0
            y -= x
            output.append((x,y))
 
    print len(output)
 
    for (a,b) in output[::-1]:
        print a, b
 
# k=4
# x,y=9,9
solve(k, x, y)


### FIXED CODE ###

a, b = [int(i) for i in raw_input().split()]

if abs(a-b)%2==1:
  print "IMPOSSIBLE"
else:
  print (a+b)/2
a = raw_input()
x,y = a.split
x = int(x)
y = int(y)
print x*y + " " + x*2 + y*2

### FIXED CODE ###

x = raw_input().split(" ")
 
a = int(x[0])
b = int(x[1])
 
print str(a*b) + " " + str(2*(a+b))
N,M = map(int,input().split())
A = list(map(int,input().split()))
CA = {}
for i in range(N):
    if A[i] not in CA:
        CA[A[i]] = 0
    CA[A[i]] += 1
indA = [0 for _ in range(N*M+1)]
for i in range(N):
    indA[A[i]] = 1
B = list(map(int,input().split()))
CB = {}
for j in range(M):
    if B[j] not in CB:
        CB[B[j]] = 0
    CB[B[j]] += 1
indB = [0 for _ in range(N*M+1)]
for j in range(M):
    indB[B[j]] = 1
flag = 0
for a in CA:
    if CA[a]>1:
        flag = 1
        break
for b in CB:
    if CB[b]>1:
        flag = 1
        break
if flag==1:
    print(0)
else:
    dp = [0 for _ in range(N*M+1)]
    dp[N*M] = 1
    for k in range(N*M-1,0,-1):
        if indA[k]==1 and indB[k]==1:
            dp[k] = dp[k+1]
        elif indA[k]==1 and indB[k]==0:
            cnt = 0
            for j in range(M):
                if B[j]>k:
                    cnt += 1
            dp[k] = (dp[k+1]*cnt)%p
        elif indA[k]==0 and indB[k]==1:
            cnt = 0
            for i in range(N):
                if A[i]>k:
                    cnt += 1
            dp[k] = (dp[k+1]*cnt)%p
        else:
            cnt1 = 0
            for i in range(N):
                if A[i]>k:
                    cnt1 += 1
            cnt2 = 0
            for j in range(M):
                if B[j]>k:
                    cnt2 += 1
            cnt = cnt1*cnt2-(N*M-k)
            dp[k] = (dp[k+1]*cnt)%p
    print(dp[1])

### FIXED CODE ###

from bisect import bisect_right
p = 10**9+7
N,M = map(int,input().split())
A = list(map(int,input().split()))
CA = {}
for i in range(N):
    if A[i] not in CA:
        CA[A[i]] = 0
    CA[A[i]] += 1
indA = [0 for _ in range(N*M+1)]
for i in range(N):
    indA[A[i]] = 1
A1 = sorted(A[:])
B = list(map(int,input().split()))
CB = {}
for j in range(M):
    if B[j] not in CB:
        CB[B[j]] = 0
    CB[B[j]] += 1
indB = [0 for _ in range(N*M+1)]
for j in range(M):
    indB[B[j]] = 1
B1 = sorted(B[:])
flag = 0
if N*M not in CA or CA[N*M]!=1:flag=1
if N*M not in CB or CB[N*M]!=1:flag=1
for a in CA:
    if CA[a]>1:
        flag = 1
        break
for b in CB:
    if CB[b]>1:
        flag = 1
        break
if flag==1:
    print(0)
else:
    dp = [0 for _ in range(N*M+1)]
    dp[N*M] = 1
    for k in range(N*M-1,0,-1):
        if indA[k]==1 and indB[k]==1:
            dp[k] = dp[k+1]
        elif indA[k]==1 and indB[k]==0:
            cnt = bisect_right(B1,k)
            cnt = M-cnt
            dp[k] = (dp[k+1]*cnt)%p
        elif indA[k]==0 and indB[k]==1:
            cnt = bisect_right(A1,k)
            cnt = N-cnt
            dp[k] = (dp[k+1]*cnt)%p
        else:
            cnt1 = bisect_right(A1,k)
            cnt1 = N-cnt1
            cnt2 = bisect_right(B1,k)
            cnt2 = M-cnt2
            cnt = cnt1*cnt2-(N*M-k)
            dp[k] = (dp[k+1]*cnt)%p
    print(dp[1])
import sys

H, W, M = map(int, input().split())
d = [[0]*W for _ in range(H)]
for _ in range(M):
    h, w = map(int, input().split())
    h, w = h-1, w-1
    d[h][w] = 1
tate, yoko = [], []
for w in range(W):
    res = 0
    for h in range(H): res += d[h][w]
    tate.append(res)
for h in range(H):
    yoko.append(sum(d[h]))
    
tate_max = max(tate)
yoko_max = max(yoko)

ans_tate, ans_yoko = [], []
for i in range(W):
    if tate[i] == tate_max:
        ans_tate.append(i)
for i in range(H):
    if yoko[i] == yoko_max:
        ans_yoko.append(i)        

for h in ans_yoko:
    for w in ans_tate:
        if d[h][w]!=1:
            print(tate_max+yoko_max)
            sys.exit()

print(tate_max+yoko_max-1)

### FIXED CODE ###

import sys
H, W, M = map(int, input().split())
h_list, w_list = [0]*H, [0]*W
check = set()
for _ in range(M):
    h, w = map(int, input().split())
    check.add((h-1, w-1))
    h_list[h-1] += 1
    w_list[w-1] += 1
h_max, w_max = max(h_list), max(w_list)
h_bom = [i for i in range(H) if h_list[i]==h_max]
w_bom = [i for i in range(W) if w_list[i]==w_max]
for h in h_bom:
    for w in w_bom:
        if not (h, w) in check:
            print(h_max+w_max)
            sys.exit()
print(h_max+w_max-1)
import math

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

if c%math.gcd(a, b) == 0:
    print('YES')
else:
    print('NO') 

### FIXED CODE ###

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

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

if c%gcd(a, b) == 0:
    print('YES')
else:
    print('NO')
A,B,C,K = input().split()
if A > K:
  print(K)
elif A+B > K:
  print(A)
else:
  print(2*A + B - K)

### FIXED CODE ###

A,B,C,K = input().split()
if int(A) >= int(K):
  print(K)
elif int(A)+int(B) >= int(K):
  print(A)
else:
  print(int(A) + int(A) + int(B) - int(K))
n, d = map(int, input().split())
count = 0

for i in range(n):
    x, y = map(int, input(), split())
    if d^2 >= x^2 + y^2:
        count += 1

print(count)


### FIXED CODE ###

n, d = map(int, input().split())
count = 0

for i in range(n):
    x, y = map(int, input().split())
    if d * d >= x * x + y * y:
        count = count + 1

print(count)
c = input()
if c == 'a' or c =='i' or c == 'u' or c == 'e' or c =='O':
  priint('vowel')
else:
  print('consonant')

### FIXED CODE ###

c = input()
if c == 'a' or c =='i' or c == 'u' or c == 'e' or c =='o':
  print('vowel')
else:
  print('consonant')
n = int(input())
list=[0,'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
word = []
i = 12
while i>=0:
  x = n//(26**i)
  word.append(x)
  n = n-x*26**i
  i -= 1

while True:
  word = int(''.join(word)).split()
  if 0 in word:
    p = word.index(0)
    word[p-1] = word[p-1]-1 
    word[p] = 26
  else:
    break

h=''
for i in range(len(word)):
  h += list[word[i]]
print(h)


### FIXED CODE ###

list = [0,'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
num_list =[0]
for i in range(1,15):
    num_list.append(26**i+num_list[i-1])

n = int(input())
i = 0
while True:
    if num_list[i] >= n:
        break
    else:
        i +=1


word = []
for j in range(i,0,-1):
    x = n//26**(j-1)
    if x==27:
        word.append(26)
        n = n -26**(j-1)*(n//26**(j-1))+26**(j-1)
    else:
        word.append(x)
        n = n -26**(j-1)*(n//26**(j-1))
while True:
    if 0 in word:
        p = word.index(0)
        word[p-1] = word[p-1]-1
        word[p] = 26
    else:
        break
h =''
for k in range(len(word)):
    h+=str(list[word[k]])
print(h)
import math
n=int(input())
t=int(input())
lcm=t
a=t
for i in range(n-1):
    t=int(input())
    a=math.gcd(lcm,t)
    lcm=lcm*t//a
print(lcm)

### FIXED CODE ###

def gcd(x,y):
    if x<y:
        x,y=y,x
    if y==0:
        return x
    if y==1:
        return 1
    else:
        return gcd(y,x%y)
n=int(input())
t=int(input())
lcm=t
a=t
for i in range(n-1):
    t=int(input())
    a=gcd(lcm,t)
    lcm=lcm*t//a
print(lcm)
s=input()
s.sort()
if s[0]==s[1] and s[2]==s[3]:print('Yes')
else:print('No')

### FIXED CODE ###

s=list(input())
s.sort()
if s[0]==s[1] and s[2]==s[3] and s[1]!=s[2]:print('Yes')
else:print('No')
import statistics
import math
N, A, B = map(int, input().split())
v = [int(x) for x in input().split()]
v.sort()

base = v[N-A:]
rem = v[:N-A]
mean_max = statistics.mean(base)
cnb = 0
while mean_max == statistics.mean(base) or not len(rem) == 0:
    same = base.count(base[0])
    extra = rem.count(base[0])
    cnb += math.factorial(same+extra)/math.factorial(same)/math.factorial(extra)
    base.append(rem[len(rem)-1])
    rem = rem.pop
print(mean_max)
print(math.floor(cnb))

### FIXED CODE ###

N, A, B = map(int, input().split())
V = sorted([int(x) for x in input().split()],reverse=True)
from statistics import mean
from math import comb
maxmean = mean(V[:A])
if V[0] != V[A-1]:
    n = V.count(V[A-1])
    k = V[:A].count(V[A-1])
    way = comb(n, k)
else:
    n = V.count(V[A-1])
    way = sum(comb(n, k) for k in range(A, min(n,B)+1))
print(maxmean)
print(way)
N,K=(int(x) for x in input().split())
A=list(map(int, input().split()))
if K<=2*N:
    s=1
    for i in range(K):
        s=A[s-1]
    print(s)
else:
    s=1
    S={1}
    iloop=1
    while A[s-1] not in S:
        S.add(A[s-1])
        s=A[s-1]
        iloop=iloop+1
    p=s
    loop=0
    while A[s-1] != p:
        loop=loop+1
        s=A[s-1]
    g=(K-iloop)%loop+iloop
    s=1
    for i in range(g):
        s=A[s-1]
    print(s)


### FIXED CODE ###

N,K=(int(x) for x in input().split())
A=list(map(int, input().split()))
if K<=N:
    s=1
    for i in range(K):
        s=A[s-1]
    print(s)
else:
    s=1
    S={1}
    iloop=1
    while A[s-1] not in S:
        S.add(A[s-1])
        s=A[s-1]
        iloop=iloop+1
    p=s
    loop=1
    while A[s-1] != p:
        loop=loop+1
        s=A[s-1]
    g=(K-iloop)%loop+iloop
    s=1
    for i in range(g):
        s=A[s-1]
    print(s)
a, b = map(int,input().split())


from math import gcd

def lcm(x, y):
    return (x * y) // gcd(x, y)

print(lcm(a,b))

### FIXED CODE ###

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


from fractions import gcd

def lcm(x, y):
    return (x * y) // gcd(x, y)

print(lcm(a,b))
N = int(input())
nums =[]
count = 0
switch = False
for i in range(N):
    nums.append([int(x) for x in input().split()]

for j in nums:
    if j[0] == j[1]:
        count += 1
    elif j[0] != j[1]:
        count = 0
    if count == 3:
        switch = True
if switch == True:
    print("Yes")
elif switch == False:
    print("No")

### FIXED CODE ###

N = int(input())
nums =[]
count = 0
switch = False
for i in range(N):
    nums.append([int(x) for x in input().split()])

for j in nums:
    if j[0] == j[1]:
        count += 1
    elif j[0] != j[1]:
        count = 0
    if count == 3:
        switch = True
if switch == True:
    print("Yes")
elif switch == False:
    print("No")
N = int(input())
x = []
y = []
h = []
for i in range(N):
    (tmp_x, tmp_y, tmp_h) = map(int, input().split())
    x.append(tmp_x)
    y.append(tmp_y)
    h.append(tmp_h)

def CalcHigh(cx, cy, px, py, ph):
    ch = ph + abs(cx-px) + abs(cy-py)
    return ch

for i in range(101):
    for j in range(101):
        ch = CalcHigh(i, j, x[0], y[0], h[0])
        flag = True
        for k in range(N):
            if CalcHigh(i, j, x[k], y[k], h[k]) != ch:
                flag = False
                break
        if flag == True:
            ans = (i, j, ch)
            break
    else:
        continue
    break

print(ans[0], ans[1], ans[2])





### FIXED CODE ###

N = int(input())
x = []
y = []
h = []
for i in range(N):
    (tmp_x, tmp_y, tmp_h) = map(int, input().split())
    x.append(tmp_x)
    y.append(tmp_y)
    h.append(tmp_h)

def CalcHigh(cx, cy, px, py, ph):
    ch = ph + abs(cx-px) + abs(cy-py)
    return ch

for i in range(101):
    for j in range(101):
        ch = 0
        for k in range(N):
            if h[k] > 0:
                ch = CalcHigh(i, j, x[k], y[k], h[k])

        flag = True
        for k in range(N):
            if ch > 0:
                if h[k] == 0:
                    if CalcHigh(i, j, x[k], y[k], h[k]) < ch:
                        flag = False
                        break
                else:
                    if CalcHigh(i, j, x[k], y[k], h[k]) != ch:
                        flag = False
                        break

        if flag == True:
            ans = (i, j, ch)
            break

print(ans[0], ans[1], ans[2])
N,M = map(int,input().split())
a = []
for i in range(1,int(M**0.5)):
    if M%i == 0:
        if i <= N:
            a.append(i)
        else:
            a.append(int(M/i))
print(max(a))

### FIXED CODE ###

N,M = map(int,input().split())
a = []
for i in range(1,int(M**0.5)+1):
    if M%i == 0:
        a.append(i)
        a.append(int(M/i))
a.sort(reverse = True)
for i in a:
    if i <= M/N:
        print(i)
        break
w=int(input().split()[1])
c=[input() for _ in [0]*w]
for _c in c:
    print(_c)
    print(_c)

### FIXED CODE ###

h=int(input().split()[0])
c=[input() for _ in [0]*h]
for _c in c:
    print(_c)
    print(_c)
from itertools import accumulate
N = int(input())
A = list(map(int,input().split()))

l = 0
r = 1
tmp = A[0]
ans = 0
while l<n:
    if r==n:
        ans += r-l
        l += 1
    elif tmp+a[r] == tmp^a[r]:
        tmp = tmp+a[r]
        r += 1
    else:
        ans = r-l
        tmp = tmp-a[l]
        l += 1
print(ans)

### FIXED CODE ###

from itertools import accumulate
N = int(input())
A = list(map(int,input().split()))

l = 0
r = 1
tmp = A[0]
ans = 0
while l<N:
    if r==N:
        ans += r-l
        l += 1
    elif tmp+A[r] == tmp^A[r]:
        tmp = tmp+A[r]
        r += 1
    else:
        ans += r-l
        tmp = tmp-A[l]
        l += 1
print(ans)
N,Q = [int(i) for i in input().split()]
aaabbb = [[int(i) for i in input().split()] for j in range(N-1)]
pppxxx = [[int(i) for i in input().split()] for j in range(Q)]

tree = [[] for i in range(N+1)]

for a,b in aaabbb:
    a = a
    b = b
    tree[a].append(b)

#print(tree)

counter = [0 for i in range(N+1)]

def dfs(pos,x):
    #print(pos)
    counter[pos]+=x
    for next_pos in tree[pos]:
        dfs(next_pos,x)

for p,x in pppxxx:
    #print("newdfs")
    dfs(p,x)

print(counter[1:])


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N,Q = [int(i) for i in input().split()] #N個の頂点、Q回の操作
aaabbb = [[int(i) for i in input().split()] for j in range(N-1)] #木の辺
pppxxx = [[int(i) for i in input().split()] for j in range(Q)] #操作

tree = [[] for i in range(N+1)]

for a,b in aaabbb:
    tree[a].append(b)
    tree[b].append(a)

#print(tree)

counter = [0 for i in range(N+1)]

for p,x in pppxxx:
    counter[p] += x

#print(counter)

def dfs(pos,parent,add):
    counter[pos] += add
    for next_pos in tree[pos]:
        if not next_pos == parent:
            dfs(next_pos,pos,counter[pos])

dfs(1,0,0)

#print(counter)

print(" ".join([str(i) for i in counter[1:]]))
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)

for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

res = [set() for _ in range(N + 1)]
Q = int(input())
qd = [0] * Q
qc = [0] * Q
for i in range(Q):
  v, d, c = map(int, input().split())
  qd[i] = d
  qc[i] = c
  res[v].add(i)
#print(qd)

def clean():
  global res
  for i in range(1, N + 1):
    a = sorted(res[i], reverse = True)
    d = -1
    for j in range(len(a)):
      x = a[j]
      if qd[x] <= d: res[i].discard(y)
      d = max(d, qd[x])
clean()
for t in range(10):
  tres = [set() | s for s in res]
  for x in range(1, N + 1):
    for y in e[x]:
      for z in res[x]:
        if qd[z] > t: tres[y].add(z)
  res = tres
  clean()
#print(res)

for r in res[1: ]:
  if len(r): print(qc[max(r)])
  else: print(0)

### FIXED CODE ###

import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)

for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)
mxd = 0
res = [[-1] * 11 for _ in range(N + 1)]
Q = int(input())
qd = [0] * Q
qc = [0] * Q
for i in range(Q):
  v, d, c = map(int, input().split())
  qd[i] = d
  qc[i] = c
  res[v][d] = i
  mxd = max(mxd, d)
#print(qc)

#print(mxd)
for t in range(mxd):
  tres = [x[: ] for x in res]
  for x in range(1, N + 1):
    for y in e[x]:
      for i in range(t + 1, 11):
        res[y][i] = max(res[y][i], tres[x][i])

#print(res)
for r in res[1: ]:
  x = -1
  for i in range(11):
    if r[i] != -1: x = max(x, r[i])
  if x == -1: print(0)
  else: print(qc[x])
def main():

    N = int(input())
    if 0 > N or N > 100:
        print("input N error")
        exit()
        
    a = []
    for i in range(N):
        b = input().split()
        if len(b[0]) > 10 or len(b[0]) < 1:
            print("input S error")
            exit()

        if int(b[1]) < 0 or int(b[1]) > 100:
            print("input P error")
            exit()

        b.append(i + 1)
        a.append(b)
        
    a.sort()
    c = []
    answer = []
    
    for i in range(len(a) - 1):
        c.append(a[i])
        
        if a[i][0] != a[i+1][0] and i != len(a) - 2:
            c.sort(key=lambda x: int(x[1]), reverse=True)
            answer += c
            c = []

        elif a[i][0] != a[i+1][0] and i == len(a) - 2:
            c.sort(key=lambda x: int(x[1]), reverse=True)
            answer += c
            answer += a[i + 1]
            c = []
            
        elif a[i][0] == a[i+1][0] and i == len(a) - 2:
            c.append(a[i + 1])
            c.sort(key=lambda x: int(x[1]), reverse=True)
            answer += c
            break
            
    for i in range(len(answer)):
        print(answer[i][2])
        
        
if __name__ == '__main__':

    main()

    


### FIXED CODE ###

def main():

    N = int(input())
    if 0 > N or N > 100:
        print("input N error")
        exit()
        
    answer = []
    for i in range(N):
        s, p = input().split()
        answer.append([s, -int(p), i+1])

    answer.sort()
    for i in range(len(answer)):
        print(answer[i][2])
        
        
if __name__ == '__main__':

    main()
S,T=map(int,input().split())
A,B=map(int,input().split())
U=input()

if S==U:
    print(A-1,B)
if T==U:
    print(A,B-1)

### FIXED CODE ###

S,T=input().split()
A,B=map(int,input().split())
U=input()

if S==U:
    print(A-1,B)
if T==U:
    print(A,B-1)