P11122 [ROIR 2024] 表格游戏 (Day 1)

翻译自 [ROIR 2024 D1T3](https://neerc.ifmo.ru/school/archive/2023-2024/ru-olymp-regional-2024-day1.pdf)。 给定一个有 $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$ 应为操作所针对的行或列的初始编号。

在样例 $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$ | $0$ | 同样例 | | $1$ | $17$ | $h=1$ | | $2$ | $6$ | 第 $i$ 行中的数字和不超过 $i$ | | $3$ | $10$ | $h\le3$ | | $4$ | $13$ | $h,w\le10$ | | $5$ | $13$ | $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}$。