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

N = int(input())
A = [int(i) for i in input().split()]
B = [0]+A[:]+[0]
C = A[:]+[0]+[0]
D = [abs(i-j) for i, j in zip(B, C)]

for i in range(N):
    if B[i] < B[i+1] and B[i+1] <B[i+2]:
        print(sum(D))
    else:
        t = abs(B[i+1]-B[i])+abs(B[i+2]-B[i+1])-abs(B[i+2]-B[i])
        print(sum(D)-t)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
B = [0]+A[:]+[0]
s = 0
for i in range(N+1):
    s += abs(B[i]-B[i+1])

for i in range(N):
    if B[i] < B[i+1] and B[i+1] <B[i+2]:
        print(s)
    else:
        t = abs(B[i+1]-B[i])+abs(B[i+2]-B[i+1])-abs(B[i+2]-B[i])
        print(s-t)
### BUGGY CODE ###

from fractions import gcd
k = int(input())
result = 0

# 3つとも等しい数字
for i in range(1, k+1):
    for j in range(i, k+1):
        for m in range(j, k+1):
            if i==j==m:
                result += i
            elif i==j or j==m:
                result += gcd(i, m)*3
            else:
                result += gcd(i, gcd(j,m))*6
print(result)

### FIXED CODE ###

from math import gcd
k = int(input())
result = 0

# 3つとも等しい数字
for i in range(1, k+1):
    for j in range(i, k+1):
        for m in range(j, k+1):
            if i==j==m:
                result += i
            elif i==j or j==m:
                result += gcd(i, m)*3
            else:
                result += gcd(i, gcd(j,m))*6
print(result)
### BUGGY CODE ###

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

step = [0]
for i in A[1:]:
    if A[A.index(i)-1] >= i:
        step.append(A[A.index(i)-1] - i)
        A[A.index(i)] += A[A.index(i)-1] - i
print(sum(step))


### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
step = [0]
for k,i in enumerate(A[1:]):
    if A[k] >= i:
        step.append(A[k] - i)
        A[k+1] = A[k+1] + A[k] - i
print(sum(step))
### BUGGY CODE ###

n, t = map(int, input().split())
a, b, ab = [], [], []
for _ in range(n):
    ab.append(tuple(map(int, input().split())))
ab.sort(key=lambda x:x[0])
for i in ab:
    a.append(i[0])
    b.append(i[1])

# dp[i][j] = 0~i番目の料理でj分以内に完食できる美味しさの合計の最大値
# 0 <= i <= n-1, 0 <= j <= t-1
dp = [[0 for _ in range(a[0])] + [b[0] for _ in range(t-a[0])]]
for i in range(1, n):
    dp.append([])
    for j in range(min([t, a[i]])):
        dp[i].append(dp[i-1][j])
    for j in range(a[i], t):
        dp[i].append(max([dp[i-1][j], dp[i-1][j-a[i]]+b[i]]))

ans = []
for i in range(1, n):
    ans.append(dp[i-1][t-1] + b[i])
print(max(ans))

### FIXED CODE ###

n, t = map(int, input().split())
a, b, ab = [], [], []
for _ in range(n):
    ab.append(tuple(map(int, input().split())))
ab.sort(key=lambda x:x[0])
for i in ab:
    a.append(i[0])
    b.append(i[1])

# dp[i][j] = 0~i番目の料理でj分以内に完食できる美味しさの合計の最大値
# 0 <= i <= n-1, 0 <= j <= t-1
dp = [[0 for _ in range(min([t, a[0]]))] + [b[0] for _ in range(t-a[0])]]
for i in range(1, n):
    dp.append([])
    for j in range(min([t, a[i]])):
        dp[i].append(dp[i-1][j])
    for j in range(a[i], t):
        dp[i].append(max([dp[i-1][j], dp[i-1][j-a[i]]+b[i]]))

ans = []
for i in range(1, n):
    ans.append(dp[i-1][t-1] + b[i])
print(max(ans))
### BUGGY CODE ###

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

for i in range(M):
    A_list[A_list.index(max(A_list))] //= 2

print(sum(A_list))

### FIXED CODE ###

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

import heapq, math
A_list = [-x for x in A_list]
heapq.heapify(A_list)

for _ in range(M):
    A_min = heapq.heappop(A_list)
    heapq.heappush(A_list, math.ceil(A_min/2))

print(-sum(A_list))
### BUGGY CODE ###

