Carlo’s Garden

Carlo hates bugs$^1$, he wants to kill every single one of them$^2$. After months of hard work, he successfully killed all the bugs in his garden, but when he was about to celebrate, a grasshopper jumped out of nowhere and started to annoy him.

Figure $1$: Carlo killing the bugs.

Carlo’s garden can be represented as a square grid of length $10^9$. Initially, the grasshopper is standing at the point $(0, 0)$. The grasshopper can only jump by one cell to the East or to the North, i.e. it can jump from $(x, y)$ to $(x + 1, y)$ or $(x, y + 1)$ but not to $(x − 1, y)$ or $(x, y + 2)$. During each second, the grasshopper makes $N$ jumps. For example, if $N = 3$, after one second, the grasshopper can be at $(0, 3)$, $(2, 1)$ but not at $(3, 3)$ or $(1, 1)$.
Carlo wants to catch the grasshopper by placing traps in the garden. If the grasshopper jumps to a point where there is a trap, it will be caught and Carlo can finally celebrate. Unfortunately, he can only place one trap per second.

Figure $2$: If $N=3$, the grasshopper can arrive to $(2, 1)$ by for example first jumping to $(1, 0)$ and then to $(2, 0)$. In this case, if there were any traps on $(1, 0)$, $(2, 0)$ or $(2, 1)$, then it would be caught.

Can you help Carlo to catch the grasshopper with at most $500$ traps?

Interaction protocol

This is an interactive task.

The contestant must implement the following function:

void solve(int n);

This function will be called exactly once, at the beginning of the interaction, and supplies the contestant with the length of the grasshopper's jump - $n$. Inside this function, you can call the following function:

std::pair<int, int> trap(int x, int y)

This function will place a trap at the coordinate $(x, y)$, which is not the grasshopper’s current position, and will return the new position of the grasshopper. Once you have caught the grasshopper, the execution of the program will stop.

Don't forget to include the grasshopper.h header!

Constraints and clarifications

• $1 \leq N \leq 5$.
• Carlo’s garden is a square grid of size $10^9$.
• You can place at most $500$ traps.
• The interactor is adaptive, meaning that the route and final position of the grasshopper in each round will be determined based on your output.

Your program will be tested against several test cases grouped in subtasks. In order to obtain the score of a subtask, your program needs to correctly solve all of its test cases.

$^1$ The “animals” bugs, not the “informatics” bugs. He also hates informatics bugs by the way.
$^2$ Except bees, bees are cool.

This is an interactive task! The interaction presented here is just an example.

Example

• solve is called with $n = 1$
• trap(1, 1) returns $\{1, 0\}$
• trap(2, 0) sucessfully traps the grasshopper

Explanation

In this example $N = 1$, so the grasshopper can only jump by one cell at a time.
Initially the grasshopper is at $(0, 0)$, Carlo places a trap at $(1, 1)$.

Then the grasshopper jumps to $(1, 0)$, Carlo places a trap at $(2, 0)$.

The grasshopper can only jump to $(2, 0)$ or $(1, 1)$, in both cases it will jump on a trap and Carlo can celebrate.