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

l = list(map(int, input().split()))
n = l[0]
t = l[1]

l = list(map(int, input().split()))
maxdiff = 0
count = 0
startindex = 0
endindex = 0

i = 0
while i < n:
    # 最大値を見つける
    maxnum = 0
    maxindex = 0
    for j in range(i, n):
        if l[j] > maxnum:
            maxnum = l[j]
            maxindex = j
    #print("max: " + str(maxnum))
    #print("index: " + str(maxindex))
    if maxindex == i:
        i += 1
        continue
    # 最大の差を見つける
    for j in range(i, maxindex):
        if maxnum - l[j] > maxdiff:
            maxdiff = maxnum - l[j]
            count = 1
            #print("maxdiff: " + str(maxdiff))
            #print("count: " + str(count))
        elif maxnum - l[j] == maxdiff:
            count += 1
            #print("maxdiff: " + str(maxdiff))
            #print("count: " + str(count))
    i = maxindex + 1
print(count)


### FIXED CODE ###

l = list(map(int, input().split()))
n = l[0]
t = l[1]

l = list(map(int, input().split()))
maxdiff = 0
count = 0
currentmin = 10000000000

for i in l:
    if i - currentmin > maxdiff:
        maxdiff = i - currentmin
        count = 1
    elif i - currentmin == maxdiff:
        count += 1
    elif i < currentmin:
        currentmin = i
print(count)
### BUGGY CODE ###

def main():
    INF = 2**60
    N, M = map(int, input().split())
    XYZ = [list(map(int, input().split())) for _ in range(N)]

    sgn = [[1,1,1], [1,1,-1],[1,-1,1],[1,-1,-1],[-1,1,1],[-1,1,-1],[-1,-1,1],[-1,-1,-1]]
    ans = -INF 
    for a, b, c in sgn:
        dp = [-INF]*(M+1)
        dp[0] = 0
        for x, y, z in XYZ:
            for j in range(M-1, -1, -1):
                if dp[j] == -INF: continue
                s = dp[j]+ a*x + b*y + c*z
                if s > dp[j+1]:
                    dp[j+1] = s
        if dp[M] > ans:
            ans = dp[M]
    print(ans)

main()


### FIXED CODE ###

import sys

def main():
    INF = -2**60
    N, M = map(int, sys.stdin.buffer.readline().split())
    XYZ = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]

    sgn = [[1,1,1], [1,1,-1],[1,-1,1],[1,-1,-1],[-1,1,1],[-1,1,-1],[-1,-1,1],[-1,-1,-1]]
    ans = INF 
    for a, b, c in sgn:
        dp = [INF]*(M+1)
        dp[0] = 0
        for x, y, z in XYZ:
            for j in range(M-1, -1, -1):
                if dp[j] == INF: continue
                s = dp[j]+ a*x + b*y + c*z
                if s > dp[j+1]:
                    dp[j+1] = s
        if dp[M] > ans:
            ans = dp[M]
    print(ans)

main()
### BUGGY CODE ###

n, a = map(int, input().split())
x = list(map(int, input().split()))
M = max(x)
M = max(M, a)
dp = [[[0]*(n*M+1) for _ in range(n+1)] for _ in range(n+1)]

for j in range(n+1):
    for k in range(n+1):
        for s in range(n*M+1):
            if j == 0 and k == 0 and s == 0:
                dp[j][k][s] = 1
            elif j >= 1 and s < x[j-1]:
                dp[j][k][s] = dp[j-1][k][s]
            elif j >= 1 and k >= 1 and s>= x[j-1]:
                dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]
            else:
                dp[j][k][s] = 0
ans = 0
for k in range(1, n+1):
    ans += dp[n][k][k*a]
print(ans)


### FIXED CODE ###

n, a = map(int, input().split())
x = list(map(int, input().split()))
M = max(x)
M = max(M, a)
dp = [[[0]*(n*M+1) for _ in range(n+1)] for _ in range(n+1)]
dp[0][0][0] = 1
for j in range(n):
    for k in range(n+1):
        for s in range(n*M+1):
            if dp[j][k][s]:
                dp[j+1][k][s] += dp[j][k][s]
                dp[j+1][k+1][s + x[j]] += dp[j][k][s]

ans = 0
for k in range(1, n+1):
    ans += dp[n][k][k*a]
print(ans)
### BUGGY CODE ###

