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

import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000)

n,q=map(int,input().split())
G=[[] for i in range(n)] #隣接配列
P=[0]*n #根のポイント
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
for i in range(q):
    p,x=map(int,input().split())
    p-=1
    P[p]+=x
    

def dfs(s,p=-1,cnt=0):
    cnt+=P[s]
    P[s]=cnt
    for i in G[s]:
        if i!=p:
            dfs(i,s,cnt)

dfs(0)
print(*P,sep=" ")

### FIXED CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque

def main():
    n,q=map(int,input().split())
    G=[[] for i in range(n)] #隣接配列
    P=[0]*n #親のポイント
    for i in range(n-1):
        a,b=map(int,input().split())
        a-=1
        b-=1
        G[a].append(b)
        G[b].append(a)
    for i in range(q):
        p,x=map(int,input().split())
        p-=1
        P[p]+=x
    
    Chk=[0]*n #訪問済みチェック
    q=deque([0])
    while q: #qが空になるまで(BFS:幅優先探索)
        now=q.popleft() #取り出す
        Chk[now]=1 #訪問済みにする
        for i in G[now]: #子に対し
            if Chk[i]==0: #未訪問のとき
                P[i]+=P[now] #ポイント加算
                q.append(i) #親としてqに入れる

    print(*P)

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

n = int(input())
apple = []
for _ in range(n):
    apple.append(str(input()))
a = set(apple)
count = 0
for i in a:
    b = apple.count(i)
    if b%2 != 0:
        count += 1
    else:
        pass
print(count)

### FIXED CODE ###

n = int(input())
apple = []
for _ in range(n):
    apple.append(int(input()))
apple = sorted(apple)
apple.append(0)
count = 0
ans = 1
for i in range(n):
    if apple[i] == apple[i + 1]:
        ans += 1
    else:
        if ans%2 == 0:
            ans = 1
        else:
            count += 1
print(count)
### BUGGY CODE ###

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

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

SD=[0]*N

for i in range(N):
    if i==K-1:continue
    ans=[]
    seen=[0]*N
    stack=[[i,0]]
    seen[i]=1
    while stack:
        x,d=stack.pop()
        if x==K-1:
            ans.append(d)
        else:
            for y,co in G[x]:
                if seen[y]==0:
                    stack.append([y,d+co])
                    seen[y]=1
    SD[i]=min(ans)


for i in range(Q):
    x,y=map(int,input().split())
    ans=SD[x-1]+SD[y-1]
    print(ans)



### FIXED CODE ###

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

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

SD=[0]*N
seen=[0]*N
stack=[]
stack.append([K-1,0])
seen[K-1]=1
while stack:
    x,d=stack.pop()
    for y,d0 in G[x]:
        if seen[y]==0:
            SD[y]=d+d0
            stack.append([y,d+d0])
            seen[y]=1
for i in range(Q):
    x,y=map(int,input().split())
    ans=SD[x-1]+SD[y-1]
    print(ans)
### BUGGY CODE ###

# D - Good Grid

N, C =  map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
c = [list(map(int, input().split())) for _ in range(N)]

group0, group1, group2 = [], [], []
for row in range(N):
    for col in range(N):
        if (row + col) % 3 == 0:
            group0.append(c[row][col] -1)
        elif (row + col) % 3 == 1:
            group1.append(c[row][col] -1)
        else:
            group2.append(c[row][col] -1)

ans = []
for color0 in range(C):
    for color1 in range(C):
        for color2 in range(C):
            if len(set([color0, color1, color2])) == 3:
                tmp = 0
                for x in group0:
                    tmp += D[x][color0]
                for x in group1:
                    tmp += D[x][color1]
                for x in group2:
                    tmp += D[x][color2]
                ans.append(tmp)

print(min(ans))

### FIXED CODE ###

# D - Good Grid

N, C =  map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
c = [list(map(int, input().split())) for _ in range(N)]

group0, group1, group2 = [0]*C, [0]*C, [0]*C
for row in range(N):
    for col in range(N):
        if (row + col) % 3 == 0:
            group0[c[row][col] -1] += 1
        elif (row + col) % 3 == 1:
            group1[c[row][col] -1] += 1
        else:
            group2[c[row][col] -1] += 1

