题目背景

PA 2024 5A1 （缺 SPJ）

题目描述

题目译自 PA 2024 Runda 5 Autostrada 2

经过多年毫无意义的战争之后，Byteotia 和 Bitotia 终于签署了和平条约。作为最终协议的标志，两国首府之间修建了一条高速公路。而你则被任命为这条高速公路从 Byteotia 到 Bitotia 方向的管理者（至于从 Bitotia 到 Byteotia 方向，你并不感兴趣，它由不友好国家的管理者管理）。

高速公路上目前有 $m$ 个收费站，编号为 $1$ 到 $m$。在一天的不同时段，通过某个收费站的费用会有所不同。一天分为 $n$ 个小时，编号为 $1$ 到 $n$。目前，在第 $i$ 个小时通过第 $j$ 个收费站的花费为 $c_{i,j}$ bytealerts。其中一些成本可能为 $0$（此时收费站免费），甚至为负（此时司机通过收费站会获得 $-c_{i,j}$ bytealerts）。

整条高速公路很短，一小时就能走完。当然，你也不必如此匆忙，你可以在行驶过程中随意停车。不过，你不能在高速公路上过夜，必须在当天通过所有收费站。

当然，司机希望以尽可能低的花费通过高速公路。对于 $1 \le i \le j \le n$，我们用 $f(i,j)$ 表示司机在第 $i$ 小时通过第一个收费站，并在第 $j$ 小时通过最后一个收费站的情况下，通过整条高速公路的最小可能花费。所有 $f(i,j)$ 都是被两国政府的和平条约提前设置好的，作为高速公路管理者你不能更改他们。

但是，只要保证保留第一个和最后一个收费站，$f(i, j)$ 的值保持不变，并且设置的所有费用都是 $1$ bytealert 的整数倍的情况下，你可以自由修改通过各个收费站的花费，甚至取消某些收费站。

为了最小化高速公路维护的费用，你希望取消尽可能多的收费站。确定为了满足条约内容，最少需要保留多少收费站。

收费计划重组项目将分为两个阶段。在第一阶段，即初步设计阶段，只需找到最佳的收费站数量即可。但在第二阶段，即项目实施阶段，你还需要提供一份完整的收费站价格表计划。

输入格式

第一行三个整数 $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},\ldots,c_{i,m}\ (-10^6\le c_{i,j}\le 10^6)$，意义如题目描述。

输出格式

第一行输出一个整数 $k\ (2\le k\le m)$，表示最少需要保留多少收费站，才能满足没有 $f(i,j)$ 改变。如果 $q=0$，输出仅包含这一行一个整数。

如果 $q=1$，接下来 $n$ 行输出满足题目条件的最优价格计划。第 $i$ 行包含 $k$ 个整数 $d_{i,1},d_{i,2},\ldots,d_{i,k}\ (-10^{12}\le d_{i,j}\le 10^{12})$。$d_{i,j}$ 表示在第 $i$ 小时通过第 $j$ 个收费站的新花费。

可以从题目限制知道，总可以确定一个绝对值不超过 $10^{12}$ 且花费均为整数的计划。

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

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(i,j)$ 如下：

$$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}$ 费用，这两个收费站是不收费的。

在第二个样例中，由于收费计划重组草案仅处于初步阶段，因此输出不包含新价目表的计划。

数据范围与提示

• 有一半的子任务满足 $q=0$。
• 另一半子任务满足 $q=1$。