You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

表格游戏

题目背景

给定一个有 $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

样例输入 #1

2 3
2 2 2
2 2 2
5

样例输出 #1

NO

提示

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

先输出行删除，在输出列删除，且删除序号按顺序排序.