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)$.

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$
```

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

-   $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.

9
10
6
7

For v=1, choosing c=2 and then c=3 changes U as shown in the figure, making it a good rooted tree. The total beauty of the vertices in this tree is 2+7=9, which is the maximum among all good rooted trees, so F(1)=9.

For v=2, choosing c=4 changes U as shown in the figure, making it a good rooted tree. The total beauty of the vertices in this tree is 4+6=10, which is the maximum among all good rooted trees, so F(2)=10.