S = input()
T = input()
def swap(x, p, q):
  x_neo = ""
  for i in x:
    if i == p:
      x_neo += q
    elif i == q:
      x_neo += p
    else:
      x_neo += i
  return x_neo
for i in range(len(S)):
  if S[i] != T[i]:
    S = swap(S, S[i], T[i])
#    print(S)
if S == T:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

S = input()
T = input()
def f(x):
  d = {chr(97+i):[] for i in range(26)}
  for i in range(len(x)):
    d[x[i]].append(i)
  D = list(d.values())
  D.sort()
  return D
if f(S) == f(T):
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
B.sort()
C.sort()

def f(l, mn):
    ng = -1
    ok = len(l)
    while abs(ng - ok) > 1:
        i = (ok + ng) // 2
        x = l[i]
        if mn < x:
            ok = i
        else:
            ng = i
    return l[ok:]

ans = 0
for a in A:
    for b in f(B, a):
        ans += len(f(C, b))
print(ans)

### FIXED CODE ###

from bisect import bisect_left, bisect_right
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
C.sort()

ans = 0
for b in B:
    acnt = bisect_left(A, b)
    ccnt = N - bisect_right(C, b)
    ans += acnt * ccnt
print(ans)
### BUGGY CODE ###

def MKNUMBER(S,l,r):
    slice = S[l-1:r]
    A=list(slice)
    number=[]
    for i in A:
        if i == "A":
            number.append(1)
        elif i == "C":
            number.append(2)
        else:
            number.append(0)
    return(number)
  
def countAC(number):
    count = 0
    flg = 0
    for i in number:
        if i == 0:
            flg = 0
        if i == 1:
            flg = 1
        if i == 2:
            if flg == 1:
                count = count + 1
            flg = 0
    print(count) 
    
N,Q = input().split()
N = int(N)
Q = int(Q)
S = input()

for i in range(0,Q):
    l,r = input().split()
    l = int(l)
    r = int(r)
    number = MKNUMBER(S,l,r)
    countAC(number)

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
X = []
x = 0
check = 0
for i in S:
    if check == 1 and i == 'C':
        x += 1
        check = 0
    if i == 'A':
        check = 1
    else:
        check = 0
    X.append(x)
#print(X)
A = []
for _ in range(Q):
    l,r = map(int,input().split())
    ans = X[r-1] - X[l-1]
    A.append(ans)
for i in A:
    print(i)
### BUGGY CODE ###

A, B, C, D = map(int,input().split())

d=[[0 for j in range(D+1)] for i in range(C+1)]
d[A][B]=1
for i in range(A+1,C+1):
  d[i][B] = B*d[i-1][B] % 998244353
for j in range(B+1,D+1):
  d[A][j] = A*d[A][j-1] % 998244353
 
for i in range(A+1,C+1):
  for j in range(B+1,D+1):
    d[i][j]=(((j*d[i-1][j]) % 998244353 + i*d[i][j-1] % 998244353) % 998244353 - ((i-1)*((j-1)*d[i-1][j-1]) % 998244353) % 998244353) % 998244353
    
print(d[C][D] % 998244353)

### FIXED CODE ###

import sys
import numpy as np
#from functools import lru_cache
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
MOD = 998_244_353
 
def main(A, B, C, D):
	d = np.zeros((C + 1, D + 1), np.int64)
	d[A,B]=1
	for i in range(A+1,C+1):
  		d[i,B] = B*d[i-1,B] % MOD
	for j in range(B+1,D+1):
		d[A,j] = A*d[A,j-1] % MOD
 
	for i in range(A+1,C+1):
		for j in range(B+1,D+1):
			d[i,j]=((((j*d[i-1,j]) % MOD + i*d[i,j-1] % MOD) % MOD) -((i-1)*((j-1)*d[i-1,j-1] % MOD)% MOD)% MOD)
    
	return d[C,D] % MOD
          
"""    
    print(d[C][D] % MOD)
    dp = np.zeros((C + 1, D + 1), np.int64)
    dp[C, D] = 1
    for d in range(D, 0, -1):
        dp[C, d - 1] = dp[C, d] * C % MOD
    for c in range(C - 1, -1, -1):
        x = 0
        for d in range(D, -1, -1):
            dp[c, d] = (d * dp[c + 1, d] + x) % MOD
            x += dp[c + 1, d]
            x *= c
            x %= MOD
    return dp[A, B]
"""

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i8 = numba.from_dtype(np.int64)
    signature = (i8, i8, i8, i8)
 
    cc = CC('my_module')
    cc.export('main', signature)(main)
    cc.compile()
 
