This is an interactive problem.

You need to perform $n$ primitive operations to maintain a sequence. The sequence is initially empty.

The $i$-th primitive operation provides integers $x_i, l_i, r_i$, which means inserting element $i$ at the $x_i$-th position in the sequence (if $x_i = i$, it means inserting at the end of the sequence), and then querying the set of elements from the $l_i$-th to the $r_i$-th position in the sequence.

To answer these queries, you can manipulate several sets. These sets are initially empty and are indexed by integers from $1$ to $2 \times 10^7$.

You can spend $1$ unit of the first type of cost to perform an insertion operation: insert element $y$ into the set with index $x$. Before answering the query for the $i$-th primitive operation, you must ensure $1 \le y \le i$.

You can spend $k$ units of the second type of cost to answer a query: select sets with indices $a_1, a_2, \dots, a_k$, such that these sets are pairwise disjoint and their union is the answer to the query.

After each primitive operation, the costs of the insertion operations and the query response (first type and second type respectively) must not exceed the cost limits $m_1, m_2$ for the current subtask. The costs for each primitive operation are calculated independently.

Implementation Details

You need to implement the following function:

void solve(int x,int l,int r);

This function is called once for each primitive operation, with parameters x l r corresponding to $x_i, l_i, r_i$.

You can call the following functions:

void op1(int x,int y);
void op2(int k);

Calling op1 performs one insertion operation.

Calling op2 with $a_1, \dots, a_k$ (passed sequentially) answers the query.

You must declare these two functions in your submitted code.

Examples

Suppose the interactor calls the solve function 3 times as follows:

solve(1,1,1);
solve(1,2,2);
solve(2,1,3);

The following is a valid sequence of calls to op1 and op2:

op1(1,1);
op2(1);

At this point, the sequence is $(1)$, the set with index 1 is $\{1\}$, and the first solve function call returns.

op2(1);

At this point, the sequence is $(2,1)$, the set with index 1 is $\{1\}$, and the second solve function call returns.

op1(1,2);
op1(2,3);
op2(2);
op2(1);

At this point, the sequence is $(2,3,1)$, the set with index 1 is $\{1,2\}$, the set with index 2 is $\{3\}$, and the third solve function call returns.

Subtasks

Idea: ccz181078, Solution: ccz181078, Code: ccz181078, Data: ccz181078 & nzhtl1477

For $100\%$ of the data, $1 \le n \le 10^6$; $1 \le x_i \le i$; $1 \le l_i \le r_i \le i$.

In your output insertion operations or query responses, the set indices must be in the range $1$ to $2 \times 10^7$, and the $y$ in the insertion operation must be an element already present in the sequence.

• Subtask 1 (10 points): $1 \le n \le 10^3$.
• Subtask 2 (10 points): $l_i = 1, r_i = i$.
• Subtask 3 (10 points): $x_i = i$.
• Subtask 4 (20 points): $1 \le n \le 10^4$.
• Subtask 5 (10 points): $1 \le n \le 10^5$.
• Subtask 6 (20 points): Data is generated randomly, where $n = 10^6$, and $(l_i, r_i)$ and $x_i$ are chosen uniformly at random from all possible cases.
• Subtask 7 (20 points): No special constraints.

For Subtask 6, $(m_1, m_2) = (64, 64)$. For all other subtasks, $(m_1, m_2) = (64, 256)$.