ans = []
for color0 in range(C):
    for color1 in range(C):
        for color2 in range(C):
            if len(set([color0, color1, color2])) == 3:
                tmp = 0
                for idx in range(C):
                    tmp += D[idx][color0] * group0[idx]
                    tmp += D[idx][color1] * group1[idx]
                    tmp += D[idx][color2] * group2[idx]
                ans.append(tmp)

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

N,S = list(map(int, input().split()))
A = list(map(int, input().split()))
mod = 998244353

dp = [[0 for i in range(S+1)] for _ in range(N+1)]
# dp[i][j] Aiまでを使って、合計jを作る作り方
dp[0][0] = 1

for i in range(1,N+1):
  a = A[i-1]
  for j in range(S+1):
    dp[i][j] += dp[i-1][j] * 2
    dp[i][j] %= mod
    if j+a <= S :
      dp[i][j+a] += dp[i-1][j]
      dp[i][j+a] %= mod
print(dp[N][S])

### FIXED CODE ###

N,S = list(map(int, input().split()))
A = list(map(int, input().split()))
mod = 998244353

dp = [[0 for i in range(S+1)] for _ in range(N+1)]
# dp[i][j] Aiまでを使って、合計jを作る作り方
dp[0][0] = 1

for i in range(1,N+1):
  a = A[i-1]
  for j in range(S+1):
    dp[i][j] += dp[i-1][j] * 2
    dp[i][j] %= mod
    if j+a <= S :
      dp[i][j+a] += dp[i-1][j]
      dp[i][j+a] %= mod
print(dp[N][S])
### BUGGY CODE ###

import re
S = input()
s = len(S)
while True:
    T = re.sub("(01|10)","",S)
    if T == S:
        break
    S = T
t = len(T)
print(s-t)

### FIXED CODE ###

S = input()
stack = []
for s in S:
    if not stack:
        stack.append(s)
    else:
        if s == stack[-1]:
            stack.append(s)
        else:
            stack.pop()
print(len(S)-len(stack))
### BUGGY CODE ###

H,W,M = map(int,input().split())
T = [0] * M
H_cnt = {}
W_cnt = {}
HW = {}
for i in range(M):
    h,w = map(int,input().split())
    if not h in H_cnt:
        H_cnt[h] = 0
    if not w in W_cnt:
        W_cnt[w] = 0
    H_cnt[h] += 1
    W_cnt[w] += 1
    HW[(h,w)] = 1

HL = [[h,cnt] for h,cnt in H_cnt.items()]
WL = [[w,cnt] for w,cnt in W_cnt.items()]

HL.sort(key=lambda x: x[1],reverse=True)
WL.sort(key=lambda x: x[1],reverse=True)

HS = []
max_cnt = 0
for h,cnt in HL:
    if max_cnt<=cnt:
        HS.append([h,cnt])
        max_cnt = max(max_cnt,cnt)
        continue
    break

WS = []
max_cnt = 0
for w,cnt in WL:
    if max_cnt<=cnt:
        WS.append([w,cnt])
        max_cnt = max(max_cnt,cnt)
        continue
    break

cnt = 0
ans = 0

# ここの判定を高速にする
#cross_cnt = 0
#for hw in HW.keys():
#    h,w = hw
#    if h in HS and w in WS:
#        cross_cnt+=1


for h,hcnt in HS:
    for w,wcnt in WS:
        if (h,w) in HW:
            cnt = hcnt+wcnt-1
            ans = max(ans,cnt)
            continue
        cnt = hcnt+wcnt
        ans = max(ans,cnt)

print(ans)

















### FIXED CODE ###

H,W,M = map(int,input().split())
T = [0] * M
H_cnt = {}
W_cnt = {}
HW = {}
for i in range(M):
    h,w = map(int,input().split())
    if not h in H_cnt:
        H_cnt[h] = 0
    if not w in W_cnt:
        W_cnt[w] = 0
    H_cnt[h] += 1
    W_cnt[w] += 1
    HW[(h,w)] = 1