from my_module import main
 
A, B, C, D = map(int, read().split())
print(main(A, B, C, D))
### BUGGY CODE ###

import numpy as np

N = int(input())
As = list(map(int, input().split()))
 
sum_humidai = 0
 
for person_idx, person_height in enumerate(As):
  
  if person_idx == 0:
    continue
    
  max_front_person = max(As[:person_idx])
  max_person_idx = np.asarray(As[:person_idx]).argmax()
  
  if max_front_person > person_height:
    humidai = max_front_person - person_height
    As[person_idx] += humidai
    sum_humidai += humidai

print(sum_humidai)

### FIXED CODE ###

N = int(input())
As = list(map(int, input().split()))
 
sum_humidai = 0
max_front_person = 0
  
for person_idx, person_height in enumerate(As):
  
  if person_idx == 0:
    continue
    
  max_front_person = max(max_front_person, As[person_idx - 1])
  if max_front_person > person_height:
    humidai = max_front_person - person_height
    sum_humidai += humidai
 
print(sum_humidai)
### BUGGY CODE ###

S = str(input())
S_len = len(S)

DP = [[0] * 13 for i in range(S_len+1)]
DP[S_len][0] = 1

for i in reversed(range(S_len)):

    num = 10 ** (S_len - 1 - i) % 13

    if S[i] != "?":
        for j in range(13):
            if DP[i + 1][j] != 0:
                DP[i][(j + int(S[i]) * num) % 13] = (DP[i][(j + int(S[i]) * num) % 13] + DP[i + 1][j]) % 1000000007
    else:
        for j in range(13):
            for k in range(10):
                if DP[i + 1][j] != 0:
                    DP[i][(j + k * num) % 13] = (DP[i][
                                                     (j + k * num) % 13] +
                                                 DP[i + 1][j]) % 1000000007

print(DP[0][5])



### FIXED CODE ###

s=input()
l=len(s)
mod=10**9+7
dp=[[0 for j in range(13)] for i in range(l+1)]
dp[0][0]=1
for i in range(1,l+1):
  if s[i-1]=='?':
    for j in range(10):
      for k in range(13):
        dp[i][(k*10+j)%13]+=dp[i-1][k]%mod
  else:
    for k in range(13):
      dp[i][(k*10+int(s[i-1]))%13]+=dp[i-1][k]%mod
print(dp[-1][5]%mod)
### BUGGY CODE ###

from itertools import combinations

def build_tree(N, root_list, edges):
    for p, q in [edges]:
        p -= 1
        q -= 1
        root_p = get_root(root_list, p)
        root_q = get_root(root_list, q)
        root_now = min(root_p, root_q, p)
        root_list[p] = root_now
        root_list[q] = root_now
        root_list[root_p] = root_now
        root_list[root_q] = root_now
    return root_list

def get_root(root_list, city):
    if root_list[city] == city:
        return city
    else: 
        root_list[city] = get_root(root_list, root_list[city])
        return root_list[city]

def combi(root_list):
    return sum([a*b for a, b in combinations(root_list, 2)])
    
if __name__ == '__main__':
    N, M = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(M)]
    
    AB = AB[::-1]
    
    root_list = [i for i in range(N)]
    root_num = [1]*N
    inconvinience = []
    inconvinience.append(combi(root_num))
    
    for edges in AB:
        root_list = build_tree(N, root_list,edges)
        root_list = [get_root(root_list, i) for i in range(N)]
        root_num = [0]*N
        for i in range(N):
            root_num[get_root(root_list, i)] += 1
        inconvinience.append(combi(root_num))
    
    inconvinience.pop()
    
    for i in inconvinience[::-1]:
        print(i)

### FIXED CODE ###

from itertools import combinations

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
            self.size[x] = self.size[y]
        else:
            if x != y:
                self.size[x] += self.size[y]
                self.size[y] = self.size[x] 
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

def combi(root_list):
    return sum([a*b for a, b in combinations(root_list, 2)])
    
