Problem Statement

There is a rooted tree $T$ with $N$ vertices numbered $1$ to $N$. The root is vertex $1$, and the parent of vertex $i$ $(2 \leq i \leq N)$ is $P_i$. Each vertex has two non-negative integer values called beauty and weight. The beauty and weight of vertex $i$ are $B_i$ and $W_i$, respectively. Additionally, each vertex is painted red or blue. The color of vertex $i$ is represented by an integer $C_i$: vertex $i$ is painted red if $C_i = 0$, and blue if $C_i = 1$.

For vertex $v$, let $F(v)$ be the answer to the following problem.

Let $U$ be the rooted tree that is the subtree of $T$ rooted at $v$. You can perform the following sequence of operations on $U$ zero or more times. (The operations do not affect the beauties, weights, or colors of the vertices that are not being deleted.)

• Choose a vertex $c$ other than the root. Let $p$ be the parent of $c$.
• For each edge whose endpoint on the parent side is $c$, do the following:
• Let $u$ be the endpoint of the edge other than $c$. Delete the edge and connect $p$ and $u$ with a new edge, with $p$ on the parent side.
• Delete the vertex $c$, and the edge connecting $p$ and $c$.

A rooted tree that can be obtained as $U$ after some operations is called a good rooted tree when all of the following conditions are satisfied.

• For every edge in $U$, the edge's endpoints have different colors.
• The vertices have a total weight of at most $X$.

Find the maximum possible total beauty of the vertices in a good rooted tree.

Find all of $F(1), F(2), \dots, F(N)$.

Constraints

• $2 \leq N \leq 200$
• $0 \leq X \leq 50000$
• $1 \leq P_i \leq i - 1$
• $0 \leq B_i \leq 10^{15}$
• $0 \leq W_i \leq X$
• $C_i$ is $0$ or $1$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N X
P_2 P_3 \dots P_N
B_1 W_1 C_1
B_2 W_2 C_2
\vdots
B_N W_N C_N

Output

Print $N$ lines. The $i$-th line should contain $F(i)$.