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

num = list(map(int, input().split()))
n, tw = num[0], num[1]

w = [0]
v = [0]

for i in range(n):
    vals = list(map(int, input().split()))
    w.append(vals[0])
    v.append(vals[1])

if sum(w) < tw:
    tw = sum(w)

dp = [[0 for i in range(tw+1)] for j in range(n+1)]

for i in range(1,n+1):
    for j in range(1,tw+1):
        if w[i] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], v[i] + dp[i-1][j-w[i]])

print(dp[-1][-1])




### FIXED CODE ###

num = list(map(int, input().split()))
n, tw = num[0], num[1]

w = [0]
v = [0]

for i in range(n):
    vals = list(map(int, input().split()))
    w.append(vals[0])
    v.append(vals[1])

if sum(w) < tw:
    tw = sum(w)

dp = [[0 for i in range(tw+1)] for j in range(n+1)]

for i in range(1,n+1):
    for j in range(1,tw+1):
        if w[i] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], v[i] + dp[i-1][j-w[i]])

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

import sys
input = sys.stdin.readline
import bisect

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

Color = []
for a in A:
  idx = bisect.bisect_left(Color,a)
  if idx == 0:
    Color.insert(0,a)
  else:
    Color[idx-1] = a
  #Color.sort()
  #print(Color)
print(len(Color))

### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect

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

Color = []
for a in A:
  idx = bisect.bisect_right(Color,a)
  if idx == len(Color):
    Color.append(a)
  else:
    Color[idx] = a
  #Color.sort()
  #print(Color)
print(len(Color))
### BUGGY CODE ###

# from math import factorial,sqrt,ceil,gcd
# from itertools import permutations,combinations,combinations_with_replacement
# from collections import deque,Counter
# import re
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# import networkx as nx
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb

# slist = "abcdefghijklmnopqrstuvwxyz"
N = int(input())
lisA = list(map(int,input().split()))
# arrA = np.array(input().split(),dtype=np.int64)

ans = 0
for i in range(1,N):
    for j in range(0,N-i):
        if lisA[j]+lisA[j+i]==i:
            ans += 1
print(ans)
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))


### FIXED CODE ###

# from math import factorial,sqrt,ceil,gcd
# from itertools import permutations,combinations,combinations_with_replacement
from collections import deque,Counter
# import re
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# import networkx as nx
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb

# slist = "abcdefghijklmnopqrstuvwxyz"
N = int(input())
lisA = [0] + list(map(int,input().split()))
# arrA = np.array(input().split(),dtype=np.int64)
# j-i == Ai+Aj => i+Ai == j-Aj
lisI = []
for i,num in enumerate(lisA):
    lisI.append(i+num)

cnt = Counter(lisI[1:])
ans = 0
for j,num in enumerate(lisA):
    if j == 0:
        continue
    elif j-num in cnt:
        ans += cnt[j-num]
    else:
        continue

print(ans)
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))
### BUGGY CODE ###

N,K=map(int,input().split())
s=1
lis=list(range(N+1))
 
