LIGHTS

Problem

Let there be ~N~ light bulbs arranged in a row, numbered from ~1~ to ~N~. Some of these light bulbs are initially on, and the rest are off.

Our goal is to turn off all the light bulbs (you know how electricity bills have been rising lately), but this seems challenging because we don't know which bulbs are initially on.

This problem is interactive and can be imagined as a game with many independent rounds, in each of which you must find a way to turn off all the light bulbs by making a suitable sequence of moves, the number of which must not exceed a given number ~Q~.

The code you will write must call the functions with the following headers, which will be found in #include "lightslib.h":

pair<int, int> getNQ();
int move(int left, int right);
bool finish();

Specifically:

• The function getNQ() returns a pair of positive integers: the total number ~N~ of light bulbs and the maximum number ~Q~ of allowed moves. It should be called exactly once at the beginning of each round.

• The function move(left, right) toggles the state of the light bulbs between positions ~left~ and ~right~, included. Specifically, for each bulb ~i~ such that ~left \le i \le right~, bulb ~i~ is turned off if it was previously on, or turned on if it was previously off. The function returns the total number of light bulbs that are on after completing this move. The values of the parameters must satisfy the relationship ~1 \le left \le right \le N~.

• The function finish() must be called exactly once at the end of each round, when all light bulbs are off. It triggers the end of the round. It returns ~false~ if the game has not finished yet (meaning your program should continue to the next round), or ~true~ if your program should stop its execution.

There are no input or output data for this problem. Your program communicates with the grader only through the above three functions.

Constraints

• The number of rounds will not exceed ~10~.
• The number of light bulbs in each round will be ~1 \le N \le 100.000~.
• Consider that the responses of the three functions may depend on the sequence of moves you make (the grader is adaptive).

• If you violate the communication protocol, your program will terminate and the test case will be considered failed. For example, the following are considered violations of the communication protocol:

  • Calling getNQ at any time other than the beginning of a round.
  • Calling finish at any time other than when all light bulbs are off.
  • Calling move before getNQ or after finish in a round.
  • Calling any function after finish has returned ~true~.
  • Calling move with parameters outside the specified bounds.
  • Calling move more than ~Q~ times in a round.
  • Using any input/output commands.

• Time Limit: ~1~ sec.

• Memory Limit: ~64~ MB.

Example

Notes

• For test cases with a total value of ~30%~, it will be ~Q = 3N~
• For the rest of the test cases, it will be ~Q = N + 1~