S = input()
count = 0
for i in range(len(S) - 3):
    for j in range(i+5, len(S)+1):
        if int(S[i:j]) % 2019 == 0:
            count += 1
            break
print(count)

### FIXED CODE ###

S = input()
mod = 2019

cs_mods = {0:1}
cumsum = 0
count = 0
for i, s in enumerate(S[::-1]):
    cumsum = (cumsum + int(s) * pow(10, i, mod)) % mod
    cs_mods.setdefault(cumsum, 0)
    # count += cs_mods[cumsum]
    cs_mods[cumsum] += 1

# count = 0
for k, v in cs_mods.items():
    count += v*(v-1)//2

print(count)
### BUGGY CODE ###

import sys
import heapq

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
Q = []
for i in range(N):
    heapq.heappush(Q, (-B[i], i))
cnt = 0

while len(Q) != 0:
    _, i = heapq.heappop(Q)

    if (B[i] - A[i]) % (B[(i-1) % N] + B[(i+1) % N]) == 0:
        cnt += (B[i] - A[i]) // (B[(i-1) % N] + B[(i+1) % N])
        B[i] = A[i]
    else:
        tmp = (B[i] - 1) // (B[(i-1) % N] + B[(i+1) % N])
        B[i] -= tmp * (B[(i-1) % N] + B[(i+1) % N])
        cnt += tmp
        heapq.heappush(Q, (-B[i], i))
    
    if A == B:
        print(cnt)
        sys.exit()

print(-1)

### FIXED CODE ###

import sys
import heapq

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
Q = []
for i in range(N):
    heapq.heappush(Q, (-B[i], i))
ans = 0
cnt = 0

while len(Q) != 0:
    _, i = heapq.heappop(Q)

    if (B[i] - A[i]) % (B[(i-1) % N] + B[(i+1) % N]) == 0:
        ans += (B[i] - A[i]) // (B[(i-1) % N] + B[(i+1) % N])
        cnt += 1
        B[i] = A[i]
    else:
        tmp = (B[i] - 1) // (B[(i-1) % N] + B[(i+1) % N])
        
        if tmp == 0:
            print(-1)
            sys.exit()
        
        B[i] -= tmp * (B[(i-1) % N] + B[(i+1) % N])
        ans += tmp
        heapq.heappush(Q, (-B[i], i))
    
    if cnt == N:
        print(ans)
        sys.exit()

print(-1)
### BUGGY CODE ###

import collections
a=int(input())
b=list(map(int,input().split()))

c=collections.Counter(b)
n,m=zip(*c.most_common())
n,m=list(n),list(m)
result=0
for i in range(len(m)):
    result+=(m[i]*(m[i]-1))//2
for i in range(a):
    print(result-(m[n.index(b[i])]-1))




### FIXED CODE ###

import collections
a=int(input())
b=list(map(int,input().split()))

c=collections.Counter(b)

n,m=zip(*c.most_common())
n,m=list(n),list(m)
result=0
for i in range(len(m)):
    result+=(m[i]*(m[i]-1))//2

for i in b:
    print(result-c[i]+1)
### BUGGY CODE ###

k,s=map(int,input().split())
br=0
for x in range(k+1):
    for y in range(k+1):
        z=s-x-y
        if x+y+z==s and z>=0 and z<=k:
            br+=1
        
print(br)

### FIXED CODE ###

k,s=map(int,input().split())
br=0
k+=1
for x in range(k):
    for y in range(k):
        z=s-x-y
        if x+y+z==s and z>=0 and z<k:
            br+=1
        
print(br)
### BUGGY CODE ###

from sys import stdin
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

def main():
     n,m,k = [int(x) for x in stdin.readline().split()]
     a = cmb(n*m-2,k-2)*n*m*(m*(n**2-1)+n*(m**2-1))
     a = a//6
     a = a%(10**9+7)
     print(a)
     return

if __name__=="__main__":
     main()

### FIXED CODE ###

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

n,m,k = map(int,input().split())
nm = n*m%(10**9+7)
k = k%(10**9+7)
a = (cmb(nm-2,k-2,mod)%(10**9+7))*(nm*(m*(n**2-1)+n*(m**2-1)))//6
print(a%(10**9+7))
### BUGGY CODE ###

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

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

