There is an array of cells, numbered from to . For each pair of integers , where , there is a barrier covering all cells from to , inclusive. Each barrier is either or . A cell is if there are no active barriers that cover it. Otherwise, the cell is .
The state of each barrier is unknown to you. All you can observe is the number of visible cells. But you can flip the state of any barrier: if it's active, it turns inactive, and the other way around. Your task is to make all barriers inactive, so that all cells become visible.
Interaction Protocol
First, read an integer , denoting the number of cells ().
The following interaction will proceed in rounds. Your program should start each round by reading an integer , denoting the number of currently visible cells ().
If , then the task is done and your program must exit.
If , you can flip the state of any barrier. On a separate line, print two integers and to flip the state of the barrier (). After your query, the next round begins, and your program should read a new value of .
Your solution must make all cells visible using at most flips. In the beginning, not all cells are visible ( in the first round).
The interactor is not adaptive: in every test, the state of all barriers is chosen before the program execution.
输入格式
See Interaction Protocol.
输出格式
See Interaction Protocol.
样例
样例输入 1
3
0
0
1
2
3
样例输出 1
2 2
2 3
1 2
2 2
数据范围与提示
Initial State.
In the example, initially, only two barriers, and , are active. These two barriers cover all three cells, so is equal to 0 in the first round.
After flipping the barrier, there are now three active barriers, and still visible cells.
After flipping the barrier, cell becomes visible, so now there is visible cell.
After flipping the barrier, cell also becomes visible. The only invisible cell now is , covered by the only active barrier, , and there are visible cells.
After flipping the barrier, all barriers are now inactive, and all cells are visible. After reading , the program terminates.