HL = [[h,cnt] for h,cnt in H_cnt.items()]
WL = [[w,cnt] for w,cnt in W_cnt.items()]

HL.sort(key=lambda x: x[1],reverse=True)
WL.sort(key=lambda x: x[1],reverse=True)

HS = {}
max_cnth = 0
for h,cnt in HL:
    if max_cnth<=cnt:
        HS[h] = cnt
        max_cnth = max(max_cnth,cnt)
        continue
    break

WS = {}
max_cntw = 0
for w,cnt in WL:
    if max_cntw<=cnt:
        WS[w] = cnt
        max_cntw = max(max_cntw,cnt)
        continue
    break

cnt = 0
ans = 0

# ここの判定を高速にする
cross_cnt = 0
for hw in HW.keys():
    h,w = hw
    if h in HS and w in WS:
        cross_cnt+=1
if len(WS) * len(HS)==cross_cnt:
    print(max_cnth+max_cntw-1)
    exit()
print(max_cnth+max_cntw)


#for h,hcnt in HS:
#    for w,wcnt in WS:
#        if (h,w) in HW:
#            cnt = hcnt+wcnt-1
#            ans = max(ans,cnt)
#            continue
#        cnt = hcnt+wcnt
#        ans = max(ans,cnt)
### BUGGY CODE ###

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

Nums = []
now = 1#今見てる数
cnt = 0#nowがいくつ並んでるか

for i in range(0,n):
    if s[i] == str(now):
        cnt += 1
    else:
        Nums.append(cnt)
        now = 1 - now#０と１の切り替え
        cnt = 1#新しいのをカウントし始める
if cnt != 0:Nums.append(cnt)

#長さが２の倍数であるならば任意の数を最後に加える．ながさを奇数倍にしたい
if len(Nums) % 2 == 0:Nums.append(0)

add = 2 * k + 1 #ひっくり返せる範囲を指定
ans = 0
for i in range(0,len(Nums),2):
    tmp = 0
    left = i#(左端)
    right = min(i + add,len(Nums))#みる長さの最大値を調節（右端）

    for j in range(left,right):
        tmp += Nums[j]

    ans = max(tmp,ans)

print(ans)

### FIXED CODE ###

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

Nums = []
now = 1#今見てる数(１を見て判定していくために最初を１として判定を始める)
cnt = 0#nowがいくつ並んでるか

for i in range(0,n):
    if s[i] == str(now):
        cnt += 1
    else:
        Nums.append(cnt)
        now = 1 - now#０と１の切り替え
        cnt = 1#新しいのをカウントし始める
if cnt != 0:Nums.append(cnt)

#長さが２の倍数であるならば任意の数を最後に加える．ながさを奇数倍にしたい
if len(Nums) % 2 == 0:Nums.append(0)
sum = [0]*(len(Nums)+1)

for i in range(len(Nums)):
    sum[i+1] = sum[i] + Nums[i]

add = 2 * k + 1
ans = 0

for i in range(0,len(sum),2):
    tmp = 0
    left = i
    right = min(i+add,len(Nums))
    tmp = sum[right] - sum[left]
    ans = max(ans,tmp)

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

from collections import defaultdict
n = int(input())
rob = defaultdict(list)
for i in range(n):
    x,l  = map(int,input().split())
    rob[x] = [l,x-l,x+l]
rob = sorted(rob.items(), key=lambda x:x[1])
tmp = []
for idx in range(0,len(rob)-1):
    i,[l,left,right] = rob[idx]
    for idx2 in range(idx+1,len(rob)):
        j,[_,_,_] = rob[idx2]
        if left < j < right:
            tmp.append(idx2)

print(len(rob)-len(set(tmp)))

### FIXED CODE ###

n = int(input())
rob = []
for i in range(n):
    x,l = map(int,input().split())
    rob.append([x-l,x+l])
rob.sort()
ans  = n
right = rob[0][1]
for i,[l,r] in enumerate(rob):
    if i == 0:
        continue
    if l < right:
        ans -= 1
        right = min(right,r)
    else:
        right = r
print(ans)
### BUGGY CODE ###

