Interactive Hoglins Hunt

Problem Statement

This is an interactive problem.

Harry and Hermione are trying to hunt down \(\emph{hoglins}\) which are haunting Hogwarts. There is a long hallway in Hogwarts, consisting of \(n\) individual \(\emph{cells}\), numbered from \(1\) to \(n\) from left to right.

Hermione can cast a spell that would \(\emph{block}\) any cell of the hallway of her choosing. After the spell is cast, the blocked cell will remain blocked while she casts other spells.

Hoglins are simple creatures; all they do is randomly move around and bump into stuff. More precisely, every hoglin has a range which it considers to be \(\emph{accessible}\). Initially, when the hoglin appears, its accessible range is from cell \(1\) to cell \(n\).

At the beginning of the hunt a single hoglin appears in a cell chosen uniformly at random. Then, until this hoglin is caught, the following happens in each round:

• Hermione can cast a spell to block any single cell of her choosing, or do nothing.
• If the cell she is trying to block is the cell with the hoglin, the hoglin is caught. Immediately after that, all blocked cells become free, and if there are more hoglins to catch the next one appears immediately in a random cell.
• If the hoglin is not caught, it chooses a target cell uniformly at random from its accessible range and starts moving towards it (one cell at a time) as follows:
  • If the target cell is to the right of its current position, it moves right; if it is to the left, it moves left. If the chosen cell is the same as its current cell, it does nothing.
  • During the movement, if the hoglin tries to move from an unblocked cell at position \(i\) to a neighboring blocked cell at \(i\pm1\), it updates the corresponding boundary of its accessible range to \(i\).
  • If the hoglin bumps into any blocked cell on its way (i.e. it attempts to move into a blocked cell), a loud sound is produced. In this case, the hoglin returns to its starting cell for that round.
  • If it does not bump into a blocked cell, the hoglin stays at the target cell and its accessible range remains unchanged.

To free Hogwarts from hoglins, Harry and Hermione need to catch \(k\) hoglins. However, they only have time to hunt for at most \(200\,000\) rounds. Help them devise an efficient strategy!

Interaction Protocol

The judge first outputs two integers \(n\) and \(k\) (\(1 \le n \le 10^{18}\); \(1 \le k \le 800\)). Then the hunting begins.

The interaction proceeds in rounds as follows:

1. At the beginning of each round, your program must output an integer \(p\) (\(0 \le p \le n\)), indicating the cell Hermione will try to block. If \(p=0\) or if the cell is already blocked, no new cell is blocked in that round.
2. If the current hoglin is in cell \(p\) then it is caught. The judge outputs 2 (or 3 if it is the \(k\)th hoglin caught), all blocks are reset, and the next hoglin appears immediately (if any remain).
3. If the hoglin is not caught, it moves as described. The judge outputs 0 if the hoglin moves successfully without bumping, or 1 if it bumps into a blocked cell during its move.
4. If you perform \(200\,000\) actions without catching the \(k\)th hoglin, the judge outputs -1 and terminates your program.

Summary of Judge Responses

• -1 — Too many actions.
• 0 — Hoglin moved successfully without bumping.
• 1 — Hoglin bumped into a blocked cell during its move.
• 2 — Hoglin caught (interaction resets for the next hoglin).
• 3 — Hoglin caught and this was the \(k\)th hoglin (terminate your program immediately).

inputFormat

Input Format:

The first line contains two integers \(n\) and \(k\) --- the number of cells in the hallway and the number of hoglins to catch. The subsequent interaction is governed by the protocol described in the statement.

outputFormat

Output Format:

In each round, output a single integer \(p\) (\(0 \le p \le n\)), representing the cell Hermione tries to block. Remember to flush the output each round as the problem is interactive.

sample

10 1
0
2

0

</p>