9125: Puzzle: Star Battle

Grammy is a puzzle master. Today, she is playing a variant of "Star Battle" puzzle.

The puzzle consists of a $(4n)\times (4n)$ grid. The grid is divided into $4n$ blocks, but each block may be disconnected. The goal is to place stars into the grid so that each row, each column, and each block contains exactly $n$ stars. Additionally, two stars cannot be adjacent, diagonally or orthogonally. In other words, two stars cannot be placed in two cells that share an edge or a corner.

The left picture illustrates a $4\times 4$ empty puzzle, and the right picture shows a solution to the puzzle.

Grammy surely knows how to solve the puzzle, but she decided to give you a quiz. Please solve the puzzle.

The first line contains a single integer $n$ ($1\le n\le 300$), denoting the number of stars to place in each row.
Each of the following $4n$ lines contains $4n$ integers grcg_{rc}grc (1≤grc≤4n1 \leq g_{rc} \leq 4n1≤grc≤4n), denoting the index of the block which the cell (at row $r$, column $c$) belongs to. It is guaranteed that each block contains at least one cell. However, it is not guaranteed that each block is an orthogonally connected region.

If the solution does not exist, output "$\text{NO}$" on a single line.
Otherwise, output "$\text{YES}$" on the first line, then output 4n24n^24n2 lines, each of which contains $2$ integers r,cr,cr,c (1≤r,c≤4n1\leq r,c \leq 4n1≤r,c≤4n), denoting the coordinates (row $r$, column $c$) of each placed star.
If there are multiple solutions, output any.

1
1 2 2 2
1 2 2 4
3 4 4 4
3 3 3 4

YES
1 3
2 1
3 4
4 2