BajtocjaとBitocjaは、長年の無意味な戦争の末、ついに平和条約に署名しました。両国の首都を結ぶ高速道路が建設され、あなたはBajtocjaからBitocjaへ向かう高速道路の管理者に任命されました。
現在、高速道路には $m$ 個の料金所があり、1から $m$ まで順に番号が振られています。最初の料金所は高速道路の入り口に、最後の料金所は出口にあります。料金所を通過するコストは、時間帯によって異なる場合があります。1日は $n$ 時間に分割されており、1から $n$ まで番号が振られています。現在、時間 $i$ における料金所 $j$ の通過コストは $c_{i,j}$ バジタラーです。これらのコストの中には $0$ （通過無料）や負の値（ドライバーが通過時に $-c_{i,j}$ バジタラーを受け取る）であるものも含まれます。
高速道路は非常に短く、1時間以内に通過可能です。もちろん、急ぐ必要はなく、走行中に何度でも停車できます。ただし、高速道路上で宿泊することはできません。すべての料金所は同じ日のうちに通過しなければなりません。
当然、ドライバーは可能な限り低いコストで高速道路を通過したいと考えています。$1 \le i \le j \le n$ に対し、$f(i, j)$ を、ドライバーが最初の料金所を時間 $i$ に、最後の料金所を時間 $j$ に通過する場合の、高速道路全区間の通過にかかる最小コストと定義します。すべての $f(i, j)$ の値は平和条約により両国政府によって決定されており、高速道路の管理者であるあなたはこれらを変更することはできません。しかし、あなたは各料金所の料金表を自由に変更したり、一部の料金所を完全に閉鎖したりすることができます。ただし、最初と最後の料金所は開いたままにしておく必要があり、$f(i, j)$ の値は変更されてはならず、あなたが設定するすべてのコストは1バジタラーの整数倍でなければなりません。
高速道路の維持コストを最小化するために、できるだけ多くの料金所を閉鎖したいと考えています。条約の条件を満たしたまま残すべき料金所の最小数を求めてください。
料金徴収システムの再編プロジェクトは2つのフェーズで構成されます。第1フェーズ（初期設計）では、最適な料金所の数を見つけるだけで十分です。しかし、第2フェーズ（実装フェーズ）では、残された料金所に対する完全な料金表の例を提示する必要があります。
入力
入力の最初の行には、3つの整数 $n, m, q$ ($2 \le n, m \le 30\,000$; $n \cdot m \le 300\,000$; $q \in \{0, 1\}$) が含まれており、それぞれ1日の時間数、現在の高速道路上の料金所数、プロジェクトのフェーズを表すビットです。$q = 0$ はプロジェクトの第1段階（初期設計）を意味し、$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$ の通過コスト（バジタラー単位）です。$c_{i,j}$ が負の場合、ドライバーは $j$ 番目の料金所を時間 $i$ に通過する際に $-c_{i,j}$ バジタラーを受け取ります。
出力
出力の最初の行には、すべての $f(i, j)$ の値を変更せずに高速道路に残すべき料金所の最小数 $k$ ($2 \le k \le m$) を出力してください。$q = 0$ の場合、出力はこの1つの数値のみを含む1行で構成される必要があります。
$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}$ を超えない整数でコストを決定することが常に可能であることが証明できます。
入出力例
入力 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$.
これらの通過コストは、2つの料金所のみを使用して実現することはできません。提案されたコスト $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
2番目のテストケースでは、プロジェクトが初期段階であるため、出力に新しい料金表の提案は含まれていません。
小課題
- 全得点の半分に相当するテストケースでは、$q = 0$ を満たします。
- 残りのテストケースでは常に $q = 1$ を満たします。