This is an interactive problem.

Scape has many binary trees in his backyard. Each node in these trees has at most one parent, one left child, and one right child. As his gardener, you need to help him maintain these binary trees.

Nodes can be in one of two states: normal or withered. There are $n$ nodes in total, labeled $1$ to $n$. Initially, there are $n$ binary trees, labeled $1$ to $n$, where tree $i$ consists only of node $i$, and all nodes are in the normal state.

The following three types of events may occur:

• Scape asks you to join binary tree $x$ and binary tree $y$ into a new binary tree. If the inorder traversal of tree $x$ is $a_1, a_2, \dots, a_n$ and the inorder traversal of tree $y$ is $b_1, b_2, \dots, b_m$, the inorder traversal of the new binary tree should be $a_1, a_2, \dots, a_n, b_1, b_2, \dots, b_m$.
• Scape asks you to split binary tree $x$ into two new binary trees. If the inorder traversal of tree $x$ is $a_1, a_2, \dots, a_n$, the inorder traversals of the two new binary trees should be $a_1, a_2, \dots, a_k$ and $a_{k+1}, a_{k+2}, \dots, a_n$, respectively.
• Mythological intends to view binary tree $x$. To make the tree more aesthetically pleasing, Scape requires you to ensure that all nodes in the tree are in the normal state, and the depth of every node does not exceed $\mathrm{maxdep}$. The depth of a node is defined as the number of its ancestors plus $1$, with the root having a depth of $1$.

To adjust these trees, you are assigned two subordinates for each tree, referred to as subordinate $1$ and subordinate $2$. Initially, they both stand on the only node of their assigned tree. In each step, you can move a subordinate to an adjacent node. At this point, you can command them to modify one of the node's children to a specific node (the original child's subtree will be detached; the new child's parent will also be updated to the current node). Due to a mysterious force, after modifying a node's child, all ancestor nodes of that node (including itself) will become withered. Finally, the subordinate will water the node; if all children of this node (ignoring empty children) are in the normal state at this time, the node will become normal.

Brief Problem Summary: You are required to maintain several sequences using binary trees. The interactor provides two pointers for each tree, each pointing to a node in the tree. You are allowed to modify the children of the node pointed to by a pointer, update the subtree information of the node pointed to by a pointer, and move a pointer to an adjacent node. You must perform join, split, and query operations using these pointers.

Task Introduction

You need to implement the following four functions:

• init(n, maxdep, maxcnt)
  • This function is called only once at the beginning. You can perform initialization here.
• join(x, y, &id1, &id2)
  • Scape asks you to join binary tree $x$ and binary tree $y$ into a new binary tree. Let $\mathrm{tot}$ be the maximum index of existing binary trees; the new binary tree will have index $\mathrm{tot}+1$. After the event, binary trees $x$ and $y$ no longer exist, and you can no longer command the subordinates assigned to them.
  • After joining the two trees, you must decide the positions of the two subordinates assigned to tree $\mathrm{tot}+1$. You can only choose from the current positions of the $4$ subordinates assigned to trees $x$ and $y$. Subordinate $1$ of tree $\mathrm{id}+1$ will be located at the position of subordinate $\mathrm{id}_1$, and subordinate $2$ will be at the position of subordinate $\mathrm{id}_2$. Assign values to $\mathrm{id}_1$ and $\mathrm{id}_2$, where $1, 2$ represent subordinates $1$ and $2$ of tree $x$, and $3, 4$ represent subordinates $1$ and $2$ of tree $y$.
• split(x, k, &p1, &p2, &p3, &p4)
  • Scape asks you to split binary tree $x$ into two new binary trees. Let $\mathrm{tot}$ be the maximum index of existing binary trees; the new binary trees will have indices $\mathrm{tot}+1$ and $\mathrm{tot}+2$. The first $k$ nodes of the inorder traversal of tree $x$ will form tree $\mathrm{tot}+1$, and the remaining nodes will form tree $\mathrm{tot}+2$. After the event, binary tree $x$ no longer exists, and you can no longer command the subordinates assigned to it.
  • You need to assign values to $p_1, p_2, p_3, p_4$ to specify the node indices where the subordinates for the two new trees are located. $p_1, p_2$ are the node indices for subordinates $1$ and $2$ of tree $\mathrm{tot}+1$, and $p_3, p_4$ are the node indices for subordinates $1$ and $2$ of tree $\mathrm{tot}+2$.
  • It is guaranteed that $1 \leq k < size(x)$.
• visit(x)
  • Mythological intends to view binary tree $x$. You need to adjust the shape of this tree according to Scape's requirements and return the index of the root node of the adjusted tree.

You can call move() to command your subordinates, but the total number of calls to this function cannot exceed $2 \times 10^6$, and for each event (the duration from when the interactor calls join()/split()/visit() until the function returns), the number of calls to move() cannot exceed $\mathrm{maxcnt}$.

• move(k, id, x, c, y)
  • Move subordinate $\mathrm{id}$ ($\mathrm{id}$ is $1$ or $2$) assigned to tree $k$ to node $x$. Node $x$ must be either the current position of the subordinate (no movement) or an adjacent node.
  • Afterward, the subordinate will change child $c$ of node $x$ ($c=0$ for left child, $c=1$ for right child) to node $y$ ($y=0$ for an empty node), and then water the node.
  • If you do not wish to modify the two children of $x$, set $c$ and $y$ to $-1$; this will not cause the ancestors of $x$ to become withered.

Implementation Details

You must submit a single source file implementing the functions above, following the naming and interface conventions below. The source code must include the header file tree.h.

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);

A sample program is provided in the distributed files.

Evaluation

The interactor will read input data in the following format:

The first line contains four integers $n, m, \mathrm{maxdep}, \mathrm{maxcnt}$, where $m$ is the number of events. After reading this line, the interactor will call the init() function once.

The next $m$ lines each describe an event. For a join event, input three integers 1 x y; for a split event, input three integers 2 x k; for a visit event, input two integers 3 x. After reading each line, the interactor will call the corresponding function.

The interactor will perform certain outputs after each call to visit(). If the output matches the expected output file and the number of calls to move() does not exceed the limit, the test case is passed. If you pass invalid parameters to move() or return an invalid value, the interactor will terminate immediately.

Scores obtained by accessing input/output files, attacking the evaluation system, or attacking the evaluation library are invalid.

Subtasks

• Subtask 1 (15 points): $1 \leq n, m \leq 1000$, $\mathrm{maxdep} = 2 \times 10^5$, $\mathrm{maxcnt} = 2 \times 10^6$.
• Subtask 2 (25 points): $1 \leq n, m \leq 30000$, $\mathrm{maxdep} = 2 \times 10^5$, $\mathrm{maxcnt} = 2 \times 10^6$.
• Subtask 3 (15 points): $1 \leq n, m \leq 10^5$, total number of split and visit events does not exceed $10000$, $\mathrm{maxdep} = 2 \times 10^5$, $\mathrm{maxcnt} = 2 \times 10^6$.
• Subtask 4 (15 points): $1 \leq n, m \leq 2 \times 10^5$, no split events, number of visit events does not exceed $20000$, $\mathrm{maxdep} = 60$, $\mathrm{maxcnt} = 250$.
• Subtask 5 (30 points): $1 \leq n, m \leq 2 \times 10^5$, total number of split and visit events does not exceed $20000$, $\mathrm{maxdep} = 60$, $\mathrm{maxcnt} = 250$.

Please note that the tree.h used for final evaluation is different from the one provided in the distributed files.