P10362 [PA 2024] Autostrada 2

PA 2024 5A1 （缺 SPJ）

**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 5 [Autostrada 2](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/aut/)** 经过多年毫无意义的战争之后，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}$ 且花费均为整数的计划。

第一个样例中，$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$。