Dynamic Tree Queries with XOR Decoding

You are given a rooted tree with n nodes numbered from 1 to n (with node 1 as the root). Each node i has an integer weight \(w_i\). The tree is dynamic and supports the following operations:

• \(0\ u\ x\): Query the subtree of node \(u\) and count how many nodes have a weight strictly greater than \(x\).
• \(1\ u\ x\): Update the weight of node \(u\) to \(x\).
• \(2\ u\ x\): Insert a new node with index equal to (current number of nodes + 1) as a child of node \(u\) and assign it the weight \(x\).

Important: This is an online problem. All input values for \(u\) and \(x\) are provided in an encoded form. For every operation, the actual parameters are decoded using the bitwise XOR with a variable \(last\) (i.e. the true value is \(u = u' \oplus last\) and \(x = x' \oplus last\)). Initially, \(last = 0\) and it is updated to the answer of the most recent query operation (operation type 0).

inputFormat

The input begins with a line containing two integers \(n\) and \(q\) (\(1 \leq n, q \leq \) limits), representing the number of nodes in the initial tree and the number of operations, respectively.

The second line contains \(n\) integers \(w_1, w_2, \dots, w_n\) where \(w_i\) is the weight of the \(i\)-th node.

The next \(n-1\) lines each contain one integer. The \(i\)-th of these lines (for \(2 \leq i \leq n\)) contains the parent of node \(i\).

Each of the following \(q\) lines represents an operation in the format:

op u x

Here, op is 0, 1, or 2. For each operation, the provided values for \(u\) and \(x\) are encoded as \(u' = u \oplus last\) and \(x' = x \oplus last\), where \(last\) is initially 0 and updated to the answer of the last query (operation 0).

outputFormat

For each query (operation 0), output the answer on a separate line. No output is required for update (operation 1) or insertion (operation 2) operations.

sample

3 6
5 3 7
1
1
0 1 4
1 0 8
0 3 4
2 0 7
0 0 7
0 0 11

2
2
1
0