LibreOJinit(n, maxdep, maxcnt)
- 该函数只会在初始调用一次，你可以在此时进行初始化的操作。
- join(x, y, &id1, &id2)
- 表示 Scape 要求你把二叉树 $x$ 和二叉树 $y$ 连接成一棵新的二叉树。设此时存在的二叉树最大的编号为 $\mathrm{tot}$，那么新的二叉树编号为 $\mathrm{tot}+1$。事件结束后不存在编号为 $x$ 和 $y$ 的二叉树，并且也不能再指挥给它们分配的手下。
- 连接两棵二叉树后，需要决定给二叉树 $\mathrm{tot}+1$ 分配的两个手下的位置，只能从分配给二叉树 $x,y$ 的 $4$ 个手下当前所处的位置中选择。二叉树 $\mathrm{id}+1$ 的 $1$ 号手下位于手下 $\mathrm{id}_1$ 的位置，$2$ 号手下位于手下 $\mathrm{id}_2$ 的位置。请对 $\mathrm{id}_1, \mathrm{id}_2$ 分别赋值，值为 $1,2$ 分别表示是二叉树 $x$ 的 $1,2$ 号手下；值为 $3,4$ 分别表示是二叉树 $y$ 的 $1,2$ 号手下。
- split(x, k, &p1, &p2, &p3, &p4)
- 表示 Scape 要求你把二叉树 $x$ 分离成两棵新的二叉树。设此时存在的二叉树最大的编号为 $\mathrm{tot}$，那么新的二叉树编号为 $\mathrm{tot}+1$ 和 $\mathrm{tot}+2$。二叉树 $x$ 中序遍历的前 $k$ 个结点会构成二叉树 $\mathrm{tot}+1$，剩余的结点会构成二叉树 $\mathrm{tot}+2$。事件结束后不存在编号为 $x$ 的二叉树，并且也不能再指挥给它分配的手下。
- 你需要对 $p_1,p_2,p_3,p_4$ 赋值来指定给两棵新的二叉树分配的手下的位置。$p_1, p_2$ 分别表示二叉树 $\mathrm{tot}+1$ 上的 $1,2$ 号手下所处的结点编号；$p_3, p_4$ 分别表示二叉树 $\mathrm{tot}+2$ 上的 $1,2$ 号手下所处的结点编号。
- 保证 $1\leq k\lt size(x)$。
- `visit(x)`
- 表示 Mythological 打算观赏二叉树 $x$。你需要按 Scape 的要求调整这棵树的形态，并且返回调整过后这棵树的根结点的编号。
你可以调用 `move()` 来指挥你的手下，但是该函数的总调用次数不能超过 $2 \times 10^6$ 次，并且在每次事件中（即交互库调用 `join()/split()/visit()` 函数到该函数结束的这段时间内）`move()` 函数的调用次数不能超过 $\mathrm{maxcnt}$ 。
- `move(k, id, x, c, y)`
- 把分配给二叉树 $k$ 的 $\mathrm{id}$ 号手下（$\mathrm{id}$ 为 $1$ 或 $2$）移动到结点 $x$。结点 $x$ 要么是该手下原来所处位置（即不移动），要么是其相邻结点。
- 之后手下会把该结点的儿子 $c$（$c=0$ 表示左儿子，$c=1$ 表示右儿子）改为结点 $y$（$y=0$ 表示空结点），然后给该结点浇水。
- 如果不希望修改 $x$ 的两个儿子，请把 $c$ 和 $y$ 设置为 $-1$，这样不会导致 $x$ 的祖先结点变为枯萎状态。
### 实现细节
你只能提交一个源文件实现上述的函数，并且遵循下面的命名和接口。源代码中需要包含头文件 `tree.h`。
```cpp
void init(int n, int maxdep, int maxcnt);
void join(int x, int y, int &id1, int &id2);
void split(int x, int k, int &p1, int &p2, int &p3, int &p4);
int visit(int x);
void move(int k, int id, int x, int c, int y);
```
下发文件中附有样例程序。
### 评测方式
交互库将读入如下格式的输入数据：
第一行为四个整数 $n,m,\mathrm{maxdep},\mathrm{maxcnt}$，$m$ 表示事件的个数。读入此行后交互库会调用一次 `init()` 函数。
接下来 $m$ 行，每行描述一次事件。若为事件 join，输入三个整数 `1 x y`；若为事件 split，输入三个整数 `2 x k`；若为事件 visit，输入两个整数 `3 x`。读入每行后交互库会调用对应的函数。
交互库会在每次调用 `visit()` 函数后进行某些输出，如果输出与数据的输出文件一致且 `move()` 函数的调用次数未超过上限，则视为通过该测试点。如果你在调用 `move()` 函数时传入了非法的参数或者返回值不合法，交互库会马上退出。
通过访问输入输出文件、攻击评测系统或攻击评测库等方式所得分数无效。
### 其他语言
C++ 以外的语言可以通过标准输入输出进行交互。
程序开始时，从标准输入读入一行，包含三个空格分隔的正整数 $n, \mathrm{maxdep}, \mathrm{maxcnt}$。
此后，从输入不断读入格式如下的信息：
- `J 请注意最终测评使用的 tree.h 与下发的文件并不一致。
由于交互量较大，时限放宽至标程在 LOJ 上运行耗时的两倍。