if __name__ == '__main__':
    N, M = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(M)]
    
    AB = AB[::-1]
    
    
    inconvinience = []
    inconvinience.append(N*(N-1)//2)
    
    tree = UnionFind(N)
    for a, b in AB:
        delta = 0
        if not tree.same_check(a, b):
            delta = tree.size[tree.find(a)]*tree.size[tree.find(b)]
        tree.union(a, b)
        inconvinience.append(inconvinience[-1] - delta)
    
    inconvinience.pop()
    
    for i in inconvinience[::-1]:
        print(i)
### BUGGY CODE ###

import numpy as np

nc, nt, nq = map(int, input().split())
t = [list(map(int, input().split())) for _ in range(nt)]
q = [list(map(int, input().split())) for _ in range(nq)]
dp = np.zeros((nc + 1, nc + 1), dtype="i8")
for l, r in t:
    dp[:l + 1, r:] += 1
for l, r in q:
    print(dp[l][r])


### FIXED CODE ###

def f(nc, nt, nq):
    t = [list(map(int, input().split())) for _ in range(nt)]
    q = [list(map(int, input().split())) for _ in range(nq)]
    dp = [[0] * (nc + 1) for _ in range(nc + 1)]
    for l, r in t:
        dp[l][r] += 1
    for i in range(1, nc + 1):
        dpi = dp[i]
        s = dpi[0]
        for j in range(1, nc + 1):
            dpi[j] = s = dpi[j] + s
    for j in range(1, nc + 1):
        s = dp[0][j]
        for i in range(1, nc + 1):
            dp[i][j] = s = dp[i][j] + s
    for l, r in q:
        print(dp[r][r] - dp[l - 1][r] - dp[r][l - 1] + dp[l - 1][l - 1])


nc, nt, nq = map(int, input().split())
f(nc, nt, nq)
### BUGGY CODE ###

S = input()
start_posi = [int(i) for i in range(len(S))]
cnt = 0

posi = start_posi
pre_posi = {}
next_posi = start_posi
while not posi in  pre_posi.values():
    pre_posi[cnt] = next_posi
    next_posi = []
    for i in posi:
        next_posi.append(i + 1 if S[i] == 'R' else i - 1)        
    posi = next_posi
    cnt += 1
    
for key, v in pre_posi.items():
    if posi == v:
        loop_width = cnt-key
        loop_point = key
        break
loop = (10**100 - loop_point)%loop_width

answer_dict = {i : 0 for i in range(len(S))}
for mass in pre_posi[loop+loop_point]:
    answer_dict[mass] += 1
print(' '.join(map(str,answer_dict.values())))

### FIXED CODE ###

def double_dp(dp,num):
    dp_new = [0]*num
    for i in range(num):
        dp_new[i] = dp[dp[i]]
    return dp_new

S = input()
dp = [int(i) for i in range(len(S))]

for i in range(len(S)):
    dp[i] = dp[i] + 1 if S[dp[i]] == 'R' else dp[i] - 1

for _ in range(17):
    dp = double_dp(dp, len(S))
        
answer_dict = {i : 0 for i in range(len(S))}
for mass in dp:
    answer_dict[mass] += 1
print(' '.join(map(str,answer_dict.values())))
### BUGGY CODE ###

from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque

def check(max_length, left, right, r, index):
    if index == 100:
        print(left)
    half = (left + right) / 2
    if 2 * half <= max_length * (r - half) / r:
        check(max_length, half, right, r, index + 1)
    else:
        check(max_length, left, half, r, index + 1)

def main():
    data = [list(map(int, input().split())) for i in range(3)]
    a = ((data[0][0] - data[1][0]) ** 2 + (data[0][1] - data[1][1]) ** 2) ** 0.5
    b = ((data[1][0] - data[2][0]) ** 2 + (data[1][1] - data[2][1]) ** 2) ** 0.5
    c = ((data[0][0] - data[2][0]) ** 2 + (data[0][1] - data[2][1]) ** 2) ** 0.5

    s = (a + b + c) / 2
    S = (s * (s - a) * (s - b) * (s - c)) ** 0.5
    r = 2 * S / (a + b + c)

    left, right = 0, max(a, b, c)

    check(max(a, b, c), left, right, r, 0)





if __name__ == '__main__':
    main()
    # test()



### FIXED CODE ###

from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque

def check(max_length, left, right, r, index):
    if index == 1000:
        print(left)
        sys.exit()
    half = (left + right) / 2
    if 2 * half <= max_length * (r - half) / r:
        check(max_length, half, right, r, index + 1)
    else:
        check(max_length, left, half, r, index + 1)

def main():
    data = [list(map(int, input().split())) for i in range(3)]
    a = ((data[0][0] - data[1][0]) ** 2 + (data[0][1] - data[1][1]) ** 2) ** 0.5
    b = ((data[1][0] - data[2][0]) ** 2 + (data[1][1] - data[2][1]) ** 2) ** 0.5
    c = ((data[0][0] - data[2][0]) ** 2 + (data[0][1] - data[2][1]) ** 2) ** 0.5

    s = (a + b + c) / 2
    S = (s * (s - a) * (s - b) * (s - c)) ** 0.5
    r = 2 * S / (a + b + c)

    left, right = 0, max(a, b, c)

    check(max(a, b, c), left, right, r, 0)





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

def kqpurge(num):
    k=0
    while num%2==0:
        num=num/2
        k+=1
    return k,int(num)

def miller_l(num):
    k,q=kqpurge(num-1)
    tnum=0
    if num==1:return False
    if num in [2,3,5,7]:return True
    for i in [2,3,5,7]:
        for e in range(k+1):
            if e==0:
                if i**q%num==1:
                    tnum+=1
                    break
                elif i**q%num==num-1:
                    tnum+=1
                    break
            else:
                temp=i**((2**e)*q)
                if temp%num==(num-1):
                    tnum=tnum+1
                    break
                elif temp%num==1:
                    break
    if tnum==4:
        return True
    else:
        return False
        
while True:
    try:n=int(input())
    except:break
    count=0
    for i in range(2,n+1):
        if miller_l(i):
            count+=1
    print(count)

### FIXED CODE ###


import math

m=999999
s=int(math.sqrt(m)+1)
li=[0]*m
li[0]=1
for i in range(1,s):
    if li[i]==0:
        li[i*2+1::i+1]=[1 for e in range(len(li[i*2+1::i+1]))]
while True:
    try:n=int(input())
    except:break
    print(len([i for i in li[:n:] if i==0]))
### BUGGY CODE ###

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

adic=dict()

for ai in a:
    if ai in adic:
        adic[ai]+=1
    else:
        adic[ai]=1
        
q=int(input())
b=[0]*(q)
c=[0]*(q)
bc=[[0]*2 for i in range(q)]
for i in range(q):
#    b[i],c[i]=map(int,input().split())
    bc[i]=map(int,input().split())
    
#print(adic)    
#for bi,ci in zip(b,c):
for bi,ci in bc:
    if bi in adic and ci in adic:
        adic[ci]=adic[ci]+adic[bi]
        del adic[bi]
    elif bi in adic and (not ci in adic):
        adic[ci]=adic[bi]
        del adic[bi]
#    print(i,adic)
    asum=0
    for i,ad in adic.items():
        asum+=i*ad
    print(asum)
    

### FIXED CODE ###

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

adic=dict()

for ai in a:
    if ai in adic:
        adic[ai]+=1
    else:
        adic[ai]=1
        
q=int(input())
b=[0]*(q)
c=[0]*(q)
bc=[[0]*2 for i in range(q)]
for i in range(q):
    bc[i]=map(int,input().split())
    
asum=0
for i,ad in adic.items():
    asum+=i*ad
    
#print(adic)    
for bi,ci in bc:
    if bi in adic and ci in adic:
        asum-=bi*adic[bi]
        adic[ci]=adic[ci]+adic[bi]
        asum+=ci*adic[bi]
        del adic[bi]
    elif bi in adic and (not ci in adic):
        asum-=bi*adic[bi]
        adic[ci]=adic[bi]
        asum+=ci*adic[bi]
        del adic[bi]
#    print(i,adic)
    print(asum)
### BUGGY CODE ###

n=int(input())
a=[]
for i in range(n):
  ainput=int(input())
  a.append(ainput)

anext=a[:]
for i in range(n):
  anext.remove(anext[i])
  b=max(anext)
  print(b)
  anext.insert(i,a[i])

### FIXED CODE ###

n=int(input())
a=[int(input()) for i in range(n)]

l1=sorted(a)[-1]
l2=sorted(a)[-2]

for i in a:
  if i==l1:
    print(l2)
  if i!=l1:
    print(l1)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
ans = []
for i in range(1,n+1):
    ans.append(1+a.index(i))
print(' '.join(map(str, ans)))

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
b = [0 for i in range(n)]
for i in range(n):
    b[a[i]-1] = i+1
print(*b)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
def main():
    n=int(input())

    #グラフの連結成分を調べる
    def Graph():
        G=[[] for i in range(n)]
        #up_G=[0]*n#up_G[i]=頂点iの親
        for i in range(n-1):
            a,b,c=map(int,input().split())
            G[a-1].append((b,c))
            G[b-1].append((a,c))
        return G

    #木上のDFSテンプレ
    from collections import deque
    def dfs(G,v,p):
        q=deque([])
        q.append([v,p])
        dis=0
        dis_l=[-1]*n
        dis_l[0]=0
        while q:
            V,P=q[-1]
            for new_v in G[V-1]:
                v0,v1=new_v
                #new_vが頂点の時はアウト
                if v0==P:continue
                if dis_l[v0-1]>=0:continue
                dis=dis_l[V-1]+v1
                dis_l[v0-1]=dis
                q.append([v0,V])
                break
            else:
                q.pop()
        return dis_l


    log=Graph()
    ans=dfs(log,1,-1)

    for i in ans:
        if i%2==0:
            print(0)
        else:
            print(1)
            
if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())

