M. Mondriamorsolo
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Bob's Mondrianansala artworks from last year were so popular that his art teacher has tasked him with creating another collection of paintings for this year's STEM Exhibit. Bob, foolishly, accepts.

Bob's paintings will once again be composed entirely of rectangles, in what he calls the Mondriamorsolo style. This year, Bob wants his paintings to be even more gorgeously geometric, so he recalls the following definitions from math class.

Recall that two objects are congruent if one can be transformed into the other by some combination of rotations or reflections. Two objects are similar if one can be made congruent to the other by scaling it up or down by the same amount in all directions.

For example, consider the following image.

  • The $$$4 \times 6$$$ rectangle would be congruent to any other $$$4 \times 6$$$ rectangle.
  • The $$$4 \times 6$$$ and $$$6 \times 4$$$ rectangles are congruent because one is just a rotation of the other.
  • The $$$2 \times 3$$$ rectangle is similar to the $$$4 \times 6$$$ and $$$6 \times 4$$$ rectangles, because it can be made congruent to both of them by scaling by a factor of $$$2$$$ in all directions.

Bob wants all rectangles in his painting to be irreducible, which he defines as follows:

  • A rectangle is reducible if it has integer side lengths, and if it can be cut up into some number of non-overlapping rectangles that satisfy the following conditions,
    • They all also have integer side lengths
    • They are all congruent to each other
    • They are all similar to the original rectangle
  • If not, then the rectangle is irreducible.
For example, the $$$4 \times 6$$$ rectangle is reducible, because we can cut it up into four $$$2 \times 3$$$ rectangles. On the other hand, we can show that the $$$2 \times 3$$$ rectangle is irreducible.

Now, the problem. A painting is in the Mondriamorsolo style if it satisfies all of the following criteria.

  • It is painted on an $$$n \times n$$$ canvas.
  • The painting is entirely composed of exactly $$$n$$$ rectangles with positive integer dimensions, and all of these rectangles are irreducible
  • No two rectangles in the painting are congruent to each other.
  • Each rectangle is painted one of $$$26$$$ different colors, and the entire rectangle is painted that color.
  • No two rectangles that touch at their edges may have the same color (though rectangles of the same color may touch at corners).
Here is an example of a $$$7 \times 7$$$ Mondriamorsolo painting.

Given a positive integer $$$n$$$, help Bob by producing any painting of that size in the Mondriamorsolo style, or say that no such painting exists.

Input

Input consists of a single line that contains a single integer $$$n$$$.

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq n \leq 1200 \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{30} & 1 \leq n \leq 8 \\ \hline 2 & \mathbf{16} & \text{$n=1$ or $n = 1000$} \\ \hline 3 & \mathbf{16} & \text{$n=1$ or $n = 1011$} \\ \hline 4 & \mathbf{16} & \text{$n=1$ or $n = 1200$} \\ \hline 5 & \mathbf{11} & 1 \leq n \leq 100 \\ \hline 6 & \mathbf{11} & \text{No further constraints.} \\ \hline \end{array}\\

\end{align*}$$$$$$

Output

If the task is possible, output YES. Otherwise, output NO.

If YES, also output the painting. We will treat the painting as a pixelmap and represent it as an ASCII grid.

Output $$$n$$$ lines, each containing a string with $$$n$$$ uppercase English letters, representing the painting. Two pixels are considered the same color if they are represented by the same letter. Contiguous regions of pixels of the same color correspond to the rectangles.

Examples
Input
1
Output
YES
A
Input
2
Output
NO
Input
7
Output
YES
CAABBBC
BAABBBC
BAABBBC
BAABBBC
BAABBBC
BAACCCB
BAACCCB