Байтония и Битония после долгих лет бессмысленных войн наконец подписали мирный договор. В знак окончательного примирения между столицами государств была построена автомагистраль. Вы были назначены управляющим участка автомагистрали, ведущего из Байтонии в сторону Битонии.
На автомагистрали в настоящее время находится $m$ пунктов оплаты, пронумерованных от $1$ до $m$. Первый из них находится в начале автомагистрали, а последний — в конце. Стоимость проезда через конкретный пункт может меняться в разное время суток. Сутки разделены на $n$ часов, пронумерованных от $1$ до $n$. В настоящее время стоимость проезда через пункт $j$ в час $i$ составляет $c_{i,j}$ байталеров. Некоторые из этих стоимостей могут быть равны $0$ (проезд через пункт в этом случае бесплатный) или даже отрицательными (водитель в этом случае получает $-c_{i,j}$ байталеров за проезд через пункт).
Вся автомагистраль настолько коротка, что её можно проехать в течение одного часа. Однако, конечно, не обязательно так спешить — во время поездки можно сделать любое количество остановок. Однако нельзя ночевать на автомагистрали; через все пункты нужно проехать в один и тот же день.
Разумеется, водители хотят проехать по автомагистрали с минимально возможными затратами. Через $f(i, j)$ для $1 \le i \le j \le n$ мы обозначаем минимально возможную стоимость проезда по всей автомагистрали, если через первый пункт водитель проезжает в час $i$, а через последний пункт — в час $j$. Все значения $f(i, j)$ были установлены в мирном договоре правительствами обеих стран, поэтому как управляющий автомагистралью вы не можете их изменить. Однако вы можете произвольно изменять тарифы на проезд через отдельные пункты или даже полностью закрыть часть пунктов, при условии, что первый и последний пункты останутся открытыми, значения $f(i, j)$ не изменятся, а все установленные вами стоимости будут целыми кратными одного байталера.
Чтобы минимизировать расходы на содержание автомагистрали, вы хотите закрыть как можно больше пунктов. Определите минимальное количество пунктов, которые должны остаться открытыми, чтобы по-прежнему соблюдались условия договора.
Проект реорганизации схемы оплаты будет состоять из двух фаз. В первой фазе — предварительном проекте — достаточно найти само оптимальное количество пунктов. Однако во второй фазе — фазе реализации проекта — вы должны дополнительно предоставить весь примерный прейскурант для оставшихся пунктов.
Входные данные
В первой строке входных данных находятся три целых числа $n, m$ и $q$ ($2 \le n, m \le 30\,000$; $n \cdot m \le 300\,000$; $q \in \{0, 1\}$), обозначающие соответственно количество часов в сутках, текущее количество пунктов оплаты на автомагистрали и бит, описывающий фазу проекта. Значение $q = 0$ означает первый этап проекта (предварительный проект), а значение $q = 1$ означает, что проект уже находится в фазе реализации.
Следующие $n$ строк содержат описание текущих оплат; $i$-я из них содержит $m$ целых чисел $c_{i,1}, c_{i,2}, \dots, c_{i,m}$ ($-10^6 \le c_{i,j} \le 10^6$). Значение $c_{i,j}$ означает стоимость проезда через пункт $j$ в час $i$, выраженную в байталерах. Если значение $c_{i,j}$ отрицательное, то за проезд через $j$-й пункт в час $i$ водитель получает $-c_{i,j}$ байталеров.
Выходные данные
В первой строке выходных данных должно находиться одно целое число $k$ ($2 \le k \le m$), обозначающее минимальное количество пунктов, которое нужно оставить на автомагистрали, чтобы ни одно значение $f(i, j)$ не изменилось. Если $q = 0$, выходные данные должны состоять только из одной строки, содержащей только это число.
Если $q = 1$, в следующих $n$ строках должен находиться примерный оптимальный прейскурант, удовлетворяющий условиям задачи. В $i$-й из этих строк должно находиться $k$ целых чисел $d_{i,1}, d_{i,2}, \dots, d_{i,k}$ ($-10^{12} \le d_{i,j} \le 10^{12}$). Значение $d_{i,j}$ означает новую стоимость проезда через $j$-й из оставшихся пунктов в час $i$.
Можно доказать, что для ограничений задачи всегда возможно определение стоимостей, являющихся целыми числами, абсолютные значения которых не превышают $10^{12}$.
Подзадачи
- В тестах, оцениваемых в половину баллов, выполняется условие $q = 0$.
- В остальных тестах всегда выполняется условие $q = 1$.
Примеры
Пример 1
Входные данные
3 6 1 -1 0 4 0 -3 0 -4 1 5 2 -5 2 -5 2 3 0 -2 2
Выходные данные
3 0 0 0 0 1 0 0 0 0
Пример 2
Входные данные
5 7 0 0 0 0 8 0 0 0 0 7 6 5 9 7 0 0 0 0 5 9 6 0 9 4 0 4 4 7 0 0 0 0 9 8 6 0
Выходные данные
3
Примечание
Пояснение к примеру: В первом тестовом примере отдельные минимальные стоимости проезда по автомагистрали следующие: $f(1, 1) = (-1) + 0 + 4 + 0 + (-3) + 0 = 0$, $f(1, 2) = (-1) + 0 + 4 + 0 + (-5) + 2 = 0$, $f(1, 3) = (-1) + 0 + 4 + 0 + (-5) + 2 = 0$, $f(2, 2) = (-4) + 1 + 5 + 2 + (-5) + 2 = 1$, $f(2, 3) = (-4) + 1 + 3 + 0 + (-2) + 2 = 0$, $f(3, 3) = (-5) + 2 + 3 + 0 + (-2) + 2 = 0$.
Таких же стоимостей проезда невозможно добиться при использовании двух пунктов. Обратите внимание, что первый и последний пункты не могут быть закрыты, несмотря на то, что при предложенных стоимостях $d_{i,j}$ на этих пунктах не взимается никакой платы.
Во втором тестовом примере выходные данные не содержат предложения нового прейскуранта, так как проект реорганизации схемы оплаты находится только на предварительной стадии.