#グラフの連結成分を調べる
def Graph():
    G=[[] for i in range(n)]
    #up_G=[0]*n#up_G[i]=頂点iの親
    for i in range(n-1):
        a,b,c=map(int,input().split())
        c=0 if c%2==0 else 1
        G[a-1].append((b,c))
        G[b-1].append((a,c))
    return G

#木上のDFSテンプレ
from collections import deque
def dfs(G,v,p):
    q=deque()
    q.append((v,p))
    dis=0
    dis_l=[-1]*n
    dis_l[0]=0
    while q:
        V,P=q.pop()
        for new_v in G[V-1]:
            v0,v1=new_v
            #new_vが頂点の時はアウト
            if v0==P:continue
            if dis_l[v0-1]>=0:continue
            dis=(dis_l[V-1]+v1)%2
            dis_l[v0-1]=dis
            q.append((v0,V))

    return dis_l


log=Graph()
ans=dfs(log,1,-1)
print(*ans,sep='\n')
### BUGGY CODE ###

from numba import njit
N = int(input())
L = list(map(int, input().split()))
L.sort()

@njit
def solve(N, L):
    cnt = 0
    for i in range(N-2):
        a = L[i]
        for j in range(i+1, N-1):
            b = L[j]
            for k in range(j+1, N):
                cnt += a+b > L[k]
    return cnt