for i in range(m):
  a[n-1] = int(a[n-1]//2)
  a.sort()

res = 0
for i in a:
  res += i
  
print(res)

### FIXED CODE ###

import heapq

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

a = list(map(int,input().split()))
b = list(map(lambda x:-x,a))

heapq.heapify(b)

for i in range(m):
  tmp = heapq.heappop(b)
  heapq.heappush(b,int(tmp/2))

res = 0

for i in range(n):
  
  res += heapq.heappop(b)
  
print(-res)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
  n = int(input())
  prev = -1
  nums = []
  table = {}

  for _ in range(n):
    v = int(input())

    if v != prev:
      nums.append(v)
      prev = v

  for i, n in enumerate(nums):
    if n not in table:
      table[n] = []

    table[n].append(i)

  values = [0] * len(nums)
  value = 1

  for i in range(len(nums)):
    values[i] += value

    for j in table[nums[i]]:
      if i == j:
        continue

      values[j] = (values[j] + value) % int(1e+9 + 7)

    value = values[i] % int(1e+9 + 7)

  print(value, flush=True)


if __name__ == '__main__':
  main()



### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
  value = 1
  skips = {}
  prev = -1

  for _ in range(int(input())):
    n = int(input())

    if n == prev:
      continue

    prev = n

    if n in skips:
      value += skips[n]

    skips[n] = value

  print(value % int(1e+9 + 7), flush=True)


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

N = int(input())
c = input()
cnt = 0
while 'WR' in c:
    cnt += 1
    w = c.find('W')
    r = c.rfind('R')
    c = list(c)
    c[w] = 'R'
    c[r] = 'W'
    c = ''.join(c)
print(cnt)

### FIXED CODE ###

n = int(input())
c = input()
a = 0
b = 0
for i in range(n):
    if c[i] == 'R':
        a+=1
ans = max(a, b)
for i in range(n):
    if c[i] == 'R':
        a-=1
    else:
        b+=1
    now = max(a, b)
    ans = min(ans, now)
print(ans)
### BUGGY CODE ###

h,w,a,b=[int(i) for i in input().split()]
p=10**9+7
kkk={}
def kai(n):
  if n in kkk:
    return kkk[n]
  a=1
  for i in range(1,n+1):
    a*=i
    a%=p
  kkk[n]=a
  return a
def conv(k,n):
  a=kai(n)*pow(kai(k),p-2,p)*pow(kai(n-k),p-2,p)
  return a%p
ans=0
for i in range(b+1,w+1):
  ans+=conv(i-1,i+h-a-2)*conv(w-i,a+w-i-1)
  ans%=p
print(ans)


### FIXED CODE ###

h, w, a, b = [int(i) for i in input().split()]

mod = 10 ** 9 + 7
kkai = [1]
for i in range(1, 210000):
    kkai.append(kkai[-1] * i % mod)


def kai(x, p=mod):
    return kkai[x]


def comb(a, b, p=mod):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    c = 1
    c *= kai(a, p)
    c *= pow(kai(b, p), p - 2, p)
    c *= pow(kai(a - b, p), p - 2, p)
    return c % p


ans = 0
for i in range(b, w):
    ans += comb(i+(h-a)-1, i)*comb((w-i)+a-2, a-1)
    ans %= mod
print(ans)
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
A = [list(input()) for i in range(H)]

INF = float('inf')
dx = [1, 0, -1, 0]
dy = [0, 1, 0 , -1]

def bfs(i, j):
    D = [[INF] * W for i in range(H)]
    que = deque()
    que.append([i, j])
    D[i][j] = 0
    
    while que != []:
        p = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < H and 0 <= ny < W and A[nx][ny] != '#' and D[nx][ny] == INF:
                que.append([nx, ny])
                D[nx][ny] = D[p[0]][p[1]] + 1
            elif 0 <= nx < H and 0 <= ny < W and A[nx][ny] == '#':
                D[nx][ny] = D[p[0]][p[1]] + 1
                return D[nx][ny]

ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == '.':
            tmp = bfs(i, j)
            ans = max(ans, tmp)
            
print(ans)

### FIXED CODE ###

from collections import deque
 
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]
 
que = deque()
INF = float('inf')
dx = [1, 0, -1, 0]
dy = [0, 1, 0 , -1]            
D = [[INF] * W for i in range(H)]

for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            que.append([i, j])
            D[i][j] = 0
                       
def bfs():
    while len(que) != 0:
        p = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < H and 0 <= ny < W and A[nx][ny] != '#' and D[nx][ny] == INF:
                que.append([nx, ny])
                D[nx][ny] = D[p[0]][p[1]] + 1
    
