Rocks on a Tree Game

Farmer John’s cows have invented a game played on a rooted tree. The tree has N nodes (numbered 1 through N) and N−1 branches; node 1 is the root. For every node i (2 ≤ i ≤ N), its parent is given by P_i with 1 ≤ P_i < i. Initially every non‐root node i contains R_i rocks (1 ≤ R_i ≤ 1000), while the root has no rocks.

The game is played by two players who alternate moves – Ted goes first. In every turn the current player must choose a non‐root node i that has at least one rock and move some rocks (at least 1 and at most L, where 1 ≤ L ≤ 1000 and not more than the current number of rocks on node i) from node i to its parent P_i. (In other words, the chosen rocks move one branch closer to the root.) The game ends when no legal move remains (i.e. when all the rocks have reached the root) and the player unable to move loses.

Ted will modify the initial configuration by performing T changes (1 ≤ T ≤ 10000). Each change is described by two integers A_j (with 1 < A_j ≤ N) and B_j (1 ≤ B_j ≤ 1000) meaning that the number of rocks on node A_j is set to B_j (changes accumulate). After each change, Ted asks you to determine whether he can force a win assuming both players play optimally.

Game Analysis (in LaTeX):

One may show that if we define the subtree sum for each non‐root node \(u\) as \[ S_u = \sum_{v \in \text{{subtree}}(u)} R_v, \] then the game is equivalent to a collection of subtraction games on each edge. In the move from node \(u\) to its parent, the number of moves performed is \(\lceil S_u / L \rceil\) if played in a minimal way; however, since a player may choose to move any number (between 1 and L, but not more than the number of rocks in that node) the overall position has a nim–value given by \[ G(u)=S_u\ \bmod\ (L+1). \] Thus the overall game is equivalent to the disjunctive sum with nim–value \[ G=\bigoplus_{u=2}^{N} \Bigl(S_u\ \bmod\ (L+1)\Bigr). \] Ted can force a win if and only if \(G\neq 0\).

Your task is to process the initial configuration and then T updates. After each update, output 1 if Ted can force a win and 0 otherwise.

inputFormat

The first line contains three integers: N, L and T.

The second line contains N−1 integers: P₂, P₃, …, P_N.

The third line contains N−1 integers: R₂, R₃, …, R_N (the initial number of rocks on nodes 2 to N; node 1 has 0 rocks).

Then follow T lines, each containing two integers A_j and B_j, representing that the number of rocks on node A_j is set to B_j.

outputFormat

For each update, output a line containing a single integer: 1 if Ted (the first player) can force a win from the current configuration, or 0 otherwise.

sample

3 2 2
1 1
5 3
2 3
3 1

0
1