Problem Description

Given an infinite chessboard (which can be viewed as a 2D Cartesian coordinate system) and $n$ white pieces and $n$ black pieces, you need to place them on integer lattice points of the board without overlap, such that there exist exactly $n$ straight lines satisfying:

• Each line passes through and only passes through a total of 4 pieces (black and white together).

• Along the line in order, it passes through black, white, white, black pieces.

Output any valid construction.

Input Format

The input contains only one line: $n$ as described in the statement.

Output Format

If it is impossible to construct a solution, output NO.

Otherwise output $2n+1$ lines: the first line outputs YES. Lines $2\sim n+1$ each contain two integers, the coordinates $x_i,y_i$ of a white piece. Lines $n+2\sim 2n+1$ each contain two integers, the coordinates $x_j,y_j$ of a black piece.

You must ensure that $-5\times 10^5\le x_i,y_i,x_j,y_j\le 5\times 10^5$.

1

NO

7

YES
2 4
2 6
4 6
5 4
6 4
6 2
4 2
0 6
2 8
6 6
8 2
6 0
3 0
2 2

Hint

[Sample Explanation]

Explanation for Sample 2: (The output lists points $A\sim N$ in order (points $A\sim G$ are white pieces, points $H\sim N$ are black pieces), and the lines are shown in the figure).

[Constraints]

This problem uses bundled testdata.

• Subtask 1 (10 pts): $n\equiv 0 \pmod{7}$.
• Subtask 2 (20 pts): $40\le n\le 400$.
• Subtask 3 (30 pts): $1\le n\le 9$.
• Subtask 4 (40 pts): no special restrictions.

For $100\%$ of the testdata, $1\le n\le 10^3$.

SPJ link

Usage: after compiling to checker.exe, in the same directory run on the command line: checker.exe chessboard.in chessboard.out chessboard.ans

You also need to use it together with testlib.h. testlib download link.

If you find the SPJ is broken, please contact the problem setter.

Translated by ChatGPT 5