## Task Description

Let us play *Lights Out*, again.

*Lights Out* is a puzzle game consisting of an $N$ by $N$ grid of lights which can be turned on and off.
Each of these $N^2$ lights has an id from $0$ to $N^2-1$ from left to right, and from top to bottom.
When the game starts, a random number of these lights are turned on.
Please refer to the following figure.

Pressing any of the lights will toggle it and all of its immediate vertical and horizontal neighbors.
The goal of the puzzle is to turn off *all* the lights with the minimum number of pressing.
Note that the order in which the lights are pressed does *not* affect the results.
Also note that we do not need to press a light more than once since pressing it twice is the same as not to press it at all.
Please refer to the following figure.

We will solve this problem by objects.
First, you have to design your own object *Lights* in **lights.h**.
*Lights* needs to implement four functions.
Function ** init** will turn off all lights.
Function

**will toggle the i-th light, and the size of lights is NxN. Function**

*flip***returns the number of the lights that are**

*numOfLights**on*, and the size of lights is NxN. For efficency you should not examine all lights to find their status. Instead you should remember the number of lights and update with

**, so that**

*flip******can return it immediately. Function

*numOfLights***will print the status of all lights. The prototype of the four functions are in**

*printLights***lights.h**as follows.

`typedef`

`struct`

`_lights{`

` `

`// Design by yourself`

`}Lights;`

`void`

`init(Lights *l);`

`int`

`numOfLights(Lights *l,`

`int`

`N);`

`void`

`flip(Lights *l,`

`int`

`i,`

`int`

`N);`

`void`

`printLights(Lights *l,`

`int`

`N);`

You need to implement all four functions.
You can test your ** flip** function with the following

**main_flip.c**:

`#include<stdio.h>`

`#include "lights.h"`

`int`

`main()`

`{`

` `

`Lights l;`

` `

`init(&l);`

` `

`int`

`n;`

` `

`int`

`index;`

` `

`int`

`N;`

` `

`scanf`

`(`

`"%d"`

`,&N);`

` `

`while`

`(`

`scanf`

`(`

`"%d"`

`,&n)!=EOF)`

` `

`flip(&l,n,N);`

` `

`printLights(&l,N);`

` `

`return`

`0;`

`}`

You can test your ** numOfLights** with the following

**main_numOfLights.c**

`#include<stdio.h>`

`#include "lights.h"`

`#define ROUND 200000000`

`int`

`main()`

`{`

` `

`Lights l;`

` `

`init(&l);`

` `

`int`

`n;`

` `

`int`

`N;`

` `

`scanf`

`(`

`"%d"`

`,&N);`

` `

`while`

`(`

`scanf`

`(`

`"%d"`

`,&n)!=EOF)`

` `

`flip(&l,n,N);`

` `

`int`

`num=0;`

` `

`for`

`(`

`int`

`i=0;i<ROUND;i++){`

` `

`num=numOfLights(&l,N);`

` `

`}`

` `

`printf`

`(`

`"%d\n"`

`,num);`

` `

`return`

`0;`

`}`

Finally write a **main.c** to find the minimum set of lights that need to be pressed to turn off all lights with the object Light provided by the TA.
If there are multiple sets of them, output the first one in dictionary order.
For example, 1 2 4 appears earlier than 1 3 4 in the dictionary order.

## Compile

`gcc -std=c99 -O2 main_flip.c lights.c `

`gcc -std=c99 -O2 main_numOfLights.c lights.c `

`gcc -std=c99 -O2 main.c lights.c`

## Subtasks

- 40 points: Only the correctness of
**init**,**flip**,and**printLights**will be considered in these subtasks. - 40 points: Correctness of all of the four functions will be considered in these subtasks.
- 20 points:
**main.c**will be checked with TA's functions. So if only the correctness of**main.c**can still get these points.

Note that if you have not completed all of the functions and you still want to submit your solution for partial credits, your **main.c** and function **numOfLights** should be empty so the program will compile, as shown below:

1 `int`

`main(){}`

1 `int`

`numOfLights(Lights *l,`

`int`

`N){}`

## Input Format

For **main_flip.c** and **main_numOfLights.c** and **main.c**, the input formats are the same.
The first line is $N$.
The second line has the indices of the lights that will be toggled in order.

- $3 ≤ N ≤ 4$

## Output Format

For **main_flip.c**, print the status of all of the lights. **1** for the **on**, and **0** for the **off**.
For **main_numOfLights.c**, print the number of the lights which are turned on.
For **main.c**, print the indices of the lights that need to be pressed in *ascending* order.
If there are multiple answers, output the first one in dictionary order.

## Sample Input 1_0 (for main_flip.c)

`4`

`0 9 13`

## Sample Output 1_0

`1 1 0 0`

`1 1 0 0`

`1 0 1 0`

`1 0 1 0`

## Sample Input 2_0 (for main_numOfLights.c)

`4`

`0 9 13`

## Sample Output 2_0

`8`

## Sample Input 3_0 (for main.c)

`4`

`0 1 2 6 10 11 12 13 15`

## Sample Output 3

`0 2 4 5 10`