题目背景

有一天亮亮学长在刷题，发现市面上的二叉树三序遍历题太朴素了，于是想了一道并不朴素的朴素的二叉树遍历。

说明

先给你一棵二叉树，然后给你 $m$ 条操作。

每种操作规定如下：
给你一个整数 $u$ 和一个参数 $x$ 要求你输出以 $u$ 号节点为根的子树的参数为 $x$ 的遍历

对于参数 $x$：$1$ 为先序遍历，$2$ 为中序遍历，$3$ 为后续遍历。

输入格式

第一行一个整数 $n$ 表示该二叉树一共有 $n$ 个节点。

接下来 $n$ 行，每行两个整数，第 $i$ 代表第 $i$ 号节点的左右孩子的节点编号，特别的，若编号为 $0$ ，则代表该孩子为空。

然后给一个整数 $m$，代表操作条数。

接下来 $m$ 行，每行两个整数 $u,x$，代表子树头结点编号和操作参数。

输出格式

对于每个操作，按要求输出对应遍历次序,每个操作的输出在一行内，不同操作输出在不同行。

样例

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

1 2 4 5 3
4 5 2

数据范围

$1\le n\le 10^5$
$1\le m\le 10^5$ 定义 $|u|$ 为以 $u$ 号节点为头的子树的节点数量，保证$\sum_{i=1}^{m}|u_i|\le 5\times10^5$