Tree Lamp Toggles and Time Travel Queries

We are given a tree with (n) nodes, rooted at node 1. Each node has a lamp that is initially turned off. The tree structure is given by a list of (n-1) parent indices for nodes 2 through (n). Then, there are (m) events. Each event is one of the following types:

• 1 x: Toggle the lamp at node \(x\) (if it is on, turn it off; if it is off, turn it on).
• 2 x y: Query the current state. Consider node \(x\) (with depth \(d\)). Among all nodes in the tree that have the same depth as \(x\), count the number of nodes whose distance from \(x\) is exactly \(y\) and have the lamp turned on. The distance between two nodes is the number of edges in the unique path connecting them. (Note that if \(y\) is odd, no two nodes of the same depth can have an odd distance; in that case, the answer is 0.) For \(y=0\), the answer is 1 if the lamp at \(x\) is on, and 0 otherwise.
• 3 x: Roll back the state to the state immediately after the \(x\)th event. (The initial state before any event is considered event 0.)

It can be shown that for any query of type 2 (with (y) even and (y \ge 2)), if (k = y/2) and if (\text{anc}) is the (k)th ancestor of (x) (provided it exists), then any node (u) (with depth (d)) satisfying the condition must lie in the subtree of (\text{anc}) but not in the subtree of the unique child of (\text{anc}) that lies on the path to (x).

Input Note: Use the precomputed Euler Tour of the tree and binary lifting (or simply parent pointers for small (n)) to answer the queries efficiently. A node (u) is considered to be in the subtree of node (v) if its Euler Tour time (in[u]) satisfies (in[v] \leq in[u] \leq out[v]).

Your task is to process all events in order and answer each query of type 2.

inputFormat

The input begins with a line containing two integers (n) and (m) ( (1 \le n, m \le 2000)), where (n) is the number of nodes, and (m) is the number of events. The next line contains (n-1) integers: (p_2, p_3, \dots, p_n), where (p_i) denotes the parent of node (i) (for (2 \le i \le n)).

Then follow (m) lines, each representing an event in one of the formats:

• 1 x: Toggle the lamp at node \(x\).
• 2 x y: Query as described above.
• 3 x: Roll back to the state after the \(x\)th event.\newline (Note: The initial state is event 0.)

outputFormat

For each query of type 2, output one line containing the answer (i.e. the count of nodes satisfying the condition in the current state).

sample

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

1
0
0
0