bfs()

ans = 0
for i in range(H):
    for j in range(W):
        tmp = D[i][j]
        ans = max(ans, tmp)
        
print(ans)
### BUGGY CODE ###

S = input()
Ls = [1, 10, 9, 12, 3, 4]  # 10^n % 13, n % 6でループ

L = len(S) - 1
mem = [[0 for _ in range(13)] for _ in range(len(S))]
if S[L] == '?':
    for m in range(10):
        mem[0][m] = 1
else:
    mem[0][int(S[L])] = 1

for i in range(1, len(S)):
    t = S[L - i]
    for m in range(13):
        if t == '?':
            s = 0
            for j in range(10):
                tm = m - ((Ls[i % 6] * j) % 13)
                if tm < 0:
                    tm += 13
                s += mem[i - 1][tm]
            mem[i][m] = s
        else:
            tm = m - ((Ls[i % 6] * int(t)) % 13)
            if tm < 0:
                tm += 13
            mem[i][m] = mem[i - 1][tm]
print(mem[len(S) - 1][5] % (10 ** 9 + 7))

### FIXED CODE ###

S = input()
Ls = [1, 10, 9, 12, 3, 4]  # 10^n % 13, n % 6でループ
C = 10 ** 9 + 7

L = len(S) - 1
mem = [[0 for _ in range(13)] for _ in range(len(S))]
if S[L] == '?':
    for m in range(10):
        mem[0][m] = 1
else:
    mem[0][int(S[L])] = 1

for i in range(1, len(S)):
    t = S[L - i]
    for m in range(13):
        if t == '?':
            s = 0
            for j in range(10):
                tm = m - ((Ls[i % 6] * j) % 13)
                if tm < 0:
                    tm += 13
                s += mem[i - 1][tm]
            mem[i][m] = s % C
        else:
            tm = m - ((Ls[i % 6] * int(t)) % 13)
            if tm < 0:
                tm += 13
            mem[i][m] = mem[i - 1][tm] % C
print(mem[len(S) - 1][5])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import collections

def main():
    N, M = list(map(int, input().split()))

    arr = []
    for x in range(M):
        L, R = list(map(int, input().split()))

        for y in range(L, R+1):
            arr.append(y)

    arrcnt = collections.Counter(arr).values()
    print(sum(i == M for i in arrcnt))


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
import collections

def main():
    N, M = list(map(int, input().split()))

    L = [0] * M
    R = [0] * M
    for i in range(M):
        L[i], R[i] = list(map(int, input().split()))

    ans = (int(min(R)) - int(max(L)) + 1)
    if ans < 0:
        print('0')
    else:
        print(ans)

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

n,m,q=map(int,input().split())
alist=[]
for i in range(m):
    l,r=map(int,input().split())
    alist.append([l,r])
alist.sort()
for j in range(q):
    count=0
    p,q=map(int,input().split())
    for j in alist:
        if p<=j[0] and q>=j[1]:
            count+=1
    print(count)

### FIXED CODE ###

n, m, Q = map(int, input().split())
lr = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for _ in range(m):
    l, r = map(int, input().split())
    lr[l][r] += 1

rui = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, n + 1):
        rui[i][j] = lr[i][j] + rui[i - 1][j] + rui[i][j - 1] - rui[i - 1][j - 1]
    
for _ in range(Q):
    p, q = map(int, input().split())
    p -= 1
    ans = rui[q][q] - rui[p][q] - rui[q][p] + rui[p][p]
    print(ans)
### BUGGY CODE ###

from itertools import combinations_with_replacement

N, M, Q = map(int,input().split())
x = [_ for _ in range(1, M+1)]
y = list(combinations_with_replacement(x, N))
l = [list(map(int, input().split())) for _ in range(Q)]

ans = 0
z = 0
for i in range(len(y)):
    for j in range(Q):
        if y[i][l[j][1]-1] - y[i][l[j][0]-1] == l[j][2]:
            z += l[j][3]
        ans = max(ans, z)
    z = 0
print(ans)

### FIXED CODE ###

from itertools import combinations_with_replacement

N, M, Q = map(int,input().split())
x = [_ for _ in range(1, M+1)]
y = list(combinations_with_replacement(x, N))
l = [list(map(int, input().split())) for _ in range(Q)]

