AT_arc226_d.Penta-Queue

This is an interactive problem (in which your program interacts with the judge via input and output).

There are five queues numbered $1$ through $5$. Initially, all queues are empty.

The judge gives you the following two types of queries, $Q$ times each, for a total of $2Q$ times.

• push query: The judge gives you an integer $X$, which is appended to the back of queue $1$. The integers $X$ given in the push queries are all distinct. Then, you may perform the following move operation zero or more times.
  • move operation: Choose integers $i,j$ satisfying $1 \le i,j \le 5$, remove the value at the front of queue $i$, and append it to the back of queue $j$. Here, you cannot choose an empty queue as $i$. It is not required that $i\ne j$.
• pop query: The judge gives this query only when at least one queue is non-empty. You choose an integer $i$ satisfying $1 \le i \le 5$. At this point, queue $i$ must be non-empty, and the value at its front must be the minimum among all the values currently contained in the five queues. Then, the judge removes the value at the front of queue $i$.

You may perform the move operation at most $10^5$ times in total. Create a program that correctly responds to all queries.

这是一个交互式问题（即你的程序通过输入和输出与评测系统进行交互）。

有编号为 $1$ 至 $5$ 的五个队列。初始时，所有队列均为空。

评测系统将向你依次给出以下两类查询，每类各 $Q$ 次，共 $2Q$ 次：

• 入队查询（push query）：评测系统给你一个整数 $X$，你需要将该整数追加到队列 $1$ 的尾部。所有入队查询中给出的整数 $X$ 互不相同。随后，你可以执行零次或多次如下移动操作（move operation）：
  • 移动操作：选择满足 $1 \le i,j \le 5$ 的整数 $i,j$，从队列 $i$ 的头部移除一个值，并将其追加到队列 $j$ 的尾部。注意：不能选择空队列为 $i$；不要求 $i\ne j$。
• 出队查询（pop query）：评测系统仅在至少有一个队列非空时给出该查询。你需要选择一个满足 $1 \le i \le 5$ 的整数 $i$，此时队列 $i$ 必须非空，且其头部的值必须是当前五个队列中所有值的最小值。然后，评测系统将移除队列 $i$ 头部的值。

你总共最多可执行 $10^5$ 次移动操作。请编写一个程序，正确响应所有查询。

Interaction

This problem is interactive.

First, the judge gives a positive integer $Q$ in the following format:

$Q$

Then, perform the following interaction $2Q$ times. In each round, the judge first gives a push query or a pop query.

A push query is given in the following format:

$1$ $X$

A pop query is given in the following format:

$2$

(If your response to the previous query was invalid, -1 will be given from Standard Input instead of a query. In this case, immediately terminate your program normally. However, if your first invalid output is your response to the $2Q$-th query, no further input will be given after that.)

If a push query is given, let $k$ be the number of move operations you perform, and let $i_r,j_r$ be the queue numbers chosen in the $r$-th move operation; output $k+1$ lines in the following format. Be sure to add a newline at the end of the output.

$k$
$i_1$ $j_1$
$i_2$ $j_2$
$\vdots$
$i_k$ $j_k$

If a pop query is given, output the number $i$ of the queue from which to remove the front value, in the following format. Be sure to add a newline at the end of the output.

$i$### Notes

• Each time you output a response to a query, flush Standard Output after adding a newline at the end. Otherwise, the judge result may be TLE.
• If you receive -1 as input from the judge, immediately terminate your program normally. If you do so, the judge result will be WA; otherwise, the judge result is indeterminate.
• Extra newlines are regarded as malformed output, so do not output them.
• After you finish responding to the $2Q$ queries, immediately terminate your program. Otherwise, the judge result will be indeterminate.
• The judge for this problem is not adaptive. Before the interaction begins, the judge determines the types and order of the queries, and the integer $X$ given in each push query.

Constraints

• $1 \le Q \le 5000$
• $1 \le X \le 10^9$
• The values $X$ appended in the push queries are all distinct.
• The push query and the pop query are each given $Q$ times.
• At the time each pop query is given, at least one queue is non-empty.
• All input values are integers.

交互方式

本题为交互式问题。

首先，评测系统会以如下格式给出一个正整数 $Q$：

$Q$

随后，你需要进行 $2Q$ 轮交互。每轮中，评测系统首先给出一个“入队查询”（push query）或一个“出队查询”（pop query）。

入队查询的格式如下：

$1$ $X$

出队查询的格式如下：

$2$

（若你对上一查询的响应无效，则标准输入将给出 -1，而非新的查询。此时请立即正常终止你的程序。但若你首次无效输出恰好是对第 $2Q$ 个查询的响应，则此后不会再提供任何输入。）

若收到入队查询，请设你执行了 $k$ 次移动操作，并设第 $r$ 次移动操作中选择的队列编号为 $i_r, j_r$；请按如下格式输出 $k+1$ 行。务必在每行末尾添加换行符。

$k$
$i_1$ $j_1$
$i_2$ $j_2$
$\vdots$
$i_k$ $j_k$

若收到出队查询，请按如下格式输出待移除队首元素的队列编号 $i$。务必在输出末尾添加换行符。

$i$

注意事项

• 每次向查询输出响应后，必须在添加换行符后刷新标准输出。否则评测结果可能为 TLE。
• 若从评测系统接收到输入 -1，请立即正常终止你的程序。若如此操作，评测结果为 WA；否则评测结果不确定。
• 多余的换行符被视为格式错误的输出，因此请勿输出。
• 在完成对全部 $2Q$ 个查询的响应后，请立即终止你的程序。否则评测结果将不确定。
• 本题的评测系统是非自适应的。在交互开始前，评测系统已预先确定所有查询的类型与顺序，以及每个入队查询中给出的整数 $X$。

约束条件

• $1 \le Q \le 5000$
• $1 \le X \le 10^9$
• 所有入队查询中追加的值 $X$ 互不相同。
• 入队查询与出队查询各出现 $Q$ 次。
• 每次出队查询发生时，至少存在一个非空队列。
• 所有输入值均为整数。