P. Night Gown
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

A national beauty pageant is the qualifier for an international beauty pageant, whose evening gown segment is held on a lava lake. Catriona, Emma, and Nadine are the three finalists of this. In preparation for the international pageant's evening gown segment, the night gown segment of this pageant is held on a $$$16 \times 16$$$ grid of squares, each containing a different sort of liquid.

Exactly one of the squares is a stone that the three contestants start on. Each step consists of walking from a square to the square in front of it, behind it, to its left, or to its right. Each square contains one of three things: lava, water, or lemonade.

Fortunately, all three contestants are fireproof, immune to lava, and can walk on liquids. Unfortunately, the contestants are wearing different colors of gowns, which means they can only walk on liquids that match the colors of their gowns:

  • Catriona is wearing an orange gown. Since orange is red mixed with yellow, she can walk on only lava or lemonade.
  • Emma is wearing a green gown. Since green is yellow mixed with blue, she can walk on only lemonade or water.
  • Nadine is wearing a purple gown. Since purple is blue mixed with red, she can walk on only water or lava.
However, due to corruption, the organizers conspired that each participant can only reach a certain number of squares by doing a series of steps starting from the starting square. They want to choose the layout of the grid such that Catriona can only reach $$$c$$$ squares, Emma can only reach $$$e$$$ squares, and Nadine can only reach $$$n$$$ squares. The square the contestants begin on counts as one of these squares.

Can you find a possible layout of the grid that satisfies this? If there is no such layout, say so.

Input

The first line of input contains $$$t$$$, the number of test cases.

Each test case consists of a single line containing three space-separated integers $$$c$$$, $$$e$$$ and $$$n$$$.

Output

For each test case, first output a single line containing either YES or NO denoting whether it is possible. If you printed YES, output 16 more lines, each containing 16 characters from the following:

  • S, which represents the starting stone.
  • ., which represents lava.
  • #, which represents water.
  • $$$\sim$$$, which represents lemonade.
Scoring

$$$0 \le t \le 60000$$$

$$$9 \le c, e, n \le 111$$$

Subtask 1 (4 points):

$$$t \le 1000$$$

$$$c = e = n = 21$$$

Subtask 2 (7 points):

$$$t \le 1000$$$

$$$c$$$, $$$e$$$ and $$$n$$$ belong to the set $$$\{21, 42\}$$$

Subtask 3 (8 points):

$$$t \le 20000$$$

$$$c = 16$$$

$$$e \ge 32$$$

$$$n \ge e + 16$$$

Subtask 4 (18 points):

$$$t \le 20000$$$

$$$21 \le c, e, n \le 42$$$

Subtask 5 (42 points):

$$$c + e + n \le 168$$$

Subtask 6 (21 points):

No additional constraints.

Example
Input
1
110 89 101
Output
YES
#####.#~~~####..
####..##~~####..
......##~~#####.
.##....##~~####.
.###.##.#~~.##.#
###..##.~~..S.#.
.##.#..~~~......
...##.~.~~..###.
#.##.~.~~...####
##..~.~~..######
##.~~~~~~..#####
#.~~~~~~~.#..###
.~~##.~~~.#.##..
.~.###..~~.####.
.~~....~~~.#####
#.~~~~~~~.######