大青鱼和小青鱼经过多年毫无意义的战争之后，终于签署了和平条约。为了象征两国彻底和解，从青鱼国首都到小青鱼国首都修建了一条高速公路，而你被委派管理这条高速公路上的收费站。

这条高速公路上总共有 $ m $ 个收费站，第一个收费站位于高速公路起点，最后一个收费站位于高速公路终点。每天被划分成 $ n $ 个小时，第 $ i $ 个小时通过第 $ j $ 个收费站的通行费用为 $ c_{i,j} $ 个“青鱼币”。值得注意的是，这个费用可能在一天的不同时间存在变化，甚至可能是负数（此时代表司机可以获得一定数量的青鱼币作为奖励）。

整条高速公路非常短，以至于可以在一小时内完成全部通行。当然，司机不一定需要赶路，可以在中途做任意次数的停留休息，但不能在公路上过夜，所有收费站都必须在同一天内通过。

为了维护青鱼两国签署的和平条约，双方政府已经共同确定了所有可能的最优通行费用，即从第一个收费站通过的时间为第 $ i $ 小时，到达最后一个收费站的时间为第 $ j $ 小时时，最低可能费用为 $ f(i,j) $。作为公路管理者，你不能改变这些费用。但你被允许调整中间收费站的收费标准，甚至可以关闭一些收费站，但必须满足：

• 第一个收费站和最后一个收费站必须保持开放；
• 所有最低费用 $ f(i,j) $ 不能因你的调整而改变；
• 新的收费标准必须为整数倍的青鱼币。

为了最大程度地节约维护成本，你希望关闭尽可能多的收费站。请你确定，在不改变任何 $ f(i,j) $ 的情况下，必须保留的最少收费站数量。

收费站重整项目共分两个阶段：

• 第一阶段（$ q=0 $）：只需给出必须保留的最少收费站数量；
• 第二阶段（$ q=1 $）：还需给出具体的新收费标准方案。

输入格式

第一行包含三个整数 $ n, m, q $（$2 \le n, m \le 30000; n \cdot m \le 300000; q \in \{0,1\}$），分别代表一天内小时数、高速公路上的收费站数量，以及当前项目阶段。

接下来 $ n $ 行，每行 $ m $ 个整数 $ c_{i,1}, c_{i,2}, \dots, c_{i,m} $（$-10^6 \le c_{i,j} \le 10^6$），代表第 $ i $ 小时通过第 $ j $ 个收费站的费用。

输出格式

输出一行一个整数 $ k $（$ 2 \le k \le m $），表示在满足所有约束的前提下必须保留的最少收费站数量。

若 $ q=1 $，还需额外输出新的收费方案，共 $ n $ 行，每行包含 $ k $ 个整数 $ d_{i,1}, d_{i,2}, \dots, d_{i,k} $（$-10^{12}\le d_{i,j}\le 10^{12}$），表示第 $ i $ 小时通过第 $ j $ 个保留收费站的通行费用。

注意：来自“小青鱼国”到“青鱼国”的方向收费情况不在你的职责范围内，由“大青鱼国”派出的友好使节负责管理。

样例数据

input

7 7 0
7 -13 4 -6 -14 1 -3
13 -14 6 -7 -15 12 -2
12 -14 5 -6 -10 11 -15
-6 -14 6 -1 -9 9 12
7 -14 7 0 -11 7 -5
9 -15 10 -3 -12 5 7
1 -13 7 -5 -14 3 9

output

6

子任务

子任务一（3 分）

$q = 0$

子任务二（4 分）

没有额外的限制。