#385 Binary Tree Queries

Statement

Statement language

You are given a tree $T$ with $N$ vertices numbered from $1$ to $N$ . Every vertex is colored either black or white.

$T$ is a binary tree. Initially, the root of $T$ is vertex $1$ .

Process the following queries.

1 $i$ : Change the root of $T$ to vertex $i$ .
2 $i$ : Toggle the color of vertex $i$ . White becomes black, and black becomes white.
3 $i$ : Let be the number of white vertices in the subtree rooted at vertex with respect to the current root. Let be the number of white vertices on the path from vertex to the current root. Both endpoints belong to the path. Print .

It is guaranteed that $T$ is a binary tree regardless of which vertex is chosen as the root.

Input

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For every type 3 query, print the answer on its own line.

Constraints

$1 \le T \le 100$ .
$1 \le N \le 100\,000$ .
$1 \le Q \le 100\,000$ .

Subtasks

#	Score	Constraints
1	26	Every case satisfies $N \le 200$ and $Q \le 200$ .
2	31	In every case, the edges are $(1, 2), (2, 3), \dots, (N - 1, N$ .

Samples

Input

Output

In the third type 3 query of the first case, vertices $1,2,3$ belong to the subtree, while vertices $3,4,5$ belong to the path to the root. The two white-vertex counts are $3$ and $2$ , so the answer is .