X,Y,Z,K = list(map(int,input().split()))
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
DD = []
A.sort()
B.sort()
C.sort()
for i in A:
    for j in B:
       DD.append(i+j)
DD.sort()
F = []
for i in DD[min(len(DD)-3010,0):]:
    for j in C:
        F.append(i+j)
F.sort()
for i in range(K):
    print(F[-1-i])
        


### FIXED CODE ###

import sys
import heapq
input = sys.stdin.readline
X,Y,Z,K = list(map(int,input().split()))
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
DD = [i+j for i in A for j in B]
DD.sort()
heap = []
for i in DD[max(len(DD)-3001,0):]:
     for j in C:
         heapq.heappush(heap,-(i+j))
for i in range(K):
    print(-heapq.heappop(heap))
### BUGGY CODE ###

N = int(input())
num_list = list(map(int, input().split()))
 
length = N
amount = 0
for i in range(length-1):
  for j in range(i+1, length):
    num1 = num_list[i]
    num2 = num_list[j]
    bit_num1 = format(num1, "b")
    bit_num2 = format(num2, "b")
    length_num1 = len(bit_num1)
    length_num2 = len(bit_num2)
    max_length = max(length_num1, length_num2)
    bit_num1 = bit_num1.zfill(max_length)
    bit_num2 = bit_num2.zfill(max_length)       
    num = ""
    for k in range(0, max_length):
      if num1 >> k & 1 and not num2 >> k & 1:
        num = "1" + num
      elif not num1 >> k & 1 and num2 >> k & 1:
        num = "1" + num
      else:
        num = "0" + num
    amount += int(num, 2) % (10**9 + 7)

L = 10**9 + 7
print(amount % L)

### FIXED CODE ###

import numpy as np
N = int(input())
num_list = np.array(input().split(), dtype="int")

max_num = max(num_list)
max_bit_num = format(max_num, "b")
max_bit_num_length = len(max_bit_num)
ans = 0
radix = 1
for i in range(max_bit_num_length):
  new_num_list = (num_list >> i) & 1
  one_amount = np.count_nonzero(new_num_list == 1)
  zero_amount = len(num_list) - one_amount
  ans += (one_amount*zero_amount)*radix
  radix *= 2
print(ans%(10**9+7))
### BUGGY CODE ###

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

mod = 10 ** 9 + 7

lcm1 = 1

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

def lcm(a, b):
    return a * b // gcd (a, b)

for i in a:
    lcm1 = lcm(lcm1, i)

ans = 0

for i in a:
    ans += lcm1 // i

print(ans%mod)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
d = {}
ans = 0
mod = 10**9 + 7

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

for i in a:
    arr = factorization(i)
    for j,k in arr:
        if j not in d:
            d[j] = k
        else:
            d[j] = max(k, d[j])

l = 1
for k,v in d.items():
    l *= pow(k,v,mod)
    l %= mod

for i in a:
    ans += l * pow(i, mod-2, mod)
    ans %= mod

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

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

for i in range(1,N+1):
    print(A_list.count(i))

### FIXED CODE ###

import collections
N = int(input())
A_list = list(map(int,input().split()))

g = collections.Counter(A_list)
for i in range(1,N+1):
    print(g[i])
### BUGGY CODE ###

import numpy as np
N = int(input())
A = np.asarray([int(input()) for _ in range(N)], dtype=np.int64)

sum_A = A.sum()
MOD = 998244353

dp1 = np.zeros(sum_A + 1, dtype=np.int64)
dp2 = np.zeros(sum_A + 1, dtype=np.int64)
dp1[0] = dp2[0] = 1
tmp_sum = 0
for a in A:
    for i in reversed(range(tmp_sum + 1)):
        dp1[i] %= MOD
        dp2[i] %= MOD
        dp1[i + a] += dp1[i]
        dp1[i] <<= 1
        dp2[i + a] += dp2[i]
    tmp_sum += a


ans = pow(3, N, MOD)
for i in range(sum_A + 1):
    if i * 2 >= sum_A:
        ans = (ans - dp1[i] * 3 + MOD * 3) % MOD
    if i * 2 == sum_A:
        ans = (ans + dp2[i] * 3) % MOD
print(ans)


### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

