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

import heapq
N = int( input())
A = [ list( map( int, input().split())) for _ in range(N)]
Q = []
for i in range(N-1):
    for j in range(i+1,N):
        heapq.heappush(Q, [A[i][j],i,j])
WF = [ [10**9+1]*N for _ in range(N)]
for i in range(N):
    WF[i][i] = 0
cnt = 0
while Q:
    a, s, g = heapq.heappop(Q)
    addcheck = 1
    for i in range(N):
        if i == s or i == g:
            continue
        else:
            if WF[s][i] + WF[i][g] == a:
                addcheck = 0
            elif WF[s][i] + WF[i][g] < a:
                 break
    else:
        WF[s][g] = a
        WF[g][s] = a
        if addcheck:
            cnt += a
        continue
    print(-1)
    break
else:
    print( cnt)

### FIXED CODE ###

import heapq
N = int( input())
A = [ list( map( int, input().split())) for _ in range(N)]
Q = []
for i in range(N-1):
    for j in range(i+1,N):
        heapq.heappush(Q, [A[i][j],i,j])
WF = [ [10**9+1]*N for _ in range(N)]
for i in range(N):
    WF[i][i] = 0
cnt = 0
while Q:
    a, s, g = heapq.heappop(Q)
    addcheck = 1
    for i in range(N):
        if i == s or i == g:
            continue
        else:
            if WF[s][i] + WF[i][g] == a:
                addcheck = 0
            elif WF[s][i] + WF[i][g] < a:
                 break
    else:
        WF[s][g] = a
        WF[g][s] = a
        if addcheck:
            cnt += a
        continue
    print(-1)
    break
else:
    print( cnt)
### BUGGY CODE ###

r, c, k = map(int, input().split())

dp = [[[0,0,0,0] for _j in range(c+1)] for _i in range(2)]
bord = [[0]*(c+1) for _i in range(r)]

for _i in range(k):
    _r, _c, _v = map(int, input().split())
    bord[_r-1][_c-1] = _v
            
for i in range(r):
    for j in range(c):
        dp[1][j][0] = max(dp[0][j])
        dp[1][j][1] = dp[1][j][0] + bord[i][j]
        for x in range(1, 4):
            dp[1][j][x] = max(
                dp[1][j][x],
                dp[1][j-1][x],
                dp[1][j-1][x-1]+bord[i][j],             
            )
        dp[0] = dp[1][::]

print(max(dp[1][c-1]))

### FIXED CODE ###

r, c, k = map(int, input().split())

dp = [[[0,0,0,0] for _j in range(c+1)] for _i in range(2)]
bord = [[0]*(c+1) for _i in range(r)]

for _i in range(k):
    _r, _c, _v = map(int, input().split())
    bord[_r-1][_c-1] = _v
            
for i in range(r):
    for j in range(c):
        dp[1][j][0] = max(dp[0][j])
        dp[1][j][1] = max(
            dp[1][j][0] + bord[i][j],
            dp[1][j-1][1],
            dp[1][j-1][0]+bord[i][j]
        )

        dp[1][j][2] = max(
            dp[1][j-1][2],
            dp[1][j-1][1]+bord[i][j],             
        )
        dp[1][j][3] = max(
            dp[1][j-1][3],
            dp[1][j-1][2]+bord[i][j],             
        )

    dp[0] = dp[1][::]

print(max(dp[1][c-1]))
### BUGGY CODE ###

N, M = map(int, input().split())
keys = set()
for i in range(1, N+1):
    keys.add(i)
for _ in range(M):
    akey = set()
    l, r = map(int, input().split())
    for i in range(l, r+1):
        akey.add(i)
    keys = keys & akey
print(len(keys))


### FIXED CODE ###

N, M = map(int, input().split())
L, R = map(int, input().split())
if M == 1:
    print(R - L + 1)
    exit()
for _ in range(M-1):
    l, r = map(int, input().split())
    if l <= R and L <= r:
        L = max(L, l)
        R = min(R, r)
    else:
        print(0)
        exit()
