AT_arc226_d [ARC226D] 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.

N/A

N/A

### 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. ### Sample Interaction Below is a case where $ Q=2 $ , and the judge appends the values $ 5,3 $ in this order. InputOutputDescription``` 2 ``` $ Q $ is given.``` 1 5 ``` A push query. $ X=5 $ is given, and it is appended to the back of queue $ 1 $ .``` 0 ``` Perform zero move operations.``` 1 3 ``` A push query. $ X=3 $ is given, and it is appended to the back of queue $ 1 $ .``` 3 1 2 1 2 2 2 ``` Perform three move operations. Move $ 5 $ to queue $ 2 $ , move $ 3 $ to queue $ 2 $ , and move the front value $ 5 $ of queue $ 2 $ to the back of the same queue. As a result, queue $ 2 $ contains $ 3,5 $ from front to back.``` 2 ``` A pop query.``` 2 ``` Choose queue $ 2 $ . Then, the judge removes the front value $ 3 $ of queue $ 2 $ .``` 2 ``` A pop query.``` 2 ``` Choose queue $ 2 $ . Then, the judge removes the front value $ 5 $ of queue $ 2 $ . ### 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.