Bajtocja 和 Bitocja 在经历了多年毫无意义的战争后，终于签署了和平条约。为了象征最终的和平，两国首都之间修建了一条高速公路。你被任命为从 Bajtocja 通往 Bitocja 方向的高速公路路段的管理者。
目前高速公路上有 $m$ 个收费站，依次编号为 $1$ 到 $m$。第一个收费站位于高速公路起点，最后一个位于终点。通过某个收费站的费用在一天中的不同时间可能有所不同。一天被分为 $n$ 个小时，编号为 $1$ 到 $n$。目前，在 $i$ 时刻通过 $j$ 号收费站的费用为 $c_{i,j}$ Bajtalar。其中一些费用可能为 $0$（此时通过收费站免费），甚至为负数（此时司机通过收费站可获得 $-c_{i,j}$ Bajtalar）。
整条高速公路很短，可以在一小时内跑完全程。当然，司机不必如此匆忙——在行驶过程中可以进行任意多次停留。但不能在高速公路上过夜；必须在同一天内通过所有收费站。
显然，司机希望以尽可能低的成本通过高速公路。对于 $1 \le i \le j \le n$，我们用 $f(i, j)$ 表示如果司机在 $i$ 时刻通过第一个收费站，并在 $j$ 时刻通过最后一个收费站时，通过整条高速公路的最小可能成本。所有 $f(i, j)$ 的值均已由两国政府在和平条约中确定，因此作为高速公路管理者，你不能更改它们。然而，你可以随意修改各个收费站的通行费价格，甚至可以完全关闭部分收费站，前提是第一个和最后一个收费站必须保持开放，且 $f(i, j)$ 的值保持不变，并且你设定的所有费用必须是 $1$ Bajtalar 的整数倍。
为了最大限度地降低高速公路的维护成本，你希望关闭尽可能多的收费站。请确定为了继续满足条约条件，必须保持开放的收费站的最小数量。
收费站收费方案的重组项目将分为两个阶段。在第一阶段（初步设计）中，你只需要找到最优的收费站数量。但在第二阶段（项目实施阶段），你还必须为保留下来的收费站提供一份完整的示例价目表。
输入格式
输入的第一行包含三个整数 $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}$ 的值表示在 $i$ 时刻通过 $j$ 号收费站的费用，单位为 Bajtalar。如果 $c_{i,j}$ 为负，则表示司机通过 $j$ 号收费站时可获得 $-c_{i,j}$ Bajtalar。
输出格式
第一行应包含一个整数 $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}$ 的值表示在 $i$ 时刻通过保留下来的第 $j$ 个收费站的新费用。
可以证明，对于题目中的限制条件，总是可以确定绝对值不超过 $10^{12}$ 的整数费用。
样例
输入 1
3 6 1 -1 0 4 0 -3 0 -4 1 5 2 -5 2 -5 2 3 0 -2 2
输出 1
3 0 0 0 0 1 0 0 0 0
说明 1
在第一个测试样例中，通过高速公路的各个最小成本如下： $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}$ 下，这些收费站不收取任何费用。
输入 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
输出 2
3
说明 2
在第二个测试样例中，输出不包含新价目表的建议，因为收费方案重组项目仅处于初步阶段。
子任务
- 在分值为总分一半的测试中，满足条件 $q = 0$。
- 在其余测试中，始终满足条件 $q = 1$。