print(R - L + 1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N, Q = map(int, input().split())

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

points = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    points[p-1] += x

def dfs(v, par):
    for nv in edges[v]:
        if nv == par:
            continue
        points[nv] += points[v]
        dfs(nv, v)

dfs(0, -1)

print(*points)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N, Q = map(int, input().split())

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

points = [0]*N
for _ in range(Q):
    p, x = map(int, input().split())
    points[p-1] += x

def dfs(v, par):
    for nv in edges[v]:
        if nv == par:
            continue
        points[nv] += points[v]
        dfs(nv, v)

dfs(0, -1)

print(*points)
### BUGGY CODE ###

from math import factorial
 
def comb(n,k,p):
  if n<0 or k<0 or n<k: return 0
  if n==0 or k==0: return 1
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
 
X, Y=map(int, input().split())
 
def f(x, y):
  s=max(x, y)
  t=min(x, y)
  st=s+t
  ans=1
  for i in range(1, t+1):
    ans=ans*(st+1-i)//i
    ans=ans%(10**9+6)
    
  return ans
  
      
b=(2*X-Y)//3
btemp=(2*X-Y)%3
if btemp>0:
  ans=0
else:
  a=(Y-b)//2
  
  #ans=mt.factorial(a+b)//(mt.factorial(a)*mt.factorial(b))
  #ans=tool.permutations(a+b)//(tool.permutations(a)*tool.permutations(b))
  s=max(a, b)
  t=min(a, b)
  ans=comb(s+t, t, 10**9+7)
print(ans)

### FIXED CODE ###

p=10**9+7
X, Y=map(int, input().split())

if (X+Y)%3>0:
  print(0)
  exit()
  
a=(2*X-Y)//3
b=(2*Y-X)//3

if a*b<0:
  print(0)
  exit()

ab=a+b
ue=[1]*(ab+1)
for i in range(1, ab+1):
  ue[i]=ue[i-1]*i%p
  
out=ue[-1]*pow(ue[a], p-2, p)%p
out=out*pow(ue[b], p-2, p)%p

print(out)
### BUGGY CODE ###

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

MAX = 10**9

dp = [MAX for i in range(n)]
dp[0] = 0

for i in range(n):
    for j in range(i + 1, i + k + 1):
        if j < n:
            dp[j] = min(dp[j], dp[i] + abs(arr[j] - arr[i]))

print(dp[-1])


### FIXED CODE ###

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

MAX = 10**9

dp = [MAX for i in range(n)]
dp[0] = 0

for i in range(n):
    for j in range(i + 1, i + k + 1):
        if j < n:
            dp[j] = min(dp[j], dp[i] + abs(arr[j] - arr[i]))

print(dp[-1])
### BUGGY CODE ###

n = int(input())
ans=0
for i in range(1, n):
    ans += i
print(ans)
        


### FIXED CODE ###

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

s = input()[::-1]
n = len(s)
amari = [0]*2019
amari[0] = 1

temp = 0
d = 1
for char in s:
    temp += int(char)*d
    amari[temp%2019] += 1
    d *= 10

ans = 0
for i in amari:
    ans += i*(i-1)/2

print(int(ans))



### FIXED CODE ###

s = input()[::-1]
n = len(s)
amari = [0]*2019
amari[0] = 1

temp = 0
d = 1
for char in s:
    temp += int(char)*d
    temp %= 2019
    d *= 10
    d %= 2019  
    amari[temp] += 1

ans = 0
for i in amari:
    ans += i*(i-1)/2

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

import sys
n, k = map(int, input().split())
h = list(map(int, input().split(' ')))

dp = [sys.maxsize for _ in range(n)]


dp[0] = 0
for i in range(n):
    for j in range(1, k+1):
        if (i+j >= n):
            break
        dp[i+j] = min(dp[i+j], abs(h[i] - h[i+j]) + dp[i])


print(dp[n-1])


### FIXED CODE ###

import numpy as np
n, k = map(int, input().split())
h = list(map(int, input().split(' ')))
h = np.array(h)

dp = np.zeros(n, dtype=int)


dp[0] = 0
i = 0
j = 0
for i in range(1, n):
    j = max(0, i-k)
    dp[i] = np.min(dp[j:i] + np.abs(h[i] - h[j:i]))


print(dp[n-1])
### BUGGY CODE ###

import sys

N = int(sys.stdin.readline())
A = tuple(map(int, sys.stdin.readline().split()))
B = []
ans = 0
for i in A:
    B.append(list(bin(i)[2:]))
C = [0 for i in range(60)]
for i in B:
    for l in range(len(i)):
        if i[-(l+1)] == '1':
            C[l] += 1
for i in range(60):
    ans = (ans + C[i]*(N-C[i])*(2**i))%(10**9+7)
print(ans)

### FIXED CODE ###

import sys
mod = 10**9+7
N = int(sys.stdin.readline())
A = tuple(map(int, sys.stdin.readline().split()))
B = []
ans = 0
C = [0 for i in range(60)]
for i in A:
    for l in range(60):
        if ((i >> l) & 1) == 1:
            C[l] += 1
for i in range(60):
    t = C[i]
    ans = (ans + t*(N-t)*(2**i)) % mod
print(ans)
### BUGGY CODE ###

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

x = 0
y = 0
for t, a in TA:
    if x <= t and y <= a:
        x = t
        y = a
    else:
        if t >= a:
            while(1):
                if (x*a) % t == 0 and (x*a) // t >= y:
                    y = (x*a) // t
                    break
                else:
                    x += 1
        else:
            while(1):
                if (y*t) % a == 0 and (y*t) // a >= x:
                    x = (y*t) // a
                    break
                else:
                    y += 1

print(x+y)


### FIXED CODE ###

import math
N = int(input())
TA = [list(map(int, input().split())) for i in range(N)]

x = 1
y = 1
for t, a in TA:
    if x <= t and y <= a:
        x = t
        y = a
    else:
        v = max(-(-x//t), -(-y//a))
        x = v * t
        y = v * a


print(x+y)
### BUGGY CODE ###

N,K=map(int,input().split())
P=list(map(int,input().split()))
C=list(map(int,input().split()))
a=[]
s=set()
for i in range(N):
    idx=P[i]-1
    z=set()
    tl=[]
    rl=[]
    c=0
    tc=0
    while idx not in z and c<K:
        tl.append(C[idx])
        tc+=C[idx]
        rl.append(tc)
        s.add(tc)
        z.add(idx)
        idx=P[idx]-1
        c+=1
    if c<K:
        d,m=divmod(K,c)
        if m==0:
            d-=1
            m=c
        tc=d*tc
        tc+=max(rl[:m])
        s.add(tc)
print(max(s))

### FIXED CODE ###

N,K=map(int,input().split())
P=list(map(int,input().split()))
C=list(map(int,input().split()))
a=[]
ans=-10**10
for i in range(N):
    idx=P[i]-1
    z=set()
    rl=[]
    c=0
    tc=0
    while idx not in z and c<K:
        tc+=C[idx]
        rl.append(tc)
        ans=max(ans,tc)
        z.add(idx)
        idx=P[idx]-1
        c+=1
    if c<K:
        d,m=divmod(K,c)
        if m==0:
            d-=1
            m=c
        tc=d*tc
        tc+=max(rl[:m])
        ans=max(ans,tc)
print(ans)
### BUGGY CODE ###

newlst = []
lst =[]
m = int(input())
for i in range(m):
    a = str(input())
    lst.append(a)
for j in lst:
    if j not in newlst:
        newlst.append(j)
print(len(newlst))

### FIXED CODE ###

newlst = []
lst =[]
m = int(input())
while m > 0:
    a = str(input())
    lst.append(a)
    m = m -1
newlst = list(dict.fromkeys(lst))
print(len(newlst))
### BUGGY CODE ###

import sys
N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]
road_length = sum(sum(a) for a in A) //2

for k in range(N):
    for i in range(N):
        for j in range(i+1,N):
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                sys.exit()
            if A[i][j] == A[i][k] + A[k][j] and i != k and j != k:
                road_length -= A[i][j]
ans = road_length
print(ans)
            



### FIXED CODE ###

def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()
### BUGGY CODE ###

N = int(input())
A = []
for i in range(0,N):
  A.append(int(input()))
#print(A)
print(max(A[1:]))
for j in range(1,N-1):
  print(max(A[:j]+A[j+1:]))
print(max(A[:N-1]))

### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
  A.append(int(input()))
max1 = 0
max2 = 0
for i in range(N):
  if max1 < A[i]:
    max2 = max1
    max1 = A[i]
  elif A[i] > max2:
    max2 = A[i]

for j in range(N):
  if A[j] == max1:
    print(max2)
  else:
    print(max1)
### BUGGY CODE ###

A = list(input())
while A != [] and A != [0]:
    if A[:7] == list("dreamer") and A[5:10] != list("erase"):
        A = A[7:]
    elif A[:5] == list("dream"):
        A = A[5:]
    elif A[:6] == list("eraser"):
        A = A[6:]
    elif A[:5] == list("erase"):
        A = A[5:]
    else:
        A = [0]
if A == []:
    print("YES")
else:
    print("NO")


### FIXED CODE ###

s = input().replace("eraser", "").replace("erase", "")
s = s.replace("dreamer", "").replace("dream", "")
if s:
    print("NO")
else:
    print("YES")
### BUGGY CODE ###

import sys
from io import StringIO
import unittest


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

    loop_list = []
    now = 0

    if k > n:
        while 1:
            now = a[now] - 1

            if now + 1 in loop_list:
                s_index = loop_list.index(now + 1)
                before_loop = s_index
                loop_list = loop_list[s_index:]
                break
            else:
                loop_list.append(now + 1)

        l = len(loop_list)
        k -= before_loop

        # print(loop_list, l, before_loop)
        print(loop_list[k % l - 1])
    else:
        for _ in range(k):
            now = a[now] - 1

        print(now + 1)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """4 5
3 2 4 1"""
        output = """4"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """6 727202214173249351
6 5 2 5 3 2"""
        output = """2"""
        self.assertIO(input, output)


if __name__ == "__main__":
    # unittest.main()
    resolve()


### FIXED CODE ###

import sys
from io import StringIO
import unittest


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

    loop_list = []
    loop_set = set()
    now = 0

    if k > n:
        for _ in range(k):
            now = a[now] - 1

            if now + 1 in loop_set:
                s_index = loop_list.index(now + 1)
                before_loop = s_index
                loop_list = loop_list[s_index:]
                break
            else:
                loop_list.append(now + 1)
                loop_set.add(now + 1)

        l = len(loop_list)
        k -= before_loop

        # print(loop_list, l, before_loop)
        print(loop_list[k % l - 1])
    else:
        for _ in range(k):
            now = a[now] - 1

        print(now + 1)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """4 5
3 2 4 1"""
        output = """4"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """6 727202214173249351
6 5 2 5 3 2"""
        output = """2"""
        self.assertIO(input, output)


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

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

for i in range(K):
    lis = [0] * (N+1)
    for j in range(N):
        lis[min(N,j+A[j]+1)] -= 1
        lis[max(0, j-A[j])] += 1
    cnt = 0
    for j in range(N):
        cnt += lis[j]
        A[j] = cnt

    cnt2 = 0
    for j in range(N):
        if A[j] == N:
            cnt2 += 1
    if cnt2 == N:
        break
    #print(lis)
print(' '.join(map(str,A)))


### FIXED CODE ###

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

for i in range(K):
    lis = [0] * (N+1)
    for j in range(N):
        lis[min(N,j+A[j]+1)] -= 1
        lis[max(0, j-A[j])] += 1
    cnt = 0
    for j in range(N):
        cnt += lis[j]
        A[j] = cnt

    cnt2 = 0
    for j in range(N):
        if A[j] == N:
            cnt2 += 1
    if cnt2 == N:
        break
    #print(lis)
print(' '.join(map(str,A)))
### BUGGY CODE ###

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

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

d = {}
disabled = set()
for i in range(len(A)):
    # save
    divisors = make_divisors(A[i])
    for divisor in divisors:
        if divisor not in d:
            d[divisor] = [i]
        else:
            d[divisor].append(i)
    # judge
    if A[i] in d:
        for item in d[A[i]]:
            if item != i:
                disabled.add(item)
                if A[item] == A[i]:
                    disabled.add(i)

# print(disabled)
print(len(A) - len(disabled))

### FIXED CODE ###

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

max_number = max(A) + 1
ng = [False] * max_number
counter = 0
prev = 0
for ai in A:
    if ai == prev:
        counter -= 1
        prev = 0
    if not ng[ai]:
        counter += 1
        prev = ai
    for i in range(ai, max_number, ai):
        ng[i] = True
print(counter)
### BUGGY CODE ###

a=[]
n= int(input())
a=list(map(int,input().split()))
ans=1
for i in (a):
    ans=ans*i

if ans<=(10**18):
    print(ans)
else:
    print(-1)

### FIXED CODE ###

n= int(input())
a=list(map(int,input().split()))
a.sort()
ans=1
for i in a:
    ans=ans*i
    if ans>(10**18):
        print(-1)
        break
    elif ans==0:
        print(ans)
        break
if ans<=(10**18)and ans!=0:
    print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
mod=10**9+7
dp=[0 for i in range(N+1)]
dp[0]=1
dp[-1]=0
A=[]
for i in range(M):
  A.append(int(input()))
#print(A)
for i in range(1,N+1):
  if i in A:
    continue
  else:
    dp[i]=(dp[i-1]+dp[i-2])%mod
print(dp[N]%mod)


### FIXED CODE ###

N,M=map(int,input().split())
mod=10**9+7
dp=[0]*(N+1)
dp[0]=1
dp[-1]=0
A=[]
for i in range(M):
  A.append(int(input()))
A=set(A)
#print(A)
for i in range(1,N+1):
  if dp[i-1]==0 and dp[i-2]==0:
    break
  elif i in A:
    continue
  else:
    dp[i]=(dp[i-1]+dp[i-2])%mod
print(dp[N]%mod)
### BUGGY CODE ###

N = int(input())
S = str(input())
cnt = 0
for k in range(2, N):
    for j in range(1, k):
        for i in range(0, j):
            if i < j < k and S[i] != S[j] and S[j] != S[k] and S[k] != S[i] and (j - i) != (k - j):
                cnt += 1

print(cnt)

### FIXED CODE ###

n = int(input())
s = input()

r = s.count('R')
g = s.count('G')
b = s.count('B')

ans = r*g*b

cnt = 0
for i in range(n):
    for d in range(n):
        j = i + d
        k = j + d
        if k >= n:break
        if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            ans -= 1
ans -= cnt

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

import sys


def Sieve(N, AList):
    AList.sort(key = lambda x: x[0])

    N_NotDivisible = 0
    index = 0
    while( index < N ):
        if( AList[index][1]==True):
            if(index ==N-1):
                N_NotDivisible += 1
                break
            elif(AList[index][0] != AList[index+1][0]):
                N_NotDivisible += 1
            else:
                AList[index][1]= False
            for i in range(index+1, N, 1):
                if(AList[i][1]==False or AList[i][0] % AList[index][0]==0):
                    AList[i][1]=False

        index += 1
    #print(Mins)
    return N_NotDivisible

if(__name__ == "__main__"):

    N = int( input().strip() )
    AList_str = input().strip().split()

    AList = [ [0, True] for i in range(N) ]
    for i in range(N):
        AList[i][0] = int(AList_str[i])

    N_NotDivisible= Sieve(N, AList)
    print(N_NotDivisible)


### FIXED CODE ###

import sys

def Sieve2(N, AList, Bools, Max_A):
    N_NotDivisible = 0
    value = 0
    for i in range(N):
        if(AList[i]>value):
            value = AList[i]
            if(Bools[value]==True):
                N_NotDivisible += 1

            for j in range(2, Max_A//value+1, 1 ):
                Bools[j*value] = False
    #print(Mins)
    return N_NotDivisible


if(__name__ == "__main__"):

    N = int( input().strip() )
    AList_str = input().strip().split()
    Max = 0
    AList = [0] * N
    for i in range(N):
        AList[i] = int(AList_str[i])
        Max = max(AList[i], Max)
    Bools = [False] * (Max+1)
    AList.sort()
    Dups = []
    for Num in range(N):
        value = AList[Num]
        Bools[value] = True
        if(Num < N-1 and AList[Num] == AList[Num+1]):
            Dups.append(value)
    for Num in range(len(Dups)):
        value = Dups[Num]
        Bools[value] = False


    N_NotDivisible= Sieve2(N, AList, Bools, Max)
    print(N_NotDivisible)
### BUGGY 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 = map(int, input().split(' '))

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

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

Q = int(input())


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

res = ['0']*N

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


print('\n'.join(res))


### 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 ###

n, w = (int(x) for x in input().split())
wv = [[0, 0]]
for _ in range(n):
    wv.append([int(x) for x in input().split()])
vmax = max(wv, key=lambda x:x[1])[1]
dp = [[float('inf')] * (n * vmax + 1) for _ in range(n + 1)]
for i in range(w + 1):
    dp[0][0] = 0
for i in range(1, n + 1):
    for j in range(0, n * vmax + 1):
        if j - wv[i][1] >= 0:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - wv[i][1]] + wv[i][0])
        else:
            dp[i][j] = dp[i - 1][j]
ans = 0
for i in range(n * vmax, -1, -1):
    if dp[n][i] <= w:
        ans = i
        break
print(ans)

### FIXED CODE ###

n, w = (int(x) for x in input().split())
wv = [[0, 0]]
for _ in range(n):
    wv.append([int(x) for x in input().split()])
vmax = max(wv, key=lambda x:x[1])[1]
dp = [[float('inf')] * (n * vmax + 1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(1, n + 1):
    for j in range(0, n * vmax + 1):
        if j - wv[i][1] >= 0:
            dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - wv[i][1]] + wv[i][0])
        else:
            dp[i][j] = dp[i - 1][j]
for i in range(n * vmax, -1, -1):
    if dp[n][i] <= w:
        ans = i
        break
print(ans)
### BUGGY CODE ###

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

con = 0

for i in range(1,N):
  if P[i] <= min(P[:i]):
    con += 1

print(con + 1)

### FIXED CODE ###

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

inf = 10 ** 9

Q = [inf] * N

m = inf

con = 0

for i in range(0,N):
  if P[i] <= m:
    m = P[i]
  Q[i] = m
  if P[i] <= Q[i]:
    con += 1

print(con)