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

S = input()
mod = 10 ** 9 + 7
count = 0
for i in range(1,len(S)-1):
    if S[i] == "B" or S[i] == "?":
        left, right = list(S[:i]), list(S[i+1:])
        leftA, leftQ = left.count("A"), left.count("?")
        rightC, rightQ = right.count("C"), right.count("?")
        if leftQ >= 1:
            leftpatt = leftA * (3 ** leftQ) + leftQ * (3 ** (leftQ - 1))
        else:
            leftpatt = leftA
        if rightQ >= 1:
            rightpatt = rightC * (3 ** rightQ) + rightQ * (3 ** (rightQ - 1))
        else:
            rightpatt = rightC
        count += leftpatt * rightpatt
        count %= mod
print(int(count))

### FIXED CODE ###

S = input()
mod = 10 ** 9 + 7
count = 0
leftA = (1 if S[0] == "A" else 0)
leftQ = (1 if S[0] == "?" else 0)
rightC = S[1:].count("C")
rightQ = S[1:].count("?")

def mult(a, b, mod):
    if b == 0:
        return a
    else:
        return ((3*a + b) * pow(3, b-1, mod))

for i in range(1,len(S)-1):
    if S[i] == "B" or S[i] == "?":
        rightQ -= (1 if S[i] == "?" else 0)
        count += mult(leftA, leftQ, mod) * mult(rightC, rightQ, mod)
        count %= mod
        leftQ += (1 if S[i] == "?" else 0)
    elif S[i] == "A":
        leftA += 1 
    else:
        rightC -= 1
print(count)
### BUGGY CODE ###

N=int(input())
S=[]
for i in range(N):
    a=input()
    if a  not in S:
        S.append(a)
print(len(S))

### FIXED CODE ###

N=int(input())
S=[]
for i in range(N):
    a=input()
    S.append(a)
b=list(set(S))
print(len(b))
### BUGGY CODE ###

n,m= map(int,input().split())
A = list(map(int,input().split()))
B = []
for _ in range(m):
  b,c = map(int,input().split())
  B += [c]*b
C = A + B
C.sort()
C.reverse()
print(sum(C[0:n]))

### FIXED CODE ###

n,m= map(int,input().split())
AA = list(map(int,input().split()))
A = [(AA[i],1) for i in range(n)]
for _ in range(m):
  b,c = map(int,input().split())
  A += [(c,b)]
A.sort()
A.reverse()
rest = n
score = 0
for (cc,bb) in A:
  use = min(bb,rest)
  rest -= use
  score += use*cc
print(score)
### BUGGY CODE ###

x,y,z,k = map(int,input().split())
a = sorted(list(map(int,input().split())), reverse = True)
b = sorted(list(map(int,input().split())), reverse = True)
c = sorted(list(map(int,input().split())), reverse = True)

ab = []
for i in range(x):
    for j in range(y):
        ab.append(a[i] + b[j])
        if len(ab) == k:
            break
ab.sort(reverse = True)

abc = []
for i in range(min(len(ab),k)):
    for j in range(min(z,k)):
        abc.append(ab[i] + c[j])
abc.sort(reverse = True)

for i in range(k):
    print(abc[i])


### FIXED CODE ###

x,y,z,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

ab = []
for i in range(x):
    for j in range(y):
        ab.append(a[i] + b[j])
ab.sort(reverse = True)

abc = []
for i in range(min(k,len(ab))):
    for j in range(z):
        abc.append(ab[i] + c[j])

abc.sort(reverse = True)

for i in range(k):
    print(abc[i])