print(solve(N, L))

### FIXED CODE ###

from numba import njit
N = int(input())
L = list(map(int, input().split()))
L.sort()

@njit
def solve(L):
    cnt = 0
    for i in range(N-2):
        a = L[i]
        for j in range(i+1, N-1):
            b = L[j]
            for k in range(j+1, N):
                cnt += a+b > L[k]
    return cnt
print(solve(L))
### BUGGY CODE ###

x = {}
n, m = map(int, raw_input().split())
flag = True
for _ in xrange(m):
    l, r, d = map(int, raw_input().split())
    if l in x:
        if r in x:
            if x[l][1] + d != x[r][1]:
                if x[l][0] == x[r][0]:
                    flag = False
                else:
                    for k, v in x.iteritems():
                        if v[0] == r:
                            x[k] = (x[l][0], v[1] + x[l][1] + d)
        else:
            x[r] = (x[l][0], x[l][1] + d)
    else:
        x[l], x[r] = (l, 0), (l, d)
print 'Yes' if flag else 'No'


### FIXED CODE ###

from collections import deque
n, m = map(int, raw_input().split())
graph = {_: set() for _ in xrange(n + 1)}
in_deg, dist = [0] * (n + 1), [-1] * (n + 1)
for _ in xrange(m):
    l, r, d = map(int, raw_input().split())
    graph[l].add((r, d))
    in_deg[r] += 1
que = deque([i for i in xrange(n + 1) if not in_deg[i]])
cst = 1
while que:
    stp = que.popleft()  # start_point
    if in_deg[stp] < 0:
        in_deg[stp] = cst
    for v, d in graph[stp]:
        if dist[v] < 0:
            dist[v] = dist[stp] + d
        else:
            if dist[v] != dist[stp] + d:
                print 'No'
                exit()
        in_deg[v] -= 1
        if not in_deg[v]:
            que.append(v)
print 'No' if [_ for _ in in_deg[1:] if _ > 0] else 'Yes'