Bulb Game

Friends Minhyeong and Seonyul play a game on a board with $N$ buttons and $N-1$ bulbs. $N$ is always even.

Minhyeong and Seonyul take turns pressing buttons. At each step, the player picks a button that has not been pressed yet and presses it. When Seonyul presses a button, the state of every bulb between that button and the button Minhyeong pressed just before is flipped. Off bulbs turn on, and on bulbs turn off.

At the start, every bulb is off. If Minhyeong presses button 2 and Seonyul presses button 4 from this state, the board changes as shown below.

If Minhyeong then presses button 3 and Seonyul presses button 5, the board changes as shown below.

The game ends when all $N$ buttons have been pressed. If more bulbs are on than off, Seonyul wins. Otherwise, Minhyeong wins.

To make the game exciting, Seonyul proposed that the loser buy chicken for 16 friends, including Minhyeong and Seonyul. Chicken for 16 people is expensive, so losing could cost Seonyul a large sum. Write a program that plans a strategy for Seonyul to win. A winning strategy always exists.

You must write the functions Init(N) and MakeTurn(M) that play the game. (Init(N) and MakeTurn(M) are in bulb.c / bulb.cpp.)

void Init(int N) is called once at the start. You can do preprocessing here.

• $N$: number of bulbs ($2 \le N \le 1\,000$, $N$ is even)

int MakeTurn(int M) is called $N/2$ times after Init is called. Return the number of the button Seonyul should press on his turn.

• $M$: number of the button Minhyeong pressed on his turn ($1 \le M \le N$)
• Return value: number of the button Seonyul presses on his turn ($1 \le$ return value $\le N$)

If the game finishes normally and Seonyul loses, print Wrong[1]. If the return value of MakeTurn(M) is out of range or is a button that was already pressed, print Wrong[2] and the program ends immediately.

An example program is shown below.

#include "bulb.h"

void Init(int N) {
	// do nothing
}

int MakeTurn(int M) {
	return (M+2)%7;
}

Do not use memory access, system calls, or other abnormal methods. Doing so may be judged wrong.

You can download sample code from the problem page. If you use an IDE such as Visual Studio, Eclipse, or Code::Blocks, put bulb.cpp, bulb.h, and grader.cpp (or bulb.c, bulb.h, and grader.c) in one project and compile it.

In a terminal, use one of these commands.

• C / gcc: gcc -Wall -lm -static -o bulb -O2 bulb.c grader.c
• C++ / G++: g++ -Wall -lm -static -o bulb -O2 bulb.cpp grader.cpp

When you run the program, it reads $N$ from stdin, then reads the button number Minhyeong pressed. The grader prints the button number Seonyul pressed (the return value of MakeTurn). After the game ends, the sample grader prints whether the answer is correct.

Submit only the code for bulb.c or bulb.cpp.