Dynamic Tree Queries with XOR Input Modification

You are given a rooted tree with n nodes (node 1 is the root) and each node i has an integer weight w_i. Initially, the tree is assumed to be a star: the root 1 is connected to every other node (i.e. for i=2,…,n, the parent of node i is 1).

The tree may evolve into a forest after performing certain operations. The following operations are supported:

• 0 u x: Query the subtree with root u and count the number of nodes in that subtree whose weight is strictly greater than x. Print the answer. (After each query, update the special value last to the answer.)
• 1 u x: Update: change the weight of node u to x.
• 2 u x: Insertion: add a new node with id (current number of nodes + 1). Its parent is u and its weight is x.
• 3 u: Deletion: remove the edge between node u and its parent, making u the root of its connected component.

Important: All the values for u and x provided in the input must be XORed with the variable last to obtain the actual parameters. Initially, last is 0. Note that only query operations (of type 0) produce an output and update last; the other operations do not affect last.

This is an online problem, i.e. the parameters of each operation depend on the answer of the previous query.

inputFormat

The first line contains two integers n and q separated by a space.

The second line contains n integers w₁, w₂, …, w_n representing the weights of the initial tree nodes. The tree is initially assumed to be a star with node 1 as the root and for every i = 2,…,n, the parent of node i is 1.

The next q lines each represent an operation in one of the following formats:

• 0 u x
• 1 u x
• 2 u x
• 3 u

For every operation, the provided values for u and x (if present) must be XORed with last (initially 0) to obtain the true parameters.

outputFormat

For each operation of type 0, output the answer (the count of nodes in the subtree with weight strictly greater than x) on a new line.

sample

3 4
1 2 3
1 2 5
2 1 7
3 2
0 1 2

1