C. Canonizing Cannonade
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Here is a well-known joke among Jesuits:

Q: When was St. Ignatius of Loyola canonized?

A: At the Battle of Pamplona

Bob is helping choreograph a mock battle at his school, where the participants are role-playing as soldiers at the Battle of Pamplona.

A formation is an $$$r \times c$$$ grid with $$$m$$$ of its squares containing a soldier. The enemy can spend one cannonball to do the following:

  • Select a row or column, and eliminate all soldiers in the chosen row or column.
Let the resiliency of a formation be the minimum number of cannonballs needed to eliminate all its soldiers.

You are given $$$r, c, m, k$$$. Construct any formation such that its resiliency is exactly equal to $$$k$$$ (or say if the task is impossible). Also, please answer $$$T$$$ different test cases per file.

Input

The first line of input contains a single integer $$$T$$$. Then, the descriptions of each of the $$$T$$$ test cases follows.

Each test case is described by a single line containing the four space-separated integers $$$r, c, m, k$$$.

Output

For each test case, if the task is possible, output a line containing the word YES. Otherwise, output NO.

If YES, also output an $$$r \times c$$$ grid—that is, output $$$r$$$ lines, each containing a string of $$$c$$$ characters. The grid should consist only of . and # characters, representing empty space and squares with soldiers, respectively—you are reminded that exactly $$$m$$$ of these characters should be #

If there are multiple possible solutions, any will be accepted.

Scoring

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

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 0 \leq T \leq 1500 \\ 1 \leq r, c \leq 25 \\ 1 \leq m \leq rc \\ 1 \leq k \leq 10^9 \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{40} & m=k \\ \hline 2 & \mathbf{30} & m=2k \\ \hline 3 & \mathbf{20} & m=3 \\ \hline 4 & \mathbf{10} & \text{No further constraints.} \\ \hline \end{array}\\

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

Example
Input
2
7 8 11 4
9 6 2 10
Output
YES
........
...#....
#..#...#
#....#.#
...##.#.
........
...#....
NO
Note

In the first test case, you can verify that the soldiers can all be cleared with $$$4$$$ moves—select the third, fourth, and fifth rows from the top, and also select the fourth column from the left. Since you can't do it in $$$3$$$ moves, we conclude that the resiliency is $$$k=4$$$.

In the second test case, the task is impossible.