题目背景

翻译自 ROIR 2024 D1T3。

给定一个有 $h$ 行和 $w$ 列的表格 $A$，每个单元格内含有一个整数。行从上到下编号为 $1$ 到 $h$，列从左到右编号为 $1$ 到 $w$。允许对这个表格进行以下操作：

• 选择一列并删除它（删除的列左边和右边的列变为相邻的列）；
• 选择一行并删除它（删除的行上边和下边的行变为相邻的行）。

这些操作可以按任意顺序执行任意多次。

题目描述

你需要确定是否可以通过这些操作将表格变为一个数字之和为 $s$ 的表格。如果可以，请给出具体的操作。

输入格式

第一行包含两个数字 $h$ 和 $w$，表示表格的大小（$1 \leq h, w \leq 15$）。

接下来 $h$ 行，每行包含 $w$ 个整数，其中第 $i$ 行第 $j$ 列为 $A_{i,j}$（$0 \leq A_{i,j} \leq 10^9$）。

最后一行输入数字 $s$，即需要通过操作达到的和（$1 \leq s \leq 10^{18}$）。

输出格式

如果从原始表格中无法得到一个数字之和为 $s$ 的表格，输出 NO。

否则：

• 第一行输出 YES。
• 第二行输出一个数字 $k$ ，表示需要进行的操作次数。
• 接下来的 $k$ 行，每行输出两个整数 $t_j$，$i_j$，其中 $t_j = 1$ 表示操作是对行进行的，$t_j = 2$ 表示操作是对列进行的。数字 $i_j$ 应为操作所针对的行或列的初始编号。

3 3
1 2 3
2 3 1
3 1 2
8

YES
2
1 3
2 3

2 3
2 2 2
2 2 2
5

NO

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

YES
3
1 4
1 5
2 1

提示

在样例 $1$ 中，最初给定的表格是：

$$\begin{matrix} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \\ \end{matrix} $$

删除第三行和第三列后，我们得到以下表格，其元素总和为 $8$：

$$\begin{matrix} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \\ \end{matrix} \rightarrow \begin{matrix} 1 & 2 & 3 \\ 2 & 3 & 1 \\ \end{matrix} \rightarrow \begin{matrix} 1 & 2 \\ 2 & 3 \\ \end{matrix} $$

在样例 $2$ 中，显然无法通过操作从初始表格中得到元素总和为 $5$ 的表格，因为初始表格全部都是 $2$，而 $5$ 是一个奇数。

在样例 $3$ 中，最初给定的表格是：

$$\begin{matrix} 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 \\ \end{matrix} $$

删除最后两行和第一列后，我们得到以下表格，其元素总和为 $34$：

$$\begin{matrix} 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 \\ \end{matrix} \rightarrow \begin{matrix} 1 & 2 & 1 & 4 & 5 \\ 2 & 5 & 4 & 1 & 2 \\ 4 & 2 & 4 & 3 & 1 \\ 1 & 2 & 4 & 5 & 2 \\ \end{matrix} \rightarrow \begin{matrix} 1 & 2 & 1 & 4 & 5 \\ 2 & 5 & 4 & 1 & 2 \\ 4 & 2 & 4 & 3 & 1 \\ \end{matrix} \rightarrow \begin{matrix} 2 & 1 & 4 & 5 \\ 5 & 4 & 1 & 2 \\ 2 & 4 & 3 & 1 \\ \end{matrix} $$

子任务	分值	特殊性质
$0$		同样例
$1$	$17$	$h=1$
$2$	$6$	第 $i$ 行中的数字和不超过 $i$
$3$	$10$	$h\le3$
$4$	$13$	$h,w\le10$
$5$		$h,w\le12$
$6$	$12$	$A_{i,j}\le6$
$7$	$29$	无

对于 $100\%$ 的数据，$1 \leq h, w \leq 15$，$0 \leq A_{i,j} \leq 10^9$，$1 \leq s \leq 10^{18}$。