3. Table Game
time limit per test
1 s
memory limit per test
512 megabytes
input
standard input
output
standard output

Consider a table consisting of $$$h$$$ rows and $$$w$$$ columns. We denote $$$A_{i, j}$$$ to be the number located at the intersection of the $$$i$$$-th row and the $$$j$$$-th column. It is guaranteed that $$$A_{i, j}$$$ are non-negative integers.

One may apply a sequence of zero or more changes to the table. Each change should be one of the following:

  • Choose a column and remove it from the table (after this operation, columns strictly to the left and to the right of the chosen one will become adjacent).
  • Choose a row and remove it from the table (after this operation, rows strictly to the bottom and to the top of the chosen one will become adjacent).

Determine whether it is possible to perform such operations that after applying them to the table, the sum of its elements becomes equal to $$$s$$$.

Input

The first line of input contains two integers $$$h$$$ and $$$w$$$ — the number of rows and columns of the table $$$A$$$ respectively ($$$1 \leq h, w \leq 15$$$).

Each of the next $$$h$$$ lines contains $$$w$$$ integers — elements of table $$$A$$$ ($$$0 \leq A_{i,j} \leq 10^{9}$$$).

The last line of input contains a single integer $$$s$$$ — the desired sum ($$$1 \leq s \leq 10^{18}$$$).

Output

If it is impossible to get a table with a sum of elements equal to $$$s$$$ from the initial one, print «NO».

Otherwise:

  • In the first line of output, print «YES».
  • In the second line, print a single integer $$$k$$$ — the number of operations you need to perform to get a table with a sum of elements equal to $$$s$$$.
  • In each of the next $$$k$$$ lines, print two integers $$$t_{j}, i_{j}$$$ (where $$$1 \leq j \leq k$$$). If $$$t_{j} = 1$$$, the $$$j$$$-th operation removes row $$$i_{j}$$$ in initial numeration from the table. Otherwise, $$$t_{j}=2$$$ and the $$$j$$$-th operation should remove column $$$i_{j}$$$ from the table.
Scoring

There are 7 subtasks. The score and additional constraints of each subtask are as follows:

|c|c|}

Subtask

Points Additional Constraints Dependencies Feedbac policy
117 $$$h = 1$$$ICPC
26 the sum of elements in $$$i$$$-th row does not exceed $$$i$$$ICPC
310 $$$h \leq 3$$$1ICPC
413 $$$h,w \leq 10$$$ICPC
513 $$$h, w \leq 12$$$4ICPC
612 $$$a_{i, j} \leq 6$$$ICPC
729There are no additional constraints1–6ICPC
Examples
Input
3 3
1 2 3
2 3 1
3 1 2
8
Output
YES
2
1 3
2 3
Input
2 3
2 2 2
2 2 2
5
Output
NO
Input
5 5
1 2 1 4 5
2 5 4 1 2
4 2 4 3 1
5 5 3 2 4
1 2 4 5 2
34
Output
YES
3
1 4
1 5
2 1
Note

In sample input 1, the initial table is as follows:

$$$\begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline 2 & 3 & 1 \\ \hline 3 & 1 & 2 \\ \hline \end{array}$$$

By erasing the third row and the third column, one can get a table with a sum of elements $$$8$$$:

$$$\begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline 2 & 3 & 1 \\ \hline 3 & 1 & 2 \\ \hline \end{array} \to \begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\ \hline 2 & 3 & 1 \\ \hline \end{array} \to \begin{array}{|c|c|} \hline 1 & 2 \\ \hline 2 & 3 \\ \hline \end{array}$$$

In sample input 2, it can be shown that it is impossible to get a table with the desired sum of elements from the initial one.

In sample input 3, the initial table is as follows:

$$$\begin{array}{|c|c|c|c|c|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline 5 & 5 & 3 & 2 & 4 \\ \hline 1 & 2 & 4 & 5 & 2 \\ \hline \end{array}$$$

By erasing rows four and five and row one, we can get a table with a sum of elements $$$34$$$:

$$$\begin{array}{|c|c|c|c|c|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline 5 & 5 & 3 & 2 & 4 \\ \hline 1 & 2 & 4 & 5 & 2 \\ \hline \end{array} \to \begin{array}{|c|c|c|c|c|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline 5 & 5 & 3 & 2 & 4 \\ \hline \end{array} \to \begin{array}{|c|c|c|c|c|} \hline 1 & 2 & 1 & 4 & 5 \\ \hline 2 & 5 & 4 & 1 & 2 \\ \hline 4 & 2 & 4 & 3 & 1 \\ \hline \end{array} \to \begin{array}{|c|c|c|c|} \hline 2 & 1 & 4 & 5 \\ \hline 5 & 4 & 1 & 2 \\ \hline 2 & 4 & 3 & 1 \\ \hline \end{array}$$$