B. Rectangular Wooden Block
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Mr. Noya has a pet hamster that loves to gnaw on wood.

One day, Mr. Noya brought home a rectangular wooden block with dimensions $$$L \times W \times H$$$, meaning it has a length of $$$L$$$ units, a width of $$$W$$$ units, and a height of $$$H$$$ units, divided into $$$L \times W \times H$$$ unit cubes. Using one vertex of the block as the origin, the length direction as the $$$x$$$-axis, the width direction as the $$$y$$$-axis, and the height direction as the $$$z$$$-axis, a spatial coordinate system $$$O-xyz$$$ is established. The unit cube with $$$x$$$-coordinate in $$$[i-1, i)$$$, $$$y$$$-coordinate in $$$[j-1, j)$$$, and $$$z$$$-coordinate in $$$[k-1, k)$$$ is denoted as $$$(i, j, k)$$$.

Note: The block does not necessarily have length greater than width (i.e., it is not required that $$$W \leq L$$$); the terms are just used to fix the directions.

Mr. Noya does not want the wooden block to be completely gnawed away by his hamster, so he decides to reinforce it. Reinforcing the unit cube at $$$(i,j,k)$$$ has a cost $$$V(i,j,k)$$$. Additionally, there are three matrices $$$A,B,C$$$ representing constraints from the three orthogonal views (front view, side view, and top view):

  • For matrix $$$A = \{a_{ij}\}_{H \times L}$$$, if $$$a_{ij} = 0$$$, then for all $$$1 \leq p \leq W$$$, the cube at $$$(j, p, i)$$$ must not be reinforced. If $$$a_{ij} = 1$$$, at least one of these cubes must be reinforced.
  • For matrix $$$B = \{b_{ij}\}_{H \times W}$$$, if $$$b_{ij} = 0$$$, then for all $$$1 \leq q \leq L$$$, the cube at $$$(q, j, i)$$$ must not be reinforced. If $$$b_{ij} = 1$$$, at least one of these cubes must be reinforced.
  • For matrix $$$C = \{c_{ij}\}_{W \times L}$$$, if $$$c_{ij} = 0$$$, then for all $$$1 \leq r \leq H$$$, the cube at $$$(j, i, r)$$$ must not be reinforced. If $$$c_{ij} = 1$$$, any number (including zero) of these cubes may be reinforced.

Note: Mr. Noya can reinforce each unit cube at most once.

Note: For matrix $$$C$$$, a non-zero value does not require reinforcing at least one unit cube.

Under the above conditions, Mr. Noya wants to minimize the total cost of reinforcing the wooden block. Can you help him?

Note: You do not need to consider the issue of unit cubes being suspended in air.

Input

The first line contains a positive integer $$$T$$$ $$$(1 \leq T \leq 5 \times 10^3)$$$, indicating the number of test cases.

For each test case, the first line contains three positive integers $$$L$$$, $$$W$$$, $$$H$$$ $$$(1 \leq L \times W \times H \leq 10^3)$$$, representing the length, width, and height of the block.

The next line contains $$$L\times W\times H$$$ integers. The $$$[(i-1)\times W+j-1]\times H+k$$$-th integer is $$$V(i,j,k)$$$ $$$(-10^9\leq V(i,j,k)\leq 10^9)$$$.

Then follow $$$H$$$ lines. The $$$i$$$-th line is a binary string of length $$$L$$$, denoted $$$a_{i1}a_{i2}\cdots a_{iL}$$$, representing the $$$i$$$-th row of matrix $$$A$$$.

Then follow $$$H$$$ lines. The $$$i$$$-th line is a binary string of length $$$W$$$, denoted $$$b_{i1}b_{i2}\cdots b_{iW}$$$, representing the $$$i$$$-th row of matrix $$$B$$$.

Then follow $$$W$$$ lines. The $$$i$$$-th line is a binary string of length $$$L$$$, denoted $$$c_{i1}c_{i2}\cdots c_{iL}$$$, representing the $$$i$$$-th row of matrix $$$C$$$.

It is guaranteed that the sum of $$$L \times W \times H$$$ over all test cases in a single test point does not exceed $$$5 \times 10^3$$$.

Output

For each test case, the first line contains a string $$$\texttt{YES}$$$ or $$$\texttt{NO}$$$ indicating whether Mr. Noya's conditions can be satisfied.

If the conditions can be satisfied, then output on the second line an integer representing the minimum reinforcement cost of the cuboid; on the third line a nonnegative integer representing the number $$$k$$$ of reinforced unit cubes; followed by $$$k$$$ lines, each containing three positive integers representing the coordinates of each reinforced unit cube. Note that each unit cube can be reinforced at most once.

If there are multiple valid solutions, outputting any one of them will be considered correct.

Example
Input
2
3 2 2
1 1 4 5 -1 4 -1 9 1 9 8 1
011
111
11
11
111
111
1 2 2
1 2 3 4
0
0
01
01
1
1
Output
YES
5
6
2 1 1
2 2 1
3 1 1
1 1 2
2 1 2
3 2 2
NO