3. Игра с таблицей
ограничение по времени на тест
1 с
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана таблица $$$A$$$ из $$$h$$$ строк и $$$w$$$ столбцов, в каждой ячейке которой записано целое число. Строки пронумерованы от $$$1$$$ до $$$h$$$ сверху вниз, столбцы пронумерованы от $$$1$$$ до $$$w$$$ слева направо.

Разрешается применять к этой таблице следующие операции:

  • выбрать столбец таблицы и удалить его (столбцы слева и справа от него становятся соседними);
  • выбрать строку таблицы и удалить ее (строки сверху и снизу от нее становятся соседними).

Эти операции разрешается применить произвольное число раз в любом порядке.

Определите, возможно ли при помощи этих операций получить из исходной таблицу с суммой чисел, равной заданному числу $$$s$$$, и если да, то какие операции и в каком порядке необходимо применить.

Входные данные

Первая строка ввода содержит числа $$$h$$$ и $$$w$$$ — размеры таблицы ($$$1 \leq h, w \leq 15$$$).

Каждая из следующих $$$h$$$ строк содержит по $$$w$$$ целых чисел — таблицу $$$A$$$ ($$$0 \leq A_{i,j} \leq 10^{9}$$$).

В последней строке ввода находится число $$$s$$$ — необходимая сумма ($$$1 \leq s \leq 10^{18}$$$).

Выходные данные

Если получить таблицу с суммой чисел $$$s$$$ из исходной невозможно, выведите строку «NO».

Иначе:

  • В первой строке выведите строку «YES».
  • Во второй строке выведите единственное число $$$k$$$ — количество операций с таблицей, которые необходимо применить, чтобы получить из неё таблицу с суммой чисел $$$s$$$.
  • В каждой из следующих $$$k$$$ строк выведите по два целых числа $$$t_{j}, i_{j}$$$, где $$$t_{j} = 1$$$, если очередная операция производится со строкой, и $$$t_{j}=2$$$, если она производится со столбцом таблицы. Число $$$i_{j}$$$ должно быть равно номеру строки или столбца, соответственно, в исходной нумерации, с которой эта операция производится.
Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

|c|c|}

Подзадача

Баллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
117 $$$h = 1$$$первая ошибка
26 сумма чисел в $$$i$$$-й строке не превосходит $$$i$$$первая ошибка
310 $$$h \leq 3$$$1первая ошибка
413 $$$h,w \leq 10$$$первая ошибка
513 $$$h, w \leq 12$$$4первая ошибка
612 $$$a_{i, j} \leq 6$$$первая ошибка
7291–6первая ошибка
Примеры
Входные данные
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
Примечание

В первом примере изначально дана следующая таблица:

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

Удалив третьи строку и столбец получим таблицу с суммой чисел $$$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}$$$

Во втором примере можно показать, что разрешенными операциями невозможно получить таблицу с суммой чисел $$$5$$$ из исходной.

В третьем примере изначально дана таблица:

$$$\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}$$$

Удалив последние две строки и первый столбец, получим таблицу с суммой чисел $$$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}$$$