N. Ziftawi's Tree
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Yaman and Ziftawi were good friends who shared a love for nature, Ziftawi had a magnificent tree in his backyard, a connected graph with no cycles and a value assigned to each node. The tree was a symbol of their friendship, bringing them joy and tranquility.

One day, Yaman, driven by curiosity, decided to play a mischievous prank on Ziftawi. He secretly stole the entire tree, leaving behind only the root node with the number $$$1$$$ which has the value of $$$x$$$. Yaman regrets his actions and is determined to fix his mistake by restoring the tree with your help.

You will be given $$$q$$$ queries of three types:

  • $$$1$$$ $$$u$$$ $$$y$$$ $$$-$$$ Assuming the tree initially has $$$n$$$ nodes, you should add a node with the number $$$n + 1$$$ and a value of $$$y$$$ as a child of node $$$u$$$.

    For example: if the tree initially has $$$10$$$ nodes, and the children of node $$$1$$$ are $$$[2, 3, 5]$$$, when you add a new node as a child of the node $$$1$$$, its children will be: $$$[2, 3, 5, 11]$$$

  • $$$2$$$ $$$l$$$ $$$r$$$ $$$-$$$ Consider an array $$$b$$$ that represents the DFS ORDER of the current tree starting from node $$$1$$$, you need to reverse the values of the nodes appearing in the array $$$b$$$ from index $$$l$$$ to index $$$r$$$.
  • $$$3$$$ $$$u$$$ $$$-$$$ Print the value of the node $$$u$$$.

A DFS ORDER is an array $$$b$$$ that represents the ordering of the nodes in a rooted tree, constructed by recursively calling a DFS procedure starting from the root. When called on a given node $$$v$$$, the procedure does the following:

  1. Append $$$v$$$ to array $$$b$$$.
  2. Traverse the sorted list of node $$$v$$$ children and recursively calls DFS-procedure on each child, except for node $$$u$$$ if $$$v$$$ was reached directly from $$$u$$$.
Input

The first line contains two integers $$$x, q$$$ $$$(1 \le x, q \le 10^5)$$$, the value of the node number $$$1$$$, and the number of queries.

The next $$$q$$$ lines contain the queries as follows:

If the $$$i$$$-th query type is $$$1$$$ then it will be followed by two numbers $$$u$$$, $$$y$$$ $$$(1 \le u, y \le 10^5)$$$, the parent node, the value of the child node (It is guaranteed that the node $$$u$$$ has been added to the tree)

If the $$$i$$$-th query type is $$$2$$$ then it will be followed by two numbers $$$l$$$, $$$r$$$ $$$(1 \le l \le r \le 10^5)$$$, the boundaries of the range that we want to reverse its values (It is guaranteed that $$$l, r$$$ is less than or equal to the number of nodes in the current tree)

If the $$$i$$$-th query type is $$$3$$$ then it will be followed by one number $$$u$$$ $$$(1 \le u \le 10^5)$$$, the number of the node that you have to print its value (It is guaranteed that the node $$$u$$$ has been added to the tree)

Output

For each query of type $$$3$$$ print the value of the node $$$u$$$ in that query.

Example
Input
5 8
1 1 6
1 1 7
1 3 8
2 1 4
3 1
3 2
3 3
3 4
Output
8
7
6
5