题目描述

译自 ROI Regional 2024 Day2 T4. Обходы бинарного дерева

二叉树是一组顶点，每个顶点可以有左孩子和右孩子。其中一个顶点是树的根，它不是任何其他顶点的孩子。从根开始，每次移动到一个孩子，可以到达任何顶点。可以从给定顶点到达的所有顶点的集合称为其子树。

二叉树有三种主要遍历方式：前序遍历（pre-order）、中序遍历（in-order）和后序遍历（post-order）。

前序遍历的顺序是通过以下递归算法获得的：

1. 将树的根添加到遍历序列中。
2. 如果根有左孩子，记录其子树的前序遍历。
3. 如果根有右孩子，记录其子树的前序遍历。

在中序遍历中，根在其孩子子树的遍历之间被记录，而在后序遍历中，根在其孩子子树的遍历之后被记录。

我们可以将这三种遍历方式进行概括：在每个顶点记录一个从 $-1$ 到 $1$ 的整数 $x$，表示我们在何时记录这个顶点：

• $x = -1$：在遍历其孩子子树之前；
• $x = 0$：在遍历其孩子子树之间；
• $x = 1$：在遍历其孩子子树之后。

因此，如果所有顶点记录的是 $-1$，则遍历是前序遍历；如果是 $0$，则是中序遍历；如果是 $1$，则是后序遍历。

考虑一个有 $n$ 个顶点的树，顶点编号从 $1$ 到 $n$。树的根是顶点 $1$。最初，所有顶点记录的数字都是 $-1$。

在研究中，需要处理 $q$ 个以下类型的查询：

1. 将顶点 $l, l+1, \dots, r$ 的数字更改为 $x$（$x$ 可以是 $-1$、$0$ 或 $1$）。
2. 报告在当前遍历中顶点 $i$ 的位置。

需要输出所有第二种类型查询的答案。

输入格式

第一行输入包含两个整数 $n$ 和 $q$ $(1 \le n, q \le 10^5)$。

接下来的 $n$ 行中，每行包含两个整数 $L_i$ 和 $R_i$ $(0 \le L_i, R_i \le n)$，分别表示顶点 $i$ 的左孩子和右孩子的编号，如果没有对应的孩子则为 $0$。

保证 $L_i$ 和 $R_i$ 构成一个有效的二叉树。

接下来的 $q$ 行中，每行表示一个查询。第一位是整数 $t$ $(t \in \{1, 2\})$，表示查询的类型。

如果是第一种类型的查询，接下来是三个整数 $l, r$ 和 $x$（$1 \le l \le r \le n$, $x$ 可以是 $-1$、$0$ 或 $1$），表示更改顶点范围和新值。

如果是第二种类型的查询，接下来是一个整数 $i$ $(1 \le i \le n)$，表示需要输出顶点 $i$ 在遍历中的位置。

输出格式

对于每个第二种类型的查询，输出一个从 $1$ 到 $n$ 的整数，表示对应顶点在遍历中的位置。

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

4
1
2

在样例中，遍历顺序如下变化：

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

数据范围与提示

详细子任务附加限制及分值如下表所示。