sum_A = sum(A)
MOD = 998244353

dp1 = [0] * (sum_A + 1)
dp2 = [0] * (sum_A + 1)
dp1[0] = dp2[0] = 1

for a in A:
    dp1_ = [0] * (sum_A + 1)
    dp2_ = [0] * (sum_A + 1)
    for i in range(sum_A + 1):
        # R に塗った場合
        if i + a <= sum_A:
            dp1_[i + a] = (dp1_[i + a] + dp1[i]) % MOD
            dp2_[i + a] = (dp2_[i + a] + dp2[i]) % MOD
        # G, B に塗った場合
        dp1_[i] = (dp1_[i] + dp1[i] * 2) % MOD
        dp2_[i] = (dp2_[i] + dp2[i]) % MOD
    dp1 = dp1_
    dp2 = dp2_

ans = pow(3, N, MOD)
for i in range(sum_A + 1):
    if i * 2 >= sum_A:
        ans = (ans - dp1[i] * 3 + MOD * 3) % MOD
    if i * 2 == sum_A:
        ans = (ans + dp2[i] * 3) % MOD
print(ans)
### BUGGY CODE ###

import sys
import heapq

input = sys.stdin.readline
n, m = map(int, input().split())
A = list(map(int, input().split()))
heapq.heapify(A)

BC = [list(map(int, input().split())) for _ in range(m)]
BC.sort(key=lambda x: -x[1])

mx = n*2+1
[heapq.heappushpop(A, bc[1]) for bc in BC for _ in range(bc[0]) if len(A) < mx]
print(sum(A))

### FIXED CODE ###

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]
BC.sort(key=lambda x: -x[1])

maxi = n*2
extend = A.extend
[extend([ls[1]] * ls[0]) for ls in BC if len(A) <= maxi]
A.sort(reverse=True)

print(sum(A[:n]))
### BUGGY CODE ###

n = int(input())
x = [input() for i in range(n)]
i = 0
count, yo, list_yo = [], [], []

while not(x == []):
  a = x.count(x[i])
  count.append(a)
  yo.append(x[i])
  x.remove(x[i])
  
for k, c in enumerate(count):
  if c == max(count):
    list_yo.append(yo[k])

list_yo.sort()
for i in range(len(list_yo)):
   print(list_yo[i])



### FIXED CODE ###

import collections
n = int(input())
s = [input() for i in range(n)]
s = collections.Counter(s)
m = 0
ans = []

for i in s.values():
  m = max(m,i)

for k, j in s.items():
  if j == m:
    ans.append(k)
ans.sort()

for i in range(len(ans)):
  print(ans[i])
#print(*ans, sep = "\n")
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def all_group_members(self):
        return [set(self.members(r)) for r in self.roots()]

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    n, m = map(int, input().split())
    P = list(map(lambda x:int(x) - 1, input().split()))
    uf = UnionFind(n)
    for _ in range(m):
        x, y = map(lambda x:int(x) - 1, input().split())
        uf.union(x, y)
    ans = 0
    for g in uf.all_group_members():
        Q = set([p for i, p in enumerate(P) if i in g])
        ans += len(g & Q)
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def all_group_members(self):
        return [set(self.members(r)) for r in self.roots()]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    n, m = map(int, input().split())
    P = list(map(lambda x:int(x) - 1, input().split()))
    uf = UnionFind(n)
    for _ in range(m):
        x, y = map(lambda x:int(x) - 1, input().split())
        uf.union(x, y)
    ans = 0
    for i, p in enumerate(P):
        if uf.same(i, p):
            ans += 1
    print(ans)

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

import heapq
N = int(input())
A = [(-1) * int(input()) for _ in range(N)]

for i in range(N):
    tmp_A = A[:i] + A[i + 1:]
    heapq.heapify(tmp_A)
    print((-1) * heapq.heappop(tmp_A))

### FIXED CODE ###

def MI():
    return map(int, input().split())

def LI():
    return list(map(int, input().split()))

N = int(input())
A = [int(input()) for _ in range(N)]
B = sorted(A)

for i in range(N):
    if A[i] == B[-1]:
        print(B[-2])
    else:
        print(B[-1])