def tousa(l,r):
    return((l+r)*(r-l+1)//2)
 
 
for i in range(K,N+1):
    s+=(tousa(lis[-i:][0], lis[-i:][-1])-tousa(lis[:i][0], lis[:i][-1])+1)
# print(s)
print(s%(10**9+7))

### FIXED CODE ###

N,K=map(int,input().split())
s=1

def tousa(l,r):
    return((l+r)*(r-l+1)//2)

for i in range(K,N+1):
    s+= (tousa(N-i+1, N) - tousa(0, i-1) + 1)
# print(s)
print(s%(10**9+7))
### BUGGY CODE ###

from decimal import Decimal


def div(n):
    n = int(n)
    two = format(n, 'b')[::-1].find('1')
    if two < 0:
        return(-1, -1)
    n = n >> two
    cnt = 0
    while n % 5 == 0:
        n //= 5
        cnt += 1
    return (two, cnt)


n = int(input())
arr = [div(int(Decimal(input()) * 10**9)) for _ in range(n)]

ans = 0
for i in range(len(arr)):
    for j in range(i + 1, len(arr)):
        (a, b), (c, d) = arr[i], arr[j]
        if a + c >= 18 and b + d >= 18:
            ans += 1
    
print(ans)

### FIXED CODE ###

def div(n, d):
    cnt = 0
    while n % d == 0 and cnt < 18:
        n //= d
        cnt += 1
    return cnt


n = int(input())
dp = [[0]*19 for _ in range(19)]

ans = 0
for _ in range(n):
    x = round(float(input()) * pow(10, 9))
    two = div(x, 2)
    five = div(x, 5)
    ans += dp[18 - two][18 - five]
    for i in range(two + 1):
        for j in range(five + 1):
            dp[i][j] += 1

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

# -*- coding: utf-8 -*-
# E

import sys
# 再起回数上限変更
# sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
a = []
x = []

for i in range(H):
    a.append(list(map(int, input().split())))
for i in range(H):
    x.append(list(map(int, input().split())))
    for j in range(W):
        x[i][j] = abs(x[i][j] - a[i][j])

# print(x)

dp = [[[] for _ in range(W)] for _ in range(H)]
# print(dp[0][0])

dp[0][0].append(x[0][0])
# print(dp)

for i in range(H):
    for j in range(W):
        if i > 0:
            for num in dp[i-1][j]:
                # print(num)
                dp[i][j].append(num + x[i][j])
                dp[i][j].append(abs(num - x[i][j]))
        if j > 0:
            for num in dp[i][j-1]:
                # print(num)
                dp[i][j].append(num + x[i][j])
                dp[i][j].append(abs(num - x[i][j]))

print(min(dp[H-1][W-1]))


### FIXED CODE ###

# -*- coding: utf-8 -*-
# E: bit演算を活用して効率的に計算しないとTLEになる

# dp[[i][j]で、(i,j)で可能な偏りを格納していく
# 1, 2, 3が可能な場合は"00000111"と表現する
# n + m を可能にするには、n << mにすれば良い
# (1, 2, 3)に2を足して(3, 4, 5)を可能にするなら、
# "00011100"としたいので、n << mで良い
# (3, 4, 5)に±4する場合；
# 求めたいのは(7, 8, 9) | (-1, 0, 1)
# −１を1としたい

import sys
# 再起回数上限変更
# sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
a = []
x = []

for i in range(H):
    a.append(list(map(int, input().split())))
for i in range(H):
    x.append(list(map(int, input().split())))
    for j in range(W):
        x[i][j] = abs(x[i][j] - a[i][j])


dp = [[0 for _ in range(W)] for _ in range(H)]
dp[0][0] = 1 << x[0][0]
# print(bin(dp[0][0]))


def reverse(d, x):
    res = 0
    for i in range(x+1):
        res <<= 1
        if (1<<i) & d:
            res |= 1
    return res


for i in range(H):
    for j in range(W):
        g = x[i][j]
        if i > 0:
            d1 = dp[i-1][j]
            dp[i][j] |= d1 << g | d1 >> g | reverse(d1, g)
        if j > 0:
            d2 = dp[i][j-1]
            dp[i][j] |= d2 << g | d2 >> g | reverse(d2, g)


a = dp[H-1][W-1]
for i in range(a.bit_length()):
    if a >> i & 1 == 1:
        print(i)
        sys.exit()
### BUGGY CODE ###

n=int(input())
S=str(input())
r=S.count('R')
g=S.count('G')
b=S.count('B')
cnt=r*g*b
for i in range(n):
    for a in range(1,n):
        j=i+a
        k=j+a
        if k==n:
            break
        if k<n:
            if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
                cnt-=1

print(cnt)

### FIXED CODE ###

n=int(input())
S=str(input())
r=S.count('R')
g=S.count('G')
b=S.count('B')
cnt=r*g*b
for i in range(n):
    for a in range(1,n):
        j=i+a
        k=j+a
        if k>=n:
            break
        if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
            cnt-=1

print(cnt)
### BUGGY CODE ###

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

dp = [[[0 for k in range(N+1)] for j in range(N+1)] for i in range(N+1)]
dp[0][0][0] = 0

a,b,c = 0,0,0
for i in range(N):
    if A[i] == 1:
        a += 1
    elif A[i] == 2:
        b += 1
    else:
        c += 1

for k in range(c+1):
    for j in range(b+c-k+1):
        for i in range(a+b+c-k-j+1):
            if i==j==k==0:
                continue
            temp = N
            if i!=0:
                temp += dp[i-1][j][k]*i
            if j!=0:
                temp += dp[i+1][j-1][k]*j
            if k!=0:
                temp += dp[i][j+1][k-1]*k
            dp[i][j][k] = temp/(i+j+k)

print(dp[a][b][c])

### FIXED CODE ###

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

dp = [[[0.0 for k in range(N+1)] for j in range(N+1)] for i in range(N+1)]
dp[0][0][0] = 0

a,b,c = 0,0,0
for i in range(N):
    if A[i] == 1:
        a += 1
    elif A[i] == 2:
        b += 1
    else:
        c += 1

for k in range(c+1):
    for j in range(b+c-k+1):
        for i in range(a+b+c-k-j+1):
            if i==j==k==0:
                continue
            temp = N
            if i!=0:
                temp += dp[i-1][j][k]*i
            if j!=0:
                temp += dp[i+1][j-1][k]*j
            if k!=0:
                temp += dp[i][j+1][k-1]*k
            dp[i][j][k] = temp/(i+j+k)

print(dp[a][b][c])
### BUGGY CODE ###

n=int(input())

for k in range(1,n+1):

    ans=0
    for x in range(1,51):
        if k-x**2<=0:
            break
        for y in range(1,51):
            if k-x**2- y**2<=0:
                break

            for z in range(1,51):
                if x**2 + y**2 + z**2 +x*y + y*z + z*x ==k:
                    ans+=1
                    break


    print(ans)


### FIXED CODE ###

n=int(input())

ans=[0]*(n+1)

for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            f= x**2 + y**2 + z**2 + x*y + y*z + z*x
            if f<=n:
                ans[f]+=1

for i in range(1,n+1):
    print(ans[i])
### BUGGY CODE ###

N = int(input())
tmp = input().split(" ")
l = [int(i) for i in tmp]
ans = 0
for i in range(N):
  for j in range(i+1):
    if l[j] < l[i]:
      break
  else:
    ans+=1
print(ans)


### FIXED CODE ###

N = int(input())
tmp = input().split(" ")
l = [int(i) for i in tmp]
ans = 1
ll = list()
ll.append(l[0])
for i in range(1,N):
    ll.append(min(ll[i-1],l[i]))
for i in range(1,N):
  if ll[i-1] > l[i]:
    ans+=1
print(ans)
### BUGGY CODE ###

from bisect import bisect_right
A,B,Q = map(int,input().split())
S = [int(input()) for _ in range(A)]
S.append(10**11)
T = [int(input()) for _ in range(B)]
T.append(10**11)
Ds = {i:0 for i in range(A)}
Ds[A] = 10**11
cur = 0
for i in range(A):
    ind = bisect_right(T,S[i])
    if ind==0:
        Ds[i] = T[0]-S[i]
    else:
        Ds[i] = min(T[ind]-S[i],S[i]-T[ind-1])
Dt = {j:0 for j in range(B)}
Dt[B] = 10**11
cur = 0
for j in range(B):
    ind = bisect_right(S,T[j])
    if ind==0:
        Dt[j] = S[0]-T[j]
    else:
        Dt[j] = min(S[ind]-T[j],T[j]-S[ind-1])
for _ in range(Q):
    x = int(input())
    inds = bisect_right(S,x)
    if inds==0:
        cnts = S[0]-x+Ds[0]
    else:
        cnts = min(S[inds]-x+Ds[inds],x-S[inds-1]+Ds[inds-1])
    indt = bisect_right(T,x)
    if indt==0:
        cntt = T[0]-x+Dt[0]
    else:
        cntt = min(T[indt]-x+Dt[indt],x-T[indt-1]+Dt[indt-1])
    print(min(cnts,cntt))

### FIXED CODE ###

from bisect import bisect_right
A,B,Q = map(int,input().split())
S = [int(input()) for _ in range(A)]
S.append(10**11)
S.insert(0,-10**11)
T = [int(input()) for _ in range(B)]
T.append(10**11)
T.insert(0,-10**11)
Ds = {i:0 for i in range(1,A+1)}
Ds[A+1] = 10**11
Ds[0] = 10**11
for i in range(1,A+1):
    ind = bisect_right(T,S[i])
    Ds[i] = min(T[ind]-S[i],S[i]-T[ind-1])
Dt = {j:0 for j in range(1,B+1)}
Dt[B+1] = 10**11
Dt[0] = 10**11
for j in range(1,B+1):
    ind = bisect_right(S,T[j])
    Dt[j] = min(S[ind]-T[j],T[j]-S[ind-1])
for _ in range(Q):
    x = int(input())
    inds = bisect_right(S,x)
    cnts = min(S[inds]-x+Ds[inds],x-S[inds-1]+Ds[inds-1])
    indt = bisect_right(T,x)
    cntt = min(T[indt]-x+Dt[indt],x-T[indt-1]+Dt[indt-1])
    print(min(cnts,cntt))
### BUGGY CODE ###

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

fac = [0 for _ in range(n+1)]
inv = [0 for _ in range(n+1)]
finv = [0 for _ in range(n+1)]

fac[0] =fac[1]= 1
inv[0] =inv[1]= 1
finv[0] = finv[1] = 1

p = 10**9 + 7
#p = 31
#inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
for i in range(2,n+1):
    fac[i] = (fac[i-1]*i)%p
    inv[i] = (p - inv[p%i]*int(p/i)%p)%p
    finv[i] = (finv[i-1]*inv[i])%p
    
#print(fac)
#print(inv)
#print(finv)

def cal(m,k):
    return fac[m]*(finv[k]*finv[m-k]%p)%p

ans = (2**n -1)%p
ans = (ans - cal(n,a) - cal(n,b))%p

if(ans<0):
    ans = -1*ans

print(ans)

### FIXED CODE ###

import math

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

p = 10**9 + 7


def cmb(n, r):
    total = 1
    for i in range(r):
        total = total * (n - i) % p
        
    return total * pow(math.factorial(r), p - 2, p) % p

total = pow(2, n, p)-1
a_total = cmb(n, a)
b_total = cmb(n, b)
print((total - a_total - b_total) % p)
### BUGGY CODE ###

n=int(input())
s=list(input())

rn=s.count('R')
gn=s.count('G')
bn=n-rn-gn

ans=bn*gn*rn
if n>2:
  
  for x in range(n-2):
    
    y=(n-1-x)//2
    for i in range(1,y+1):
      if  (not s[x]==s[x+i]) & (not s[x]==s[x+i+i]) & (not s[x+i]==s[x+i+i]):
        ans-=1
        
  print(ans)
    
else:
  print(0)


### FIXED CODE ###

n=int(input())
s=list(input())

rn=s.count('R')
gn=s.count('G')
bn=n-rn-gn

ans=bn*gn*rn
if n>2:
  
  for x in range(n-2):
    
    y=(n-1-x)//2
    for i in range(1,y+1):
      if  (not s[x]==s[x+i]) & (not s[x]==s[x+i+i]) & (not s[x+i]==s[x+i+i]):
        ans-=1
        
  print(ans)
    
else:
  print(0)
### BUGGY CODE ###

from collections import defaultdict
from bisect import bisect_right

""" Binary Indexed Tree """
class BIT:

    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N+1)

    def add(self, x, a):
        while x <= self.N:
            self.bit[x] += a
            x += x & -x

    def sum(self, x):
        ret = 0
        while x != 0:
            ret += self.bit[x]
            x -= x & -x
        return ret

    # x < sum(index) となる最小の index を返す
    def upper_bound(self, x):
        l, r = -1, self.N
        while l+1 < r:
            m = (l+r)//2
            y = self.sum(m)
            if x < y:
                r = m
            else:
                l = m
        return r

    # x <= sum(index) となる最小の index を返す
    def lower_bound(self, x):
        l, r = -1, self.N
        while l+1 < r:
            m = (l+r)//2
            y = self.sum(m)
            if y < x:
                l = m
            else:
                r = m
        return r

N, Q = map(int, input().split())
c = list(map(int, input().split()))
rl = [None] * Q
for i in range(Q):
    l, r = map(int, input().split())
    rl[i] = (r, l, i)
rl.sort()
bit = BIT(N+1)
ans = [None] * Q
last_idx = [-1] * (N+1)
j = 0
for r, l, i in rl:
    while j < r:
        if last_idx[c[j]] == -1:
            last_idx[c[j]] = j
        else:
            bit.add(last_idx[c[j]]+1, -1)
            last_idx[c[j]] = j
        bit.add(j+1, 1)
        j += 1
    ans[i] = bit.sum(r) - bit.sum(l-1)
print(*ans, sep='\n')
            

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    bit = [0] * (N+1)

    def add(x, a):
        while x <= N:
            bit[x] += a
            x += x & -x

    def sum(x):
        ret = 0
        while x != 0:
            ret += bit[x]
            x -= x & -x
        return ret

    c = list(map(int, input().split()))
    lr = [None] * Q
    for i in range(Q):
        l, r = map(int, input().split())
        lr[i] = (i, l, r)
    lr.sort(key=lambda x: x[2])
    ans = [None] * Q
    last_idx = [-1] * (N+1)
    j = 0
    for i, l, r in lr:
        while j < r:
            if last_idx[c[j]] == -1:
                last_idx[c[j]] = j
            else:
                add(last_idx[c[j]]+1, -1)
                last_idx[c[j]] = j
            add(j+1, 1)
            j += 1
        ans[i] = sum(r) - sum(l-1)
    for a in ans:
        print(a)
            
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

i = 2
len_ = len(a_lst)
sum_ = {}
xor_ = {}
res = 0
for i in range(len_):
  sum_[i] = {}
  xor_[i] = {}
  for j in range(i, len_):
    if j == i:
      sum_[i][j] = a_lst[i]
      xor_[i][j] = a_lst[i]
      res += 1
    else:
      sum_[i][j] = sum_[i][j-1] + a_lst[j]
      xor_[i][j] = xor_[i][j-1] ^ a_lst[j]  
      if sum_[i][j] == xor_[i][j]:
        res += 1
print(res)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
l=0
r=1
t=a[0]
ans=0
 
while l<n:
  if r==n:
    ans+=r-l
    l+=1
    continue
  if t+a[r]==t^a[r]:
    t+=a[r]
    r+=1
  else:
    ans+=r-l
    t-=a[l]
    l+=1
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
def main():
    N, Q = map(int, input().split())
    E = [[] for i in range(N+1)]
    counter = [0] * (N+1)

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

    for i in range(Q):
        # 頂点p を根とする部分木に含まれるカウンターにxを足す
        p, x = map(int, input().split())
        counter[p] += x

    queue = []

    parent = [1]
    def mktree(v, parent, E):
        children = E[v]
        children.remove(parent)
        for child in children:
            mktree(child, v, E)

    while parent:
        p = parent.pop()
        for child in E[p]:
            E[child].remove(p)
            parent.append(child)

    def get(v, children, counter):
        c = counter[v]
        for child in children[v]:
            counter[child] += c
            get(child, children, counter)
    """
    parent = [1]
    while parent:
        p = parent.pop()
        c = counter[p]
        for child in E[p]:
            counter[child] += c
            parent.append(child)
    """
    get(1, E, counter)
    print(" ".join(str(x) for x in counter[1:]))

main()






### FIXED CODE ###

def main():
    import sys
    sys.setrecursionlimit(2*10**5)
    N, Q = map(int, input().split())
    E = [[] for i in range(N+1)]
    counter = [0] * (N+1)

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

    for i in range(Q):
        # 頂点p を根とする部分木に含まれるカウンターにxを足す
        p, x = map(int, input().split())
        counter[p] += x

    queue = []

    parent = [1]
    def mktree(v, parent, E):
        children = E[v]
        children.remove(parent)
        for child in children:
            mktree(child, v, E)

    while parent:
        p = parent.pop()
        for child in E[p]:
            E[child].remove(p)
            parent.append(child)

    def get(v, children, counter):
        c = counter[v]
        for child in children[v]:
            counter[child] += c
            get(child, children, counter)

    parent = [1]
    while parent:
        p = parent.pop()
        c = counter[p]
        for child in E[p]:
            counter[child] += c
            parent.append(child)

    print(" ".join(str(x) for x in counter[1:]))

main()
### BUGGY CODE ###

S = input()
ans = 0
for i in range(6, int(S)//2019 + 1):
  d = str(2019*i)
  if "0" in d:
    continue
  ans += S.count(d)
print(ans)


### FIXED CODE ###

s = input()
a = 0
mods = [0]*2019
mods[a] += 1
r = 1
for i in s[::-1]:
  a = (a+int(i)*r)%2019
  r = r*10%2019
  mods[a] += 1
ans = 0
for i in mods:
  ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)

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

    dfs(0)
    print(*P)

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

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

    print(*P)

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

n = int(input())
s = list(map(int,input()))
ans =[]
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            ans.append(s[i]*100+10*s[j]+s[k])
print(len(set(ans)))

### FIXED CODE ###

n = int(input())
s = str(input())

number_i = list(range(10))
ans = 0

for i in range(n-2):
    if int(s[i]) in number_i:
        number_i.remove(int(s[i]))
        number_j = list(range(10))
        #print(number_i)

        for j in range(i+1,n-1):
            if int(s[j]) in number_j:
                number_j.remove(int(s[j]))
                number_k = list(range(10))

                for k in range(j+1,n):
                    if int(s[k]) in number_k:
                        number_k.remove(int(s[k]))
                        ans += 1
                        #print(int(s[i])*100+int(s[j])*10+int(s[k]))

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

n = int(input())
List = list(map(int, input().split()))
ans = 0
while all(i%2 == 0 for i in List):
  a = [i/2 for i in List]
  ans += 1
print(ans)

### FIXED CODE ###

n=int(input())
List=list(map(int,input().split()))
ans=0
while(1):
    for i in range(n):
        if List[i]%2!=0:
            print(ans)
            exit()
    for i in range(n):
        List[i]//=2
    ans+=1
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
graph = [[float('inf') for _ in range(n)] for _ in range(n)]
graph1 = {i:[] for i in range(n)}
for _ in range(n-1):
  u,v,w = map(int,input().split())
  graph[u-1][v-1] = w
  graph[v-1][u-1] = w
  graph1[u-1].append(v-1)
  graph1[v-1].append(u-1)
  
  
color = [-1 for i in range(n)] 
color[0] = 0
def dfs(i,j):#(child, parent)
  for k in graph1[i]:
    if k ==j:
      continue
    if color[k] != -1:
      continue
    if graph[k][i] %2:
      color[k] = 1 -color[i]
    else:
      color[k] = color[i]
    dfs(k,i)
dfs(0,-1)

for i in range(n):
  print(color[i])



### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
d = {}
graph = {i:[] for i in range(n)}
for _ in range(n-1):
  u,v,w = map(int,input().split())
  d[(u-1,v-1)] = w
  graph[u-1].append(v-1)
  graph[v-1].append(u-1)
  
  
color = [-1 for i in range(n)] 
color[0] = 0
from collections import deque
queue =deque([0])

while queue:
  p = queue.popleft()
  color_p = color[p]
  for i in graph[p]:
    if color[i] != -1:
      continue
    else:
      if d[(min(i,p),max(i,p))] %2:
        color[i] = 1 - color_p
      else:
        color[i] = color_p
      queue.append(i)

for i in range(n):
  print(color[i])