Lumber Jack is a well known bus driver in Cluj-Napoca. After so many mornings ruined by passengers fighting over free seats, he decided to make his life a little easier.
There are N ≤ 105 people in a queue, waiting for the bus. They are indexed 1 through N. Lumber Jack wants to make sure that only people who do not fight with each other get on the same bus, while all others wait for the next one.
Theoretically, there are infinitely many buses, with infinite capacity (initially empty), which arrive one after the other. However, Lumber Jack wants to use a finite number of them, which he seeks to minimize.
He wants to fill the buses with as many people as possible. The first person in the queue gets on the current bus instantly as it arrives. Each person afterwards gets on the same bus, if possible (that is, they won't get in a fight with someone else in the bus). If some person can't get on the bus, they (and everyone behind them in the queue) must wait for the next one.
Our bus driver can ask questions about the people in the queue. The boolean function F(x, y) tells him whether or not passengers with indices x, x+1, …, y can be seated safely in the same bus. Asking such a question has a cost of y-x+1 GMs.
Lumber Jack has exactly 20*N GMs. He is allowed to give the result (i.e. the minimum number of needed buses, and the first person who enters each bus) only at the end of the interaction.
Interaction
Your solution will be verified by a simulator. The simulator will provide on the first line the integer N.
You can respond by writing either one of the following queries:
- 1 x y, where 1 ≤ x ≤ y ≤ N.
- 2 k a1 a2 … ak.
Each query of type 1 denotes the fact that Lumber Jack asks F(x, y). The simulator will print 0 or 1, with the meaning stated above.
You should only have a single type 2 query. This means that Lumber Jack decided he needs k buses, and ai is the first person who got on bus i (1 ≤ i ≤ k). Afterwards, your program should halt.
Note: After each command you should print a newline character and immediately flush the output, using functions such as fflush(stdout) or cout.flush().
Score
Your solution is considered correct if, for all testcases, the number of buses and the first person from each bus are correct, and Lumber Jack does not exceed 20*N GMs.
Sample
| User program | Simulator | Explanation |
|---|---|---|
| 6 | There are 6 people at the bus stop. | |
| 1 1 2 | Can the first two passengers be seated in the same bus? (cost = 2) | |
| 1 | Yes, they can. | |
| 1 1 3 | Can the first three passengers be seated in the same bus? (cost = 3) | |
| 1 | Yes, they can. | |
| 1 1 4 | Can the first four passengers be seated in the same bus? (cost = 4) | |
| 0 | No, they can't. Better ship the first three passengers and then wait for the next bus. | |
| 1 4 5 | Can the fourth and fifth passengers be seated in the same bus? (cost = 2) | |
| 0 | No, they can't. Better ship the fourth passenger all by himself, and make the fifth wait. | |
| 1 5 6 | Can the fifth and sixth passengers be seated in the same bus? (cost = 2) | |
| 1 | Yes, they can. Ship them together on the last bus. | |
| 2 3 1 4 5 | Lumber Jack provides his answer. At least 3 buses are needed. They are loaded as follows:
|
