Description

After moving across the 49th parallel to Canada, the land of rocks and trees, Farmer John's cows invented a game to spend their leisure time on the pasture; naturally, it involved the rocks and trees! Cowboy Ted likes this game very much, but so poor is his luck that he always loses to other cows. This time, he is going to seek your help.

The game's rules are simple. It is played with a tree that has both $N$ $(2 \leqslant N \leqslant10000)$ nodes conveniently numbered $1 \cdots N$ and also $N-1$ branches. Node 1 is the root of this tree; except for node 1, node $i$ has parent $P_i$ $(1 \leqslant P_i < i)$. Initially, each node contains some rocks (except the root node, which has no rocks). In particular, non-root node $i$ has exactly $R_i$ $(1 \leqslant R_i \leqslant 1000)$ rocks at the beginning of the game.

Two players alternate turns to play this game, with Ted going first. In each turn, the current player can choose a non-root node $i$ and move at most $L$ $(1 \leqslant L \leqslant 1000)$ rocks from this node one branch closer to the root (i.e., move these rocks to the parent node). He must move at least one rock, and, of course, he cannot exceed the current number of rocks on this node. The game ends when a player can't make a legal move (i.e., when all the rocks are on node 1); that player loses.

Ted needs your help. He has given you the initial configuration of the game, and he will then make $T$ $(1 \leqslant T \leqslant 10000)$ changes to the configuration one by one. Please help him determine, after each step, if he can win the game beginning from this configuration, assuming both he and his opponent use the best possible strategy.

Ted's changes are specified as two integers $A_j$ $(1 < A_j \leqslant N)$ and $B_j$ $(1 \leqslant B_j \leqslant 1000)$, meaning that Ted will change the number of rocks on node $A_j$ to $B_j$ (this is a "set", not a "subtract" or "add"), and will then ask you whether he can win. Changes accumulate; node $A_j$'s rocks stay at $B_j$ until another change for $A_j$ appears.

Consider this example with three nodes numbered as shown and the shape shown in Board 0. Initially, there are 5 rocks on node 2 and 3 rocks on node 3; see Board 1.

For the first change, Ted removes 2 rocks from node 2 (thus leaving 3); see Board 2. For the second change, Ted removes 2 rocks from node 3 (thus leaving 1). Note that node 2 still has 3 rocks; see Board 3.

Board 0 Board 1 Board 2 Board 3

(No link is provided in the original statement.)

Your program should determine in each case who wins.

For about 30% of the test cases, $N \leqslant 10$, and $T \leqslant 100$, and no tree node will have more than 5 rocks on it after any of Ted's changes.

Partial feedback will be provided for your first $50$ submissions.

Input Format

Line $1$: Three space-separated integers: $N$, $T$, and $L$.
Lines $2 \cdots N$: Line $i$ contains two space-separated integers: $P_i$ and $R_i$.
Lines $N+1 \cdots N+T$: Line $j+N$ describes Ted's next change using two space-separated integers: $A_j$ and $B_j$.

Output Format

Lines $1 \cdots T$: Line $i$ contains "Yes" if Ted can win the game after change $i$, and "No" otherwise.

3 2 10 
1 5 
1 3 
2 3 
3 1 

No 
Yes 

Hint

Testdata source: bzoj.

Translated by ChatGPT 5