ans = []
z = 0
for i in range(len(y)):
    for j in range(Q):
        if y[i][l[j][1]-1] - y[i][l[j][0]-1] == l[j][2]:
            z += l[j][3]
        ans.append(z)
    z = 0
print(max(ans))
### BUGGY CODE ###

n = int(input())
L = list(map(int, input().split()))
L.sort()

count = 0
for i in range(0, n-2):
  for j in range(i+1, n-1):
    t = L[i] + L[j]
    for k in range(n-1, j, -1):
      if L[k] < t:
        count += k - j
        break

print(count)


### FIXED CODE ###

import bisect
n = int(input())
L = list(map(int, input().split()))
L.sort()

count = 0
for i in range(0, n-2):
  for j in range(i+1, n-1):
    t = L[i] + L[j]
    idx = bisect.bisect_left(L, t)
    count += idx - (j+1)

print(count)
### BUGGY CODE ###

def chmin(a,b):
    if a > b:
        return b
    else:
        return a


N, K = map(int, input().split())
h = list(map(int, input().split()))
INF = float('inf')
dp = [INF] * N
dp[0] = 0


for i in range(N):
    for j in range(1,K+1):
        if i+j < N:
            dp[i+j] = chmin(dp[i+j], dp[i] + abs(h[i] - h[i+j]))

print(dp[N-1])

### FIXED CODE ###

def chmin(a,b):
    if a > b:
        return b
    else:
        return a


N, K = map(int, input().split())
h = list(map(int, input().split()))
INF = float('inf')
dp = [INF] * N
dp[0] = 0


for i in range(N):
    for j in range(1,K+1):
        if i+j < N:
            dp[i+j] = chmin(dp[i+j], dp[i] + abs(h[i] - h[i+j]))

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

N,M=map(int,input().split())
flag = False
v=[]
x=[]
y=[]
for i in range(M):
    a,b=map(int,input().split())
    if a==1:
        x.append(b)
    if b==N:
        y.append(a)
for i in x:
    for j in y:
        if i==j:
            flag=True
            break
    if flag:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

N,M=map(int,input().split())
x=[0]*(N+1)
y=[0]*(N+1)
for i in range(M):
    a,b=map(int,input().split())
    if a==1:
        x[b]=1
    if b==N:
        y[a]=1
for i in range(N+1):
    if x[i]==1 and y[i]==1:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
max_a = 0
for i in a:
  tmp = a.count(i - 1) +a.count(i) + a.count(i + 1)
  if tmp > max_a:
    max_a = tmp
  tmp = a.count(i) +a.count(i + 1) + a.count(i + 2)
  if tmp > max_a:
    max_a = tmp
print(max_a)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [0] * (pow(10,5) + 1)
for i in range(n):
  if a[i] == 0:
    b[0] += 1
    b[1] += 1
  elif a[i] == pow(10,5):
    b[pow(10,5) - 1] += 1
    b[pow(10,5)] += 1
  else:
    b[a[i]] += 1
    b[a[i] - 1] += 1
    b[a[i] + 1] += 1
print(max(b))
### BUGGY CODE ###

from functools import reduce
from fractions import gcd
N = int(input())
A = [int(i) for i in input().split()]
ans = 0
for i in range(N):
  L = A[:i]
  R = A[i+1:]
  ans = max(ans, reduce(gcd,L+R))
print(ans)

### FIXED CODE ###

import fractions
from functools import reduce
n = int(input())
a = list(map(int,input().split()))
left = [0] * (n + 1)
right = [0] * (n + 1)
for i in range(n):
    left[i + 1] = (fractions.gcd(left[i],a[i]))
    right[n - i - 1] = (fractions.gcd(right[n - i],a[n - 1 - i]))
ans = 0
for i in range(n):
    ans = max(ans,fractions.gcd(left[i],right[i + 1]))
print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())
is_order = True
for i in range(Q):
    tmp = input()
    if len(tmp) == 1:
        t = 1
        is_order = not is_order
    else:
        t,f,c = tmp.split()
        f = int(f)
        if f == 1:
            if is_order:
                S = c + S
            else:
                S = S + c[::-1]
        else:
            if is_order:
                S = S + c
            else:
                S = c[::-1] + S
if is_order:
    print(S)
else:
    print(S[::-1])

### FIXED CODE ###

from collections import deque