### BUGGY CODE ###

from collections import defaultdict
import sys
from copy import copy
input = sys.stdin.readline
mod = 10**9+7
N, M = map(int, input().split())
S = "".join(input().split())
T = "".join(input().split())
dS = defaultdict(int)
dT = defaultdict(int)
dS[""] += 1
dT[""] += 1
for i in range(N):
    tmp = copy(dS)
    for key in tmp:
        dS[key+S[i]] += tmp[key]

for i in range(M):
    tmp = copy(dT)
    for key in tmp:
        dT[key+T[i]] += tmp[key]
    
ans = 0
for key in dS:
    ans += dS[key]*dT[key]%mod

print(ans%mod)


### FIXED CODE ###

mod = 10**9 + 7
N, M = map(int, input().split())
S = [None] + list(map(int, input().split()))
T = [None] + list(map(int, input().split()))
dp = [[0 for _ in range(M+1)] for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, M+1):
        if S[i] == T[j]:
            dp[i][j] = (dp[i][j-1] + dp[i-1][j] + 1)%mod
        else:
            dp[i][j] = (dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1])%mod
print((dp[N][M]+1)%mod)
### BUGGY CODE ###

n, m = map(int, input().split())
lrd = []

MAX = 999999

p = [[] for _ in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    lrd.append([l-1, r-1, d, 0])
    p[l-1].append(i)
    p[r-1].append(i)

if m <= 1:
    print('Yes')
    exit()

a = [MAX for _ in range(n)]

a[lrd[0][0]] = 0
temp = [lrd[0][0]]
next = []
t = 0
s = 0
max_a = 0
min_a = 0
while 1:
    next = []
    #print("temp", temp)
    for x in temp:
        for y in p[x]:
            if lrd[y][0] == x:
                t = lrd[y][1]
                s = a[x] + lrd[y][2]
            else:
                t = lrd[y][0]
                s = a[x] - lrd[y][2]

            lrd[y][3] = 1
            if a[t] == MAX:
                a[t] = s
                next.append(t)
            elif a[t] != s:
                #print(temp, t, a[t])
                print('No')
                exit()

    #print(next)
    if len(next) == 0:
        target = 0
        i = 0
        check = 0
        for i in range(m):
            if lrd[i][3] == 0:
                target = lrd[i][0]
                check = 1
        if check == 0:
            break
        a[target] = 0
        next = [target]

    #print(next)
    temp = [] + list(set(next))

print('Yes')


### FIXED CODE ###

n, m = map(int, input().split())
lrd = []

MAX = 999999

p = [[] for _ in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    lrd.append([l-1, r-1, d, 0])
    p[l-1].append(i)
    p[r-1].append(i)

if m <= 1:
    print('Yes')
    exit()

a = [MAX for _ in range(n)]


target = lrd[0][0]
a[target] = 0
temp = [target]
t = 0
while 1:
    next = []
    for x in temp:
        for y in p[x]:
            if lrd[y][3] == 1:
                continue

            if lrd[y][0] == x:
                t = lrd[y][1]
                d = a[x] + lrd[y][2]
            else:
                t = lrd[y][0]
                d = a[x] - lrd[y][2]

            lrd[y][3] = 1

            if a[t] == MAX:
                a[t] = d
                next.append(t)
            elif a[t] != d:
                print('No')
                exit()

    if len(next) == 0:
        check = 0
        for i in range(m):
            if lrd[i][3] == 0:
                check = 1
                target = lrd[i][0]
                break

        if check == 1:
            temp = [target]
            a[target] = 0
            continue
        else:
            break

    temp = [] + list(set(next))

print('Yes')
### BUGGY CODE ###

n = int(input())
p = list(map(int,input().split()))
flag = 0
ans = 0
for i in range(n):
  for j in range(i):
    if p[j] >= p[i]:
      pass
    else:
      flag = 1
  if flag == 0:
    ans += 1
  else:
    flag = 0
print(ans)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
if n == 1:
    print(1)
else:
    mn = p[0]
    ans = 1
    for i in range(1,n):
        if p[i] < mn:
            mn = p[i]
            ans += 1
    print(ans)