Harryxun/stf_run huggingface dataset:
# -*- coding: utf-8 -*-
from itertools import starmap

n, m = map(int, input().split())
l = sorted(list(map(int, input().split())))
divcount = n - 1

if n == 1:
    print(max(l) - min(l))
else:
    divl = sorted(list(starmap(lambda a,b: a - b, zip(l[1:], l[:m - 2])), reverse = True)
    for i in range(divcount):
        del divl[0]
    
    print (sum(divl))


### FIXED CODE ###

# -*- coding: utf-8 -*-
 
n, m = map(int, input().split())
l = sorted(list(map(int, input().split())))
divcount = n - 1
 
l1 = l[1:]
l2 = l[:m - 1]
divl = []
 
for i in range(m - 1):
    divl.append(l1[i] - l2[i])
 
divl.sort(reverse = True)
 
if n == 1:
    print(max(l) - min(l))
else:
    if m > n:
        for i in range(divcount):
            del divl[0]
    
        print (sum(divl))
    
    else:
        print(0)
n = int(input())
print(n**2)

### FIXED CODE ###

x,y = list(map(int,input().split()))
if x < 10 and y < 10:
	print(x*y)
else:
  print('-1')
import sys
import os
sys.stdin = open('input.txt', 'r')

from fractions import gcd
N = int(input())
A = [int(s) for s in input().split()]
ans = 0
L = [0] * (N)
R = [0] * (N)
for n in range(0, N):
    if n != N-1:
        L[n+1] = gcd(A[n], L[n])
        R[-(n+2)] = gcd(A[-(n+1)], R[-(n+1)])
for n in range(0, N):
    temp = gcd(L[n], R[n])
    ans = max(temp, ans)
print(ans)


### FIXED CODE ###

from fractions import gcd
N = int(input())
A = [int(s) for s in input().split()]
ans = 0
L = [0] * (N)
R = [0] * (N)
for n in range(0, N):
    if n != N-1:
        L[n+1] = gcd(A[n], L[n])
        R[-(n+2)] = gcd(A[-(n+1)], R[-(n+1)])
for n in range(0, N):
    temp = gcd(L[n], R[n])
    ans = max(temp, ans)
print(ans)
h, w = map(int, input().split())
if h == 1 or w == 1:
  print(1)
else:
  if a*w%2 != 0:
    print(a*w//2 + 1)
  else:
    print(a*w//2)

### FIXED CODE ###

import sys
h, w = map(int, input().split())
if h == 1 or w == 1:
  print(1)
  sys.exit()
ans = h//2*w
if h%2 != 0:
  if w%2 != 0:
    ans += w//2+1
  else:
    ans += w/2
print(int(ans))
import sys
import string
input = sys.stdin.readline

C = input()
if C == 'z': print('a')
else: print(string.ascii_lowercase[string.ascii_lowercase.index(C)+1])

### FIXED CODE ###

alpha = 'abcdefghijklmnopqrstuvwxyz'
C = input()
print(alpha[alpha.index(C)+1])
a=input().split()
b=list(map(int,a))
if a < b:
 print(a<b)
elif a > b:
 print(a>b)
else:
 print(a == b)

### FIXED CODE ###

x=input().split()
y=list(map(int,x))
a=y[0]
b=y[1]
if a < b:
 print('a < b')
elif a > b:
 print('a > b')
else:
 print('a == b')
N, L = (int(nl) for nl in input().split())
tastes = [L+i-1 for i in range(1, N+1)]
min_taste = 0
min_taste_abs = 100
for taste in tastes:
    if min_taste_abs > abs(taste):
        min_taste_abs = abs(taste)
        min_taste = taste
min_taste_index = tastes.index(min_taste)
print(sum(tastes[:min_taste_index]+tastes[min_taste_index+1:]))

### FIXED CODE ###

N, L = (int(nl) for nl in input().split())
tastes = [L+i-1 for i in range(1, N+1)]
min_taste = 100
min_taste_abs = 100
for taste in tastes:
    if min_taste_abs >= abs(taste):
        min_taste_abs = abs(taste)
        min_taste = taste

min_taste_index = tastes.index(min_taste)
if len(tastes) == min_taste_index+1:
    print(sum(tastes[:min_taste_index]))
else:
    print(sum(tastes[:min_taste_index]+tastes[min_taste_index+1:]))
H,N=map(int,input().split())
A=list(map(int,input().split()))
if H<=sum(A):
    print(Yes)
else:
    print(No)


### FIXED CODE ###

H,N=map(int,input().split())
A=list(map(int,input().split()))
if H<=sum(A):
    print("Yes")
else:
    print("No")
n, a, b, c, d = map(int, input().split())

s = input()

flagA = True
flagB = True

for i in range(d - b):
    if s[b + i] == "#" and s[b + i + 1] == "#":
        flagB = False

for i in range(c - a):
    if ((s[a + i] == "#") or (a + i == d - 1)) and ((s[a + i + 1] == "#") or (a + i + 1 == d - 1)):
        flagA = False
        for j in range(c - a):
            if (s[a + j] == "." and s[a + j + 1] == "." and s[a + j + 2] == "."):
                flagA = True

if flagA and flagB:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

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

s = input()

if c < d:
    for i in range(b, d):
        if s[i:i+2] == "##":
            print(('No'))
            exit()
    for i in range(a, c):
        if s[i:i+2] == "##":
            print(('No'))
            exit()
    print('Yes')
else:
    for i in range(b, d):
        if s[i:i+2] == "##":
            print(('No'))
            exit()
    for i in range(a, c):
        if s[i:i+2] == "##":
            print(('No'))
            exit()
    for i in range(b-2, d-1):
        if s[i:i+3] == "...":
            print(('Yes'))
            exit()
    print('No')
#主人の大好きな数字
fav = 753
listA = list(input())
N = len(listA)
#ダックスフンドの選ぶ数字
s = 0

for i in range(0,N-2):
  a,b,c = map(str,listA[i:i+3])
  x = a+b+c
  if abs(fav-s) > abs(fav-int(x)):
    s = int(a+b+c)
print(abs(fav-s)

### FIXED CODE ###

#主人の大好きな数字
fav = 753
listA = list(input())
N = len(listA)
#ダックスフンドの選ぶ数字
s = 0

for i in range(0,N-2):
  a,b,c = map(str,listA[i:i+3])
  x = a+b+c
  if abs(fav-s) > abs(fav-int(x)):
    s = int(a+b+c)
print(abs(fav-s))
from scipy.sparse.csgraph import dijkstra

INF = 10 ** 18
N, M = map(int, input().split())
d = [[INF for _ in range(N)] for _ in range(N)]
abc = []

for i in range(M):
    a, b, c = map(int, input().split())
    abc.append([a - 1, b - 1, c])
    d[a - 1][b - 1] = c
    d[b - 1][a - 1] = c

dtra = dijkstra(d)
minlst = [INF] * N
for i in range(N):
    for j in range(N):
        if dtra[i][j] != 0:
            minlst[i] = min(minlst[i], dtra[i][j])

cnt = 0
for i in range(M):
    if int(minlst[abc[i][1]]) < abc[i][2]:
        cnt += 1

print(cnt)

### FIXED CODE ###

from scipy.sparse.csgraph import floyd_warshall

INF = 10 ** 18
N, M = map(int, input().split())
d = [[INF for _ in range(N)] for _ in range(N)]
abc = []

for i in range(M):
    a, b, c = map(int, input().split())
    abc.append([a - 1, b - 1, c])
    d[a - 1][b - 1] = c
    d[b - 1][a - 1] = c

wf = floyd_warshall(d)
cnt = 0
for i in range(M):
    if abc[i][2] > wf[abc[i][0]][abc[i][1]]:
        cnt += 1


print(cnt)
N = int(input())
s = 0
for i in range(1,n+1):
    if N / sum(int(input())) == 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

def f(n):
  return sum(map(int, str(n)))

X = int(input())

if X % f(X) == 0: 
  print("Yes")
else:
  print("No")
import math
a,b = map(int, input().split())
ans = 1
count = 2
num = math.gcd(a,b)

if a==1 or b==1:
    print(1)
else:
    while True:
        if num==1:
            print(ans)
            exit(0)
        else:
            if num%count==0:
                ans+=1
                while num%count==0:
                    num= num/count
                count+=1
            else:
                count+=1


### FIXED CODE ###

from fractions import gcd
a,b = map(int, input().split())
# ans = 1
count = 2
n=gcd(a,b)

ans = set([1])
while n % 2 == 0:
    ans.add(2)
    n //= 2
f = 3
while f * f <= n:
    if n % f == 0:
        ans.add(f)
        n //= f
    else:
        f += 2
if n != 1:
    ans.add(n)
print(len(ans))
import numpy as np


def count_multi(s, d):
  m = a = np.array([c for c in s]).astype(np.int)
  keta = 1
  count = np.count_nonzero(m == 0)
  while len(m) > 1:
    m = (m[:-1]*10 + a[keta:]) % d
    keta += 1
    count += np.count_nonzero(m == 0)
  return count
        
print(count_multi(input().strip(), 2019))


### FIXED CODE ###

s, w = [int(x) for x in input().strip().split()]
print("safe" if s > w else "unsafe")
N, A, B = map(int, input().split())

res = 0

for n in range(N+1):
  if A <= sum([int(s) for s in str(n)]) <= B:
  res += n
  
print(res)


### FIXED CODE ###

N, A, B = map(int, input().split())
res = 0
for i in range(N+1):
    if A <= sum([int(s) for s in str(i)]) <= B:
        res += i
print(res)
S = str(input())
s_list=[]
string= ""
AGCT = ["A", "G", "C", "T"]
for s in S:
    if s in AGCT:
        string += s
    else:
        s_list.append(string)
        string=""
max(map(len, s_list))

### FIXED CODE ###

S = input()
s_list=[]
string= ""
AGCT = ["A", "G", "C", "T"]
for s in S:
    if s in AGCT:
        #string = string + s
        string += s
    else:
        s_list.append(string)
        string=""
s_list.append(string)
print(max(map(len, s_list)))
import sys
from collections import defaultdict
sys.setrecursionlimit(100000)

N, M = map(int, input().split())
AB = defaultdict(list)
gain = [0]*N
for i in range(N + M - 1):
    a, b = map(int, input().split())
    AB[a - 1].append(b - 1)
    gain[b - 1] += 1

ans = [None]*N
def rec(u, p):
    ans[u] = p
    for v in AB[u]:
        gain[v] -= 1
    for v in AB[u]:
        if gain[v] == 0 and ans[v] is None:
            rec(v, u)

root = gain.index(0)
rec(root, -1)

for i in range(N):
    print(ans[i] + 1)


### FIXED CODE ###

import sys
from collections import defaultdict
sys.setrecursionlimit(100000)

N, M = map(int, input().split())
AB = []
D = defaultdict(lambda: [])
for i in range(N + M - 1):
    a, b = map(int, input().split())
    AB.append((a - 1, b - 1))
    D[a - 1].append(b - 1)

z = [0]*N
for a, b in AB:
    z[b] += 1

ans = [-1]*N
root = z.index(0)
ok = [False]*N
def rec(u, p):
    ans[u] = p
    ok[u] = True
    for v in D[u]:
        z[v] -= 1
    for v in D[u]:
        if z[v] == 0 and not ok[v]:
            rec(v, u)


rec(root, -1)

for i in range(N):
    print(ans[i] + 1)
M=[]
for i in range(1001):
   m=(i+1)/2
   M.append(m) 

N,K=map(int,input().split())
P=list(map(int,input().split()))
S=[]
s=0
for i in range(N):
    a=P[i]
    s=s+M[a]
    S.append(s)
Q=[]
q=0
for i in range(N-K+1):
    if i ==0:
        q=S[K-1]
    else:
        q=S[i+K]-S[i] 
    Q.append(q)
    q=0
print(max(Q))


### FIXED CODE ###

M=[]
for i in range(1001):
   m=(i+1)/2
   M.append(m) 

N,K=map(int,input().split())
P=list(map(int,input().split()))
S=[]
s=0
for i in range(N):
    a=P[i]
    s=s+M[a]
    S.append(s)
Q=[]
Q.append(S[K-1])
q=0
for i in range(N-K):
    q=S[i+K]-S[i] 
    Q.append(q)
    q=0
print(max(Q))
S = input()
K = int(input())
L = len(S)
a = S[0]
modi = 0
i = 0
C = []
while i < L-1:
    count = 1
    b,c = S[i],S[i+1]
    i+= 1
    while b == c:
        count += 1
        if i == L-1:
            C.append(count)
            break
        b,c = S[i],S[i+1]
        i += 1
    if i == L-1:
        break
    C.append(count)
if a != S[L-1]:
    num = 0
    for co in C:
        num += co//2
    print(int(num*K))
else:
    num1 = 0
    for co in C:
        num1 += co//2
    num2 = (C[len(C)-1]+1)//2
    for co in C[:len(C)-1]:
        num2 += co//2
        print(co,co//2)
    print(int(num1+num2*(K-1)))

### FIXED CODE ###

S = input()
K = int(input())
L = len(S)
a = S[0]
i = 0
C = []
if L == 1:
    C = [1]
while i < L-1:
    count = 1
    b,c = S[i],S[i+1]
    i+= 1
    while b == c:
        count += 1
        if i == L-1:
            break
        b,c = S[i],S[i+1]
        i += 1
    C.append(count)
if a != S[L-1]:
    num = 0
    for co in C:
        num += co//2
    ans = int(num*K)
else:
    if len(C) == 1:
        ans  = L*K//2
    else:
        num1 = 0
        for co in C:
            num1 += co//2
        num2 = (C[len(C)-1]+C[0])//2
        for co in C[1:len(C)-1]:
            num2 += co//2
        ans = int(num1+num2*(K-1))
print(ans)
XMAX = 10**5
X = int(input())
dp = [False] * XMAX
dp[0] = True

for i in range(0, X + 1):
    for p in range(100, 106):
        if i - p >= 0 and dp[i - p]:
            dp[i] = True
            next
if dp[X]:
    print(1)
else:
    print(0)

### FIXED CODE ###

X = int(input())
for i in range(1, X + 1):
    if X >= 100 * i and X <= 105 * i:
        print(1)
        exit()
print(0)
S = input().split()
T = input().split()
txt = S + T
print(txt)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
S,T = read().decode('utf-8').split()
 
answer = T + S
print(answer)
a,b=map(int,input().split())
while a<=1 or 100<=a:
    while b<=1 or 100<=b:
        a,b=int(input());

S=a*b;
L=a+a+b+b;

print(S,L);



### FIXED CODE ###

a,b=map(int,input().split());
print(a*b,2*a+2*b);
N = input()
 
if N.isupper() == true:
  print("A")
else:
  print("a")

### FIXED CODE ###

if input().isupper():
  print('A')
else:
  print('a')
def ceil(x,y):
    return x//y+(not( not x%y))
n=int(input())
a,b=1,1
for i in range(n):
    t,s = map(int,input().split())
    i = max( ceil(a/t), ceil(b/s) )
    a=t*i;b=s*i
print(a+b)

### FIXED CODE ###

def ceil(x,y):
  return (x-1)//y+1
N = int(input())
TA = [list(map(int, input().split())) for _ in range(N)]
t, a = 1, 1
for T, A in TA:
  rate = max(ceil(t, T), ceil(a, A))
  t = T * rate
  a = A * rate
print(t + a)
def main(): #startline-------------------------------------------
    k = int(input())
    ans = 0
    for i in range(1,k+1):
        for j in range(1,k+1):
            for l in range(1,k+1):
                ans += gcd(gcd(i,j),l)

    print(ans)
if __name__ == "__main__":
    main() #endline===============================================

### FIXED CODE ###

from math import gcd
def main(): #startline-------------------------------------------
    k = int(input())
    ans = 0
    for i in range(1,k+1):
        for j in range(1,k+1):
            for l in range(1,k+1):
                ans += gcd(gcd(i,j),l)

    print(ans)
if __name__ == "__main__":
    main() #endline===============================================
import copy

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

frends = {}

for i in range(m):
  a,b = map(int, input().split())
  if a not in frends:
    frends[a] = set()
  if b not in frends:
    frends[b] = set()
  frends[a].add(b)
  frends[b].add(a)

group = copy.copy(frends) 
  
for i in frends:
  flag = False
  r = group[i]
  for j in r:
    if j > i:
      flag = True
      break
  if flag == True:
    group[max(r)].update(group.pop(i))
    
cnt = 0
for i in group:
  c = len(group[i])
  if c > cnt:
    if i not in group[i]:
      c += 1
    cnt = c

print(cnt)

### FIXED CODE ###

def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

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

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if par[x] > par[y]:
        x, y = y, x
    par[x] += par[y]
    par[y] = x


N, M = map(int, input().split())
par = [-1 for i in range(N)]

for i in range(M):
    a, b = map(int, input().split())
    unite(a - 1, b - 1)

print(-min(par))
D = int(input())
if(D == 25):
  print("Christmas")
else if(D == 24):
  print("Christmas Eve")
else if(D == 23):
  print("Christmas Eve Eve")
else if(D == 22):
  print("Christmas Eve Eve Eve")

### FIXED CODE ###

D = int(input())
if(D == 25):
  print("Christmas")
elif(D == 24):
  print("Christmas Eve")
elif(D == 23):
  print("Christmas Eve Eve")
elif(D == 22):
  print("Christmas Eve Eve Eve")
import sys
INF = 1 << 60
MOD = 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

def _fmt(A, inverse = False):
    N = len(A)
    logN = (N - 1).bit_length()
    base = pow(3, (MOD - 1) // N * (1 - 2 * inverse) % (MOD - 1), MOD)
    step = N
    for k in range(logN):
        step >>= 1
        w = pow(base, step, MOD)
        wj = 1
        nA = [0] * N
        for j in range(1 << k):
            for i in range(1 << logN - k - 1):
                s, t = i + j * step, i + j * step + (N >> 1)
                ps, pt = i + j * step * 2, i + j * step * 2 + step
                nA[s], nA[t] = (A[ps] + A[pt] * wj) % MOD, (A[ps] - A[pt] * wj) % MOD
            wj = (wj * w) % MOD
        A = nA
    return A

def convolution(f, g):
    N = 1 << (len(f) + len(g) - 2).bit_length()
    Ff, Fg = _fmt(f + [0] * (N - len(f))), _fmt(g + [0] * (N - len(g)))
    N_inv = pow(N, MOD - 2, MOD)
    fg = _fmt([a * b % MOD * N_inv % MOD for a, b in zip(Ff, Fg)], inverse = True)
    del fg[len(f) + len(g) - 1:]
    return fg

def resolve():
    n, s = map(int, input().split())
    F = [None] * n
    for i, a in enumerate(map(int, input().split())):
        tmp = [0] * a
        tmp[0] = 2
        tmp.append(1)
        F[i] = tmp
    logN = (n - 1).bit_length()
    N = 1 << logN
    F += [[1] for _ in range(N - len(F))]

    for i in range(logN):
        nF = [None] * (1 << logN - i - 1)
        for i in range(1 << logN - i - 1):
            nF[i] = convolution(F[2 * i], F[2 * i + 1])[:s + 1]
        F = nF
    print(F[0][s])
resolve()

### FIXED CODE ###

import sys
INF = 1 << 60
MOD = 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, s = map(int, input().split())
    dp = [0] * (s + 1)
    dp[0] = 1
    res = 0
    A = list(map(int, input().split()))
    for a in A:
        ndp = [2 * t % MOD for t in dp]
        if s >= a:
            for i in range(s - a, -1, -1):
                ndp[i + a] += dp[i]
                ndp[i + a] %= MOD
        dp = ndp


    print(dp[s] % MOD)
resolve()
def thin(H: int, W: int, C: list)->list:
    return [[C[h//2][w] for w in range(W)] for h in range(2*H)]


if __name__ == "__main__":
    H = 0
    H, W = map(int, input().split())
    C = [input() for _ in range(H)]
    ans = thin(H, W, C)
    print('\n'.join(ans))


### FIXED CODE ###

def thin(H: int, W: int, C: list)->list:
    return [C[h//2] for h in range(2*H)]


if __name__ == "__main__":
    H = 0
    H, W = map(int, input().split())
    C = [input() for _ in range(H)]
    ans = thin(H, W, C)
    print('\n'.join(ans))
N,K = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]
dpx = 10**4+1
for i in range(1,K):
  for j in range(0,i):
      dpx = min(dpx, abs(h[i]-h[j])+dp[j])
  dp.append(dpx)
print(dp[-1])

### FIXED CODE ###

def main():
    N,K = map(int,input().split())
    h = list(map(int,input().split()))
    dp = [0]*N
    for i in range(1,N):
        dp[i]= min(abs(h[i]-h[j])+dp[j] for j in range(max(0,i-K),i))
    print(dp[-1])
main()
r = input()
r = int(r)
pi = 3.14159265358979
print("{0:6f} {1:6f}".format(r * r * pi, 2 * r * pi))

### FIXED CODE ###

r = input()
r = float(r)
pi = 3.14159265358979
print("{0:10f} {1:10f}".format((r ** 2 * pi), (2 * r * pi)))
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n)] # 親の番号
        self.size = [1]*n
    
    def root(self, x: int) -> int:
        """根を求める"""
        if self.par[x] == x: # if root
            return x
        else:
            self.par[x] = self.root(self.par[x]) # 経路圧縮
            return self.par[x]
    
    def is_same(self, x:int, y:int)->bool:
        """x と y が同じ集合に属するか否か"""
        return self.root(x)==self.root(y)
    
    def unite(self, x:int, y:int):
        """x と y の属する集合を併合"""
        x = self.root(x)
        y = self.root(y)
        if x == y: return
        self.par[x] = y
        self.size[y] += self.size[x]
        # self.size[x] = 0
        
    def get_size(self, x:int)->int:
        return self.size[self.root(x)]
        
N,M = map(int, input().split())
ab = list(tuple(map(lambda x:int(x)-1, input().split())) for _ in range(M))

def comb2(n):
    if n==0: return 0
    return n*(n-1)//2

uf = UnionFind(N)
ans = []
nex = comb2(N)
for ai,bi in reversed(ab):
    ans.append(nex)
    if uf.is_same(ai,bi):
        nex = nex
    else:
        nex = nex - uf.get_size(ai)*uf.get_size(bi)
    uf.unite(ai,bi)
for a in reversed(ans):
    print(a)

### FIXED CODE ###

#UnionFindクラス
class UnionFind:
    def __init__(self,n):
        self.par =  [i for i in range(n)]
        self.rank = [1 for _ in range(n)]

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

    # xとyの根を結合させる
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y: return
        if self.rank[x] < self.rank[y]:
            x, y = y, x
        self.rank[x] += self.rank[y]
        self.par[y] = x

    # x,yの根が同じかどうかを返す（根が同じ:True、根が異なる:False）
    def is_same(self, x, y):
        return self.find(x) == self.find(y)

    # xが含まれる木の要素数を返す
    def size(self, x):
        return self.rank[self.find(x)]
    
n,m = map(int,input().split())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(m)]
uf = UnionFind(n)
accm = []
for ai,bi in reversed(ab):
    if uf.is_same(ai,bi):
        accm.append(0)
    else:
        accm.append(uf.size(ai)*uf.size(bi))
    uf.union(ai,bi)

accm = accm[::-1]
for i in range(1,len(accm)):
    accm[i] += accm[i-1]
for a in accm:
    print(a)
from bisect import bisect_left

n = input()
ls = list(map(int, input().split()))
count = 0
for i in range(0, n - 2):
  for j in range(i + 1, n - 1):
    two_sides_sum = ls[i]+ ls[j]
    for k in range(j + 1, n):
      if two_sides_sum <= ls[k]:
        count += k - j - 1
        break
print(count)

### FIXED CODE ###

import bisect
n = int(input())

li = list(map(int, input().split()))
li.sort()

count = 0

for i in range(n - 2):
  for j in range(i + 1, n - 1):
    bi = bisect.bisect_left(li, li[i] + li[j])
    count += bi - j - 1
print(count)
S = [c for c in int()]
print(2 * S.count('+') -4)

### FIXED CODE ###

S = [c for c in input()]
print(2 * S.count('+') -4)
import math
A,B=map(int, input().split())
n=math.gcd(A, B)
divisors = []
for i in range(1, int(n**0.5)+1):
    flag=0
    if n % i == 0:
      for j in range(2, int(i**0.5)+1):
        if i%j==0:
          flag=1
          break
    if flag==0:
      divisors.append(i)
      #if i != n // i :
      #  divisors.append(n//i)
flag=0
for j in range(1, int(n**0.5)+1):
    if n%j==0:
      flag=1
      break
if flag==0:
      divisors.append(n)
print(len(divisors))     

### FIXED CODE ###

import fractions
import math
A,B=map(int, input().split())
n=fractions.gcd(A, B)
divisors = []
for i in range(1, int(n**0.5)+1):
    flag=-1
    lag=-1
    if n % i == 0:
      flag=0
      for j in range(2, int(i**0.5)+1):
        if i%j==0 and i!=j:
          flag=1
          break
      if i != n // i :
        lag=0
        for j in range(2, int((n // i)**0.5)+1):
          if (n // i)%j==0 and i!=j:
            lag=1
            break
    if flag==0:
      divisors.append(i)
    if lag==0:
      divisors.append(n//i)
#flag=0
#print(divisors)
#for j in range(2, int(n**0.5)+1):
#    if n%j==0:
#     flag=1
 #     break
#if flag==0:
 #     divisors.append(n)
print(len(divisors))
a=int(raw_input())
b=int(raw_input())

if a>b:
    print "GREATER"
elif a<b:
    print "LESS"
else:
    print "EQUAL"

### FIXED CODE ###

s1,s2,s3 = raw_input().split(' ')

print (s1[0]+s2[0]+s3[0]).upper()
class Edge():
	def __init__(self, v, w):
		self._v = v
		self._w = w
	def v(self):
		return self._v
	def w(self):
		return self._w

def dfs(v, g, colors, color = 0):
	colors[v] = color
	if not len(g[v]):
		return
	for nv in g[v]:
		if colors[nv.v()] != -1:
			continue
		nc = color if nv.w() % 2 == 0 else 1 - color
		dfs(nv.v(), g, colors, nc)

def resolve():
	n = int(input())
	colors = [-1]*n
	g = [list() for _ in range(n)]
	for _ in range(n-1):
		u, v, w = map(int, input().split())
		g[v-1].append(Edge(u-1, w))
		g[u-1].append(Edge(v-1, w))
	dfs(0, g, colors)
	for c in colors:
		print(c)
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(100**4)

class Edge():
	def __init__(self, v, w):
		self._v = v
		self._w = w
	def v(self):
		return self._v
	def w(self):
		return self._w

def dfs(v, g, colors, color = 0):
	colors[v] = color
	if not len(g[v]):
		return
	for nv in g[v]:
		if colors[nv.v()] != -1:
			continue
		nc = color if nv.w() % 2 == 0 else 1 - color
		dfs(nv.v(), g, colors, nc)

def resolve():
	n = int(input())
	colors = [-1]*n
	g = [list() for _ in range(n)]
	for _ in range(n-1):
		u, v, w = map(int, input().split())
		g[v-1].append(Edge(u-1, w))
		g[u-1].append(Edge(v-1, w))
	for i in range(n):
		if colors[i] != -1:
			continue
		dfs(i, g, colors)
	for c in colors:
		print(c)
resolve()