AT_njpc2017_d NMパズル

[problemUrl]: https://atcoder.jp/contests/njpc2017/tasks/njpc2017_d あなたはNMパズルと呼ばれるパズルゲームで遊んでいる。 このゲームは、$ 1 $ から $ NM $ までの整数のうち一つが書かれたカード $ NM $ 枚と、$ N $ 行 $ M $ 列の盤面を用いて行われる。ここで、カードに書かれた整数に重複は無い。 このゲームの目的は、スコアが $ K $ となるようにカードを配置することである。 盤面上の全てのマスにちょうど1枚ずつカードを配置した時、(各行の転倒数の和) + (各列の転倒数の和)がスコアとなる。 スコアがちょうど $ K $ となるようなカードの配置を一つ出力しなさい。 なお、条件を満たす出力が複数ある場合、どれを出力しても良い。 ここで、転倒数は以下のように定義される。 $ C_{ij} $ は盤面の $ i $ 行 $ j $ 列目のマスに配置するカードに書かれた整数を表す。ただし、左上を $ 1 $ 行 $ 1 $ 列目、右下を $ N $ 行 $ M $ 列目とする。 - 行 $ i\ (1\ ≦\ i\ ≦\ N) $ の転倒数とは、 $ 1\ ≦\ j\ \ C_{ij’} $ を満たす組 $ (j,\ j’) $ の個数である。 - 列 $ j\ (1\ ≦\ j\ ≦\ M) $ の転倒数とは、 $ 1\ ≦\ i\ \ C_{i’j} $ を満たす組 $ (i,\ i’) $ の個数である。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $

条件を満たすカードの配置を以下の形式に従って標準出力に出力せよ。 - $ C_{ij} $ は盤面の $ i $ 行 $ j $ 列目のマスに配置するカードに書かれた整数を表す。 - 整数と整数は1つの半角スペースで区切られている。 - $ C_{ij} $ は互いに異なり、$ 1 $ から $ NM $ までの整数でなければならない。 - $ C_{ij} $ は以下のように $ N $ 行 $ M $ 列で出力する。 > $ C_{11} $ $ C_{12} $ $ … $ $ C_{1M} $ $ C_{21} $ $ C_{22} $ $ … $ $ C_{2M} $ $ : $ $ C_{N1} $ $ C_{N2} $ $ … $ $ C_{NM} $

### 制約 - 入力は全て整数である。 - $ 1\ ≦\ N,\ M\ ≦\ 100 $ - $ 0\ ≦\ K\ ≦\ NM(M-1)/2\ +\ MN(N-1)/2 $ - スコアが $ K $ となるようなカードの配置は必ず存在する。 ### Sample Explanation 1 このように配置すると、転倒数は1行目が2, 2行目が1, 1列目が1, 2列目が0, 3列目が1となるため、スコアは5となり条件を満たす。 なおこれは出力例であり、他にも条件を満たす出力は存在する。