8. Binary Tree Traversal
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

A binary tree is a set of nodes, each of which can have a left child and a right child. The root node is not a child of any other node. By starting at the root node and moving to one of the children each time, it is possible to reach any node. A subtree of a node is a set of nodes that can be reached from it.

There are three common binary tree traversals: pre-order, in-order and post-order traversals.

A pre-order traversal order is an order in which nodes are visited by the following recursive procedure:

  1. Begin at the root node.
  2. If the root node has a left child, traverse its subtree recursively.
  3. If the root node has a right child, traverse its subtree recursively.

An in-order traversal visits the root node between traversals of its left and right subtrees, a post-order traversal visits the root node after traversals of its left and right subtrees.

These traversals can be combined as follows: let us assign a number $$$-1$$$, $$$0$$$ or $$$1$$$ to each node. Each number denotes at which moment the node is visited:

  • $$$x = -1$$$: before traversing of its left and right subtrees;
  • $$$x = 0$$$: between the traversal of its left and right subtrees;
  • $$$x = 1$$$: after traversing of its left and right subtrees.

If each node is assigned $$$-1$$$, this is a pre-order traversal, $$$0$$$ — an in-order traversal, $$$1$$$ — a post-order traversal.

You are given a binary tree consisting of $$$n$$$ nodes numbered with integers from $$$1$$$ to $$$n$$$. The root is the node number $$$1$$$. Initially each node is assigned $$$-1$$$.

You have to process $$$q$$$ queries of two different types:

  1. Assign $$$x$$$ to the nodes $$$l, l+1, \dots, r$$$.
  2. Find the position of node $$$i$$$ in the current traversal order.

For each query of the second type, output the answer to it.

Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 100\,000$$$).

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$L_i$$$ and $$$R_i$$$ ($$$0 \le L_i, R_i \le n$$$) — numbers of the left and right child of node $$$i$$$. If $$$L_i = 0$$$, node $$$i$$$ does not have a left child. If $$$R_i = 0$$$, node $$$i$$$ does not have a right child.

It is guaranteed that $$$L_i$$$ and $$$R_i$$$ describe a valid binary tree.

The $$$i$$$-th of the next $$$q$$$ lines describes the $$$i$$$-th query. The line starts with an integer $$$t$$$ ($$$t \in \{1, 2\}$$$) — type of the query.

In the query of the first type, the rest of the line contains three integers $$$l$$$, $$$r$$$ and $$$x$$$ ($$$1 \le l \le r \le n$$$, $$$x$$$ equals $$$-1$$$, $$$0$$$ or $$$1$$$) — boundaries of the segment of nodes and the number assigned to them.

In the query of the second type, the rest of the line contains an integer $$$i$$$ ($$$1 \le i \le n$$$) — number of the node, the position of which you have to find.

For each query of the second type, output the position of node $$$i$$$ in the current traversal order.

Output

For each query of the second type, output the position of node $$$i$$$ in the current traversal order.

Scoring

TBD

Example
Input
5 5
3 4
0 0
5 2
0 0
0 0
2 2
1 1 3 1
2 5
1 3 3 0
2 3
Output
4
1
2
Note

In the first example, the traversal order changes as follows:

  • $$$[1, 3, 5, 2, 4]$$$
  • $$$[5, 2, 3, 4, 1]$$$
  • $$$[5, 3, 2, 4, 1]$$$