P10871 [COTS 2022] Queens Kraljice

Translated from [Izborne Pripreme 2022 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2022/) D1T1。$\texttt{1s,0.5G}$。

There is an $N \times N$ chessboard. Place queens on empty squares **one by one**, maximizing the number of queens placed. You need to construct a valid plan. A queen can be placed on a square if and only if that square is attacked by an even number of queens. A queen attacks a square if and only if the queen's square and the attacked square are in the same row, column, or diagonal.

One line with an integer $N$。

The first line contains an integer $K$, the maximum number of queens that can be placed. The next $K$ lines each contain two integers $x, y$, describing the position where a queen is placed.

### Sample Explanation Explanation for sample $3$：  #### Constraints For $100\%$ of the data, it is guaranteed that $1 \le N \le 2^{10}$。 | Subtask ID | Points | Constraints | |:-----:|:------:|:-------:| | $1$ | $6$ | $1 \le N \le 2^4$ | | $2$ | $11$ | $1 \le N \le 2^6$ | | $3$ | $28$ | $1 \le N \le 2^8$ | | $4$ | $55$ | No additional constraints | Translated by ChatGPT 5