S = input()
d = deque(S)
Q = int(input())
is_order = True
for i in range(Q):
    tmp = input()
    if len(tmp) == 1:
        t = 1
        is_order = not is_order
    else:
        t,f,c = tmp.split()
        f = int(f)
        if f == 1:
            if is_order:
                d.appendleft(c)
            else:
                d.append(c[::-1]) 
        else:
            if is_order:
                d.append(c)
            else:
                d.appendleft(c[::-1])
if is_order:
    print("".join(d))
else:
    print("".join(reversed(d)))
### BUGGY CODE ###

from operator import itemgetter
import heapq
def prim_heap():
  used=[True]*n
  edgelist=[]
  for e in edge[0]:
    heapq.heappush(edgelist,e)
  used[0] = False
  res = 0
  while len(edgelist) != 0:
    minedge = heapq.heappop(edgelist)
    if not used[minedge[1]]:
      continue
    v = minedge[1]
    used[v] = False
    for e in edge[v]:
      if used[e[1]]:
        heapq.heappush(edgelist,e)
    res += minedge[0]
  return res

n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
edge=[[] for i in range(n)]
l.sort()
for i in range(n):
  l[i]=[l[i][0],l[i][1],i]
for i in range(n-1):
  edge[i].append([min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),i+1])
  edge[i+1].append([min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),i])
l=sorted(l,key=itemgetter(1))
for i in range(n-1):
  edge[l[i][2]].append([min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),l[i+1][2]])
  edge[l[i+1][2]].append([min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),l[i][2]])
print(prim_heap())

### FIXED CODE ###

from operator import itemgetter
import heapq
def prim_heap():
  used=[True]*n
  edgelist=[]
  for e in edge[0]:
    heapq.heappush(edgelist,e)
  used[0] = False
  res = 0
  while len(edgelist) != 0:
    minedge = heapq.heappop(edgelist)
    if not used[minedge[1]]:
      continue
    v = minedge[1]
    used[v] = False
    for e in edge[v]:
      if used[e[1]]:
        heapq.heappush(edgelist,e)
    res += minedge[0]
  return res

import sys
input=sys.stdin.readline
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
edge=[[] for i in range(n)]
l.sort()
for i in range(n):
  l[i]=[l[i][0],l[i][1],i]
for i in range(n-1):
  edge[i].append((min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),i+1))
  edge[i+1].append((min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),i))
l=sorted(l,key=itemgetter(1))
for i in range(n-1):
  edge[l[i][2]].append((min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),l[i+1][2]))
  edge[l[i+1][2]].append((min(abs(l[i][0]-l[i+1][0]),abs(l[i][1]-l[i+1][1])),l[i][2]))
print(prim_heap())
### BUGGY CODE ###


import copy

class dfs():
    
    def __init__(self, n, el):
        self.n = n
        self.el = el

        self.evenl = [1 for i in range(n)]
        self.g = [[0 for j in range(n)] for i in range(n)]
        self.pd = set([i for i in range(n)])

    def calc(self, nf, pd):
        pd.remove(nf)
        for i in pd:
            w = self.g[nf][i]
            if w > 0:
                if self.evenl[nf] == 1:
                    if w % 2 == 0:
                        self.evenl[i] = 1
                    else:
                        self.evenl[i] = 0
                else:
                    if w % 2 == 0:
                        self.evenl[i] = 0
                    else:
                        self.evenl[i] = 1

                self.g[nf][i] = 0
                self.g[i][nf] = 0

                self.calc(i, copy.deepcopy(pd) )

    def set_g(self):
        for e in self.el:
            u,v,w = e
            self.g[u-1][v-1] = w
            self.g[v-1][u-1] = w


n = int(input())
el = []
for i in range(n-1):
    u,v,w = map( int, input().split() )
    el.append( (u,v,w) )    

m = dfs(n,el)
m.set_g()
m.calc( 0, set([i for i in range(n)]) )

for item in m.evenl:
    print(item)

### FIXED CODE ###

from collections import deque

n = int(input())
neibors = [[] for i in range(n)]
for i in range(n-1):
    u,v,w = map( int, input().split() )
    neibors[u-1].append( (v-1,w%2) )
    neibors[v-1].append( (u-1,w%2) )

dist = [-1 for i in range(n)]
stack = deque([0])
while( len(stack) != 0 ):
    current = stack.popleft()
    current_dist = dist[current]

    for neibor_n, neibor_w in neibors[current]:
        if dist[neibor_n] == -1:
            stack.append( neibor_n )
            dist[neibor_n] = (neibor_w + current_dist) % 2  

for item in dist:
    print(item)