Stone Game on a Dynamic Tree

This problem is a variant of the classic stone game played on a tree. You are given a rooted tree where each node contains a certain number of stones. Two players play alternately. In each move, the current player selects one non‐root node in the current game tree (which is a subtree of the whole tree with a specified root) and moves between 1 and m stones from that node to its parent. Once a stone reaches the game root, it cannot be moved further.

Initially, you are given a tree consisting of n nodes. Then, there will be q operations. In addition to queries about the game state, new nodes might be added to the tree and the number of stones at a node might change.

For a query on a node u, consider the subtree rooted at u (where u is taken as the game root, and its stones are inert, i.e. they do not count because they cannot be moved). For all other nodes in this subtree, let S be the sum of stones. The game is equivalent to a single‐pile take-away game in which at each turn a player can remove from 1 up to m stones from the pile. (In such a subtraction game, the first player has a winning strategy if and only if S mod (m+1) ≠ 0.)

Your task is to process the operations online. When a query operation is given, determine whether the first player can force a win if the game were played on the current subtree with the given node as its root. Output 1 if the first player wins and 2 otherwise.

The operations are of three types:

1. Q u: Query the current game state on the subtree rooted at node u. (Remember: Do not count stones at node u itself.)
2. U u x: Update the stone count at node u to x.
3. A p x: Add a new node as a child of node p with stone count x. The new node will be assigned the smallest unused positive integer as its index.

Note: The game is played under the rules of a subtraction game where from a pile of S stones one may remove between 1 and m stones in one move. It is well known that such a game is winning for the first player if and only if S mod (m+1) ≠ 0.

inputFormat

The first line contains three integers n, m and q (n initial nodes, maximum stones per move, and number of operations). The second line contains n integers, where the i-th integer denotes the initial number of stones at node i (node 1 is the root of the initial tree).

Then follow n-1 lines; the i-th of these lines (for 1 ≤ i ≤ n-1) contains a single integer p indicating that node i+1 has parent p.

Then follow q lines, each describing an operation in one of the following formats:

• Q u: Query the subtree rooted at u.
• U u x: Update the stone count at node u to x.
• A p x: Add a new node as a child of node p with stone count x.

All numbers are separated by spaces or newlines.

outputFormat

For each query operation (lines starting with 'Q'), output a single integer on a separate line: output 1 if the first player has a winning strategy, or 2 otherwise.

sample

5 2 6
0 1 2 3 4
1
1
2
2
Q 1
Q 2
U 5 5
Q 2
A 2 1
Q 2

1
1
1
2

</p>