### BUGGY CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    INF = 10**18
    MX = 10**10
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,M,L = LI()
    road = [[] for _ in range(N)]
    for _ in range(M):
        a,b,c = LI()
        if c <= L:
            road[a-1].append((b-1,c))
            road[b-1].append((a-1,c))

    town = [[-1 for _ in range(N)] for _ in range(N)]

    for s in range(N):

        q = [(0,s)]
        town[s][s] = 0
        heapq.heapify(q)
        while q:
            z,u = heapq.heappop(q)
            if town[s][u] < z: continue
            n = z // MX
            w = z % MX
            for v,c in road[u]:
                nn = n
                nw = w + c
                if nw > L:
                    nw = c
                    nn += 1

                nz = nn * MX + nw
                if town[s][v] < 0 or town[s][v] > nz:
                    town[s][v] = nz
                    heapq.heappush(q,(nz,v))

    Q = NI()
    for _ in range(Q):
        s,t = LI()
        if town[s-1][t-1] < 0:
            print(-1)
        else:
            print(town[s-1][t-1]//MX)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq


def wf(d,n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

def main():
    INF = 10**18
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N,M,L = LI()
    road = [[INF] * N for _ in range(N)]
    for _ in range(M):
        a,b,c = LI()
        if c <= L:
            road[a-1][b-1] = c
            road[b-1][a-1] = c

    road = wf(road,N)


    gas = [[INF] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if road[i][j] <= L:
                gas[i][j] = 1

    gas = wf(gas,N)

    Q = NI()
    for _ in range(Q):
        s,t = LI()
        if gas[s-1][t-1] == INF:
            print(-1)
        else:
            print(gas[s-1][t-1]-1)


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

n = int(input())
A_list = list(map(int, input().split()))
for i in range(n):
    A_list[i] -= i
A_list.sort()
A_cum = [0] * n
for i in range(n):
    if i == 0:
        A_cum[0] = A_list[0]
    else:
        A_cum[i] = A_cum[i-1] + A_list[i]
def findinfindex(sortedlist, key, l, r):
    if r - l <= 0:
        return l
    m = (l+r+1)//2
    if sortedlist[m] > key:
        return findinfindex(sortedlist, key, l, m-1)
    else:
        return findinfindex(sortedlist, key, m, r)
sadnesses=[]
for b in range(A_list[0],A_list[n-1]+1):
    lastminus = findinfindex(A_list, b, 0, n-1)
    sadness = (lastminus + 1)*b - 2*A_cum[lastminus] + A_cum[n-1] - (n - lastminus - 1)*b
    sadnesses.append(sadness)
print(min(sadnesses))


### FIXED CODE ###

n = int(input())
A_list = list(map(int, input().split()))
for i in range(n):
    A_list[i] -= i
A_list.sort()

def sadness(a, mid):
    sad = 0
    for i in range(mid):
        sad += a[mid] - a[i]
    for i in range(mid+1,len(a)):
        sad += a[i] - a[mid]
    return sad

if n % 2 != 0:
    print(sadness(A_list, n//2))
else:
    print(min(sadness(A_list, n//2), sadness(A_list, n//2+1)))
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7

A = [a % MOD for a in A]

res = 0
for i in range(N-1):
    for j in range(i+1, N):
        res += (A[i] * A[j]) % MOD
        res %= MOD

print(res)

### FIXED CODE ###

#!/usr/bin/env python3

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

MOD = 10**9 + 7

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

A = [a % MOD for a in A]
A_d = [(a * a) % MOD for a in A]
res = ((sum(A)**2) % MOD - sum(A_d) % MOD) % MOD
res = res * pow(2, MOD-2, MOD)
res %= MOD

print(res)
### BUGGY CODE ###

N, A, B = map(int,input().split())
ans = 0
x = 0
Ball = []
while x < N:
    x = x + A + B
    for i in range(A):
        Ball.append('b')
    for i in range(B):
        Ball.append('r')
Ball = Ball[0:N]
ans = Ball.count('b')
print(ans)

### FIXED CODE ###

N, A, B = map(int,input().split())
x = N // (A + B)
y = N % (A + B)
ans = x * A + min(y,A)
print(ans)
### BUGGY CODE ###

N = int(input())
S = [input() for i in range(0, N)]

ans = 0

for i in range(0, N):
    S[i] = sorted([i for i in S[i]])
    
for i in range(0, N):
    for j in range(0, i):
        if S[i] == S[j]:
            ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
S = [input() for i in range(0, N)]

ans = 0
A = {}

for i in range(0, N):
    S[i] = sorted(S[i])
    S[i] = ''.join(S[i]) 
    if S[i] in A.keys():
        ans += A[S[i]]
        A[S[i]] += 1
    else:
        A[S[i]] = 1
    
print(ans)
### BUGGY CODE ###


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

while True:
    if min(A) == sum(A):
        break
    minA = A.index(min(A))
    maxA = A.index(max(A))
    A[maxA] = max(A)%min(A)
    if A[maxA]==0:
        A.pop(maxA)
print(min(A))





### FIXED CODE ###

import numpy as np

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

B = list(set(A))
B.sort()
C = np.asarray(B)

while(len(C)>1):
    t = C[0]
    C = np.append(C[1:]%t,t)
    C = list(set(C))
    C.sort()
    if C[0]==0:
        C = np.asarray(C[1:])
    else:
        C = np.asarray(C)

print(C[0])
### BUGGY CODE ###

#import sys
#import numpy as np
import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect
s=input()
k=int(input())
n=len(s)
a=[chr(i) for i in range(ord('a'),ord('z')+1)]
ans=set()
for i in a:
    if i not in s:
        continue
    if len(ans)>=5:
        break
    for c in range(n):
      if s[c]==i:
          l=c
          r=c
          while True:
            if  r>n:
                break
            ans.add(s[l:r+1])
            r+=1
ans=list(ans)
ans.sort()
print(ans[k-1])

### FIXED CODE ###

#import sys
#import numpy as np
import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect
s=input()
k=int(input())
n=len(s)
a=[chr(i) for i in range(ord('a'),ord('z')+1)]
ans=set()
for i in a:
    if i not in s:
        continue
    if len(ans)>=5:
        break
    for c in range(n):
      if s[c]==i:
          l=c
          r=c
          while True:
            if  r>n or r-l>6:
                break
            ans.add(s[l:r+1])
            r+=1
ans=list(ans)
ans.sort()
print(ans[k-1])
### BUGGY CODE ###

import collections

def combination(n, r, mod=10**9+7):
    n1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod
    
n = int(input())
li = list(map(int,input().split()))
c = collections.Counter(li)    
s = list(set(li))

for i in range(n):
    c[li[i]] -= 1
    ans = 0
    # print(c)
    # print(c[s[1]])
    # print(s)
    
    for j in range(len(s)):
        if c[s[j]] <= 1:
            continue
        ans += combination(c[s[j]], 2)
    c[li[i]] += 1
        
    print(ans)

### FIXED CODE ###

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

ans_li = [0]*(n+10)

for i in li:
    ans_li[i] += 1
    
result = 0    
for i in ans_li:
    result += (i * (i-1)) // 2
    
for i in li:
    ans = result
    ans += ((ans_li[i] - 1) * (ans_li[i] - 2)) // 2- (ans_li[i] * (ans_li[i] - 1)) // 2
    print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

FRIEND = [[0]*n for _ in range(n)]
BLOCK = [[0]*n for _ in range(n)]

for _ in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    FRIEND[a][b] = FRIEND[b][a] = 1

for _ in range(k):
    a, b = map(lambda x: int(x)-1, input().split())
    BLOCK[a][b] = BLOCK[b][a] = 1


def make_dfs():
    visited = [0] * n

    def inner(v):
        visited[v] = 1
        for v2 in range(n):
            if not FRIEND[v][v2]:
                continue
            if visited[v2]:
                continue
            inner(v2)
        return visited
    return inner


ans = [-1]*n

for i in range(n):
    friends = FRIEND[i]
    dfs = make_dfs()
    possibly_friends = dfs(i)
    blocks = BLOCK[i]
    blocks = [pf and b for pf, b in zip(possibly_friends, blocks)]
    ans[i] = sum(possibly_friends) - sum(friends) - sum(blocks) - 1

print(*ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

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

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

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx != ry:
            self.p[ry] += self.p[rx]
            self.p[rx] = ry

    def count_member(self, x):
        return -self.p[self.find(x)]


uf = UnionFind(n)

ab = []
for i in range(m):
    a, b = map(lambda x: int(x)-1, input().split())
    ab.append((a, b))
    uf.union(a, b)

cd = [list(map(lambda x: int(x)-1, input().split())) for _ in range(k)]
ans = [uf.count_member(i)-1 for i in range(n)]

for a, b in ab:
    if uf.find(a) == uf.find(b):
        ans[a] -= 1
        ans[b] -= 1

for c, d in cd:
    if uf.find(c) == uf.find(d):
        ans[c] -= 1
        ans[d] -= 1

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

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

ans = 1
for i in lis:
    ans *= i
    
if ans > 10**18:
    print("-1")
else:
    print(ans)


### FIXED CODE ###

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

if 0 in lis:
    print(0)
    exit()

ans = 1
for i in lis:
    ans *= i
    if ans >= 10**18:
        break

if ans > 10**18:
    print("-1")
else:
    print(ans)
### BUGGY CODE ###

import copy
N = int(input())
A = []
for i in range(N):
  A.append(int(input()))

for i in range(N):
  if max(A) != A[i]:
    print(max(A))
  else:
    AA = copy.deepcopy(A)
    AA.remove(max(A))
    print(max(AA))

### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
  A.append(int(input()))
B = sorted(A)

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

# match matching
import bisect
import sys
input = sys.stdin.readline
compare = [10**i for i in range(5*10**3+1)]
N, M = map(int, input().split())
ok = list(map(int, input().split()))
ok.sort()
a = [i for i in range(1, 10)]
b = [2, 5, 5, 4, 5, 6, 3, 7, 6]
data = {a[i]: b[i] for i in range(9)}
dp = [[0 for i in range(N+1)] for j in range(M+1)]


def find(X):
    return bisect.bisect_right(compare, X)


for i in range(M):
    for cnt in range(N+1):
        for num in ok[:i+1]:
            cost = data[num]
            if cnt > cost:
                K = dp[i+1][cnt-cost]
                if K > 0:
                    dp[i+1][cnt] = max(K + num*10 ** find(K), dp[i+1][cnt])
                    continue
                else:
                    dp[i+1][cnt] = max(K, dp[i+1][cnt])
                    continue
            elif cnt == cost:
                dp[i+1][cnt] = max(num, dp[i+1][cnt])
                continue
            else:
                dp[i+1][cnt] = max(dp[i][cnt], dp[i+1][cnt])
                continue
ans = dp[M][N]
print(ans)


### FIXED CODE ###

matches = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

n, m = map(int, input().split())
alist = list(map(int, input().split()))
alist.sort(reverse=True)

dp = [-1 for _ in range(n + 1)]
dp[0] = 0
for a in alist:
    match = matches[a]
    for i in range(n - match + 1):
        if dp[i] == -1: continue
        dp[i + match] = max(dp[i + match], dp[i] * 10 + a)

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

import math
 
 
def nCr(n,r):
    if n<r:
        return 0
    
    result = math.factorial(n)//math.factorial(r)//math.factorial(n-r)
    return result

def compute(count):
    total = 0
    for i in count:
        total += nCr(i,2)
    return total


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

count = [0] * (N+1)

for value in data:
    count[value] += 1
    

for i in range(len(data)):
    count[data[i]] -= 1
    
    total = compute(count)
    print(total)
          
          
    count[data[i]] += 1


### FIXED CODE ###

import math
 


def nC2(i):
    if i<=1:
        return 0
    return i*(i-1)//2

def compute(count):
    total = 0
    for i in count:
        total += nC2(i)
    return total


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

count = [0] * (N+1)

for value in data:
    count[value] += 1
    
    
total = compute(count)    

for value in data:
    remove = nC2(count[value])
    add = nC2(count[value]-1)

    print(total-remove+add)
### BUGGY CODE ###

N = int(input())
s = [''] * N
for _ in range(N):
    tmp = sorted(input())
    s[_] = ''.join(tmp)
tmp = sorted(s)
cnt = 0
index = 1
for _ in range(0,N - 1,index):
    index = 1
    for j in range(_ + 1, N):
        if tmp[_] == tmp[j]:
            cnt += 1
            index += 1
        else:
            break

print(cnt)


### FIXED CODE ###

N = int(input())
s = [''] * N
for _ in range(N):
    tmp = sorted(input())
    s[_] = ''.join(tmp)
tmp = sorted(s)
cnt = 1
index = 0
ansFlag = True
ans1 = 0
while ansFlag:
    cnt = 1
    for j in range(index + 1, N):
        if tmp[index] == tmp[j]:
            cnt += 1
            index += 1
        else:
            index += 1
            break

    tmp2 = 0
    for i in range(cnt, 0, -1):
        tmp1 = i - 1
        tmp2 += tmp1
        ans = tmp2
    ans1 += ans
    if index == (N - 1):
        ansFlag = False

print(ans1)
### BUGGY CODE ###

S=list(input())
n=len(S)
ans=0
flag=True
while flag:
    flag=False
    for i in range(n-1):
        if S[i]=='B' and S[i+1]=='W':
            S[i],S[i+1]='W','B'
            ans+=1
            flag=True
print(ans)

### FIXED CODE ###

S=list(input())
n=len(S)
ans=0
b=0

for s in S:
    if s=='B':b+=1
    else:ans+=b
    
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
E = [[] for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  E[a-1].append(b-1)
  E[b-1].append(a-1)
counts = [False]*N
q = [0]
counts[0] = True
r = K
while len(q) > 0:
  i = q.pop(0)
  # get_nexts
  js = E[i]
  c = K-1 if i == 0 else K-2
  rt = 1
  for j in js:
    if not(counts[j]):
      counts[j] = True
      rt = (rt*c)%1000000007
      c -= 1
      q.append(j)
  r = (r*rt)%1000000007
print(r)


### FIXED CODE ###

N, K = map(int, input().split())
E = [[] for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  E[a-1].append(b-1)
  E[b-1].append(a-1)
counts = [False]*N
q = [0]
counts[0] = True
r = K
while len(q) > 0:
  i = q.pop(0)
  # get_nexts
  js = E[i]
  c = K-1 if i == 0 else K-2
  for j in js:
    if not(counts[j]):
      counts[j] = True
      r = (r*c)%1000000007
      c -= 1
      q.append(j)
print(r)
### BUGGY CODE ###

import math, collections

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

def prime(n):
    p = []
    flag = [True] * (n - 1)
    for i in range(n - 1):
        if flag[i] == True:
            p.append(i + 2)
            num = i
            while num <= n - 2:
                flag[num] = False
                num += i + 2
    return p

gcd = 0
for i in range(n):
    gcd = math.gcd(gcd, a[i])
if gcd != 1:
    print("not coprime")
else:
    flag = True
    a2 = collections.deque(a)
    while len(a2) > 1:
        temp1 = a2.popleft()
        temp2 = a2.popleft()
        if math.gcd(temp1, temp2) != 1:
            print("setwise coprime")
            break
        else:
            a2.append(temp1 * temp2)
    else:
        print("pairwise coprime")

### FIXED CODE ###

import math, sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))

def prime(n):
    p = []
    min_p = [0 for i in range(n - 1)]
    flag = [True] * (n - 1)
    for i in range(n - 1):
        if flag[i] == True:
            p.append(i + 2)
            num = i
            while num <= n - 2:
                if flag[num] == True:
                    min_p[num] = i + 2
                flag[num] = False
                num += i + 2
    return p, min_p

gcd = 0
for i in range(n):
    gcd = math.gcd(gcd, a[i])
if gcd != 1:
    print("not coprime")
else:
    p = prime(max(a))
    p_list = {i:0 for i in p[0]}
    min_p = p[1]
    flag = True
    for i in a:
        temp = set()
        while i != 1:
            temp.add(min_p[i - 2])
            i //= min_p[i - 2]
        for j in temp:
            if p_list[j] == 1:
                flag = False
                break
            else:
                p_list[j] += 1
        if flag == False:
            print("setwise coprime")
            break
    else:
        print("pairwise coprime")
### BUGGY CODE ###

import numpy as np


def read_input(trans=int):
    return list(map(trans, input().split()))


N, K = read_input()
A = np.array(read_input(), dtype="int")
B = np.zeros(N, dtype="int")
coordinate = np.arange(1, N+1)


for _ in range(K):
    for i in range(N):
        c = coordinate[i]
        B[i] = (A >= np.abs(coordinate - c)).sum()
    A = B.copy()

print(" ".join(map(str, A.tolist())))


### FIXED CODE ###

def read_input(trans=int):
    return list(map(trans, input().split()))


N, K = read_input()
A = read_input()
K = min(K, 41)

for _ in range(K):
    B = [0]*N
    for i in range(N):
        start = max(i-A[i], 0)
        end = min(i+A[i], N-1)

        B[start] += 1
        if end+1 < N:
            B[end+1] -= 1
    for i in range(1, N):
        B[i] += B[i-1]
    A = B.copy()


print(" ".join(map(str, A)))
### BUGGY CODE ###

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

B=[]
for i,a in enumerate(A):
  if i%2==0:
    B.append(a)
  else:
    B.insert(0,a)
if N%2==1:
  B=B[::-1]

print(" ".join(map(str,B)))

### FIXED CODE ###

import collections

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

B=collections.deque([])
for i in range(N):
  if i%2==0:
    B.append(A[i])
  else:
    B.appendleft(A[i])
#print(B)
B=list(B)
#print(B)
if N%2==1:
  B=B[::-1]

print(" ".join(map(str,B)))
### BUGGY CODE ###

from collections import deque

N=int(input())
a=[set() for v in range(N+1)]
d=[[-1 for v in range(N+1)] for u in range(N+1)]
for e in range(1,N):
    u,v,w=map(int,input().split())
    a[u].add(v);a[v].add(u)
    d[u][v]=d[v][u]=w

#c=[None for v in range(N+1)] # color
d1=[None for v in range(N+1)] # distance from 1

# print(a)
# print(d)

q=deque()
q.append(1);d1[1]=0
while q:
    u=q.popleft()
    for v in a[u]:
        if d1[v] is None:
            d1[v]=d1[u]+d[u][v]
            q.append(v)

# print(d1)
for d1i in d1[1:]:
    print(d1i%2)

### FIXED CODE ###

from collections import deque

N=int(input())
a=[set() for v in range(N)] # 0-initial
for e in range(1,N):
    u,v,w=map(int,input().split())
    a[u-1].add((v-1,w))
    a[v-1].add((u-1,w))

d=[-1 for v in range(N)] # distance from 0

q=deque()
q.append(0);d[0]=0
while q:
    u=q.popleft()
    for v,w in a[u]:
        if d[v]==-1:
            d[v]=d[u]+w
            q.append(v)

for di in d:
    print(di%2)
### BUGGY CODE ###

import itertools

def tri_check(a,b,c):
  if a<b+c and b<a+c and c<a+b:
    return True
  else:
    False

N = int(input())
L = list(map(int, input().split()))
ans = 0
for a,b,c in list(itertools.combinations(L, 3)):
  if tri_check(a,b,c):
    ans += 1
    
print(ans)

### FIXED CODE ###

from collections import Counter
import bisect 

N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0

for i in range(N):
  for j in range(i+1, N):
    idx = bisect.bisect_right(L, L[i]+L[j]-1)
    ans += (idx-(j+1))

print(ans)