問題文

パズル愛好家のXは、自ら考案した新しいパズルを解こうとしています。

Xの考案したパズルは $N × N$ のグリッドからなっており、一番左上、右上、左下、右下のセルの座標をそれぞれ $(0,\ 0),\ (0,\ N-1),\ (N-1,\ 0),\ (N-1,\ N-1)$ と表します。
ここで、グリッド内のあるセルの座標を $(r,\ c)$ としたとき、下記に定義されるいずれかの領域にあると呼ぶことにします。

• $r < N/2$ かつ $c < N/2$ ならば、左上領域。
• $r < N/2$ かつ $c \geq N/2$ ならば、右上領域。
• $r \geq N/2$ かつ $c < N/2$ ならば、左下領域。
• $r \geq N/2$ かつ $c \geq N/2$ ならば、右下領域。

このパズルでは以下の操作を行うことができます。

• グリッド内のある正方形のサブグリッドを選択し、その内部を時計回りに90度回転させる。

上記操作を最大 $M$ 回まで行って、グリッドの左上領域に赤を、右上領域に黄を、左下領域に緑を、右下領域に青を集めるのがこのパズルの目標です。

パズルを考案するのは得意でも解くのは苦手なXの代わりに、どういう操作を行えばよいか考えてあげてください。

各テストケースの得点および、この問題の得点は、次のように計算されます。

• 1つのテストケースの得点は、次のように計算されます。
• すべての操作が終了したグリッドで、
  ${\it 左上領域にある赤セル数}\ +\$${\it 右上領域にある黄セル数}\ +\$${\it 左下領域にある緑セル数}\ +\$${\it 右下領域にある青セル数}$
  を得点とする。
• すべての赤セルが左上領域に、黄セルが右上領域に、緑セルが左下領域に、青セルが右下領域に集まっている場合、これを完全解と呼び、$M - {\it 操作回数}$ を得点に加える。
• テストケースは全部で $50$ 個あります。各テストケースの得点の合計が、この問題の得点になります。

入力例1Copy

4 1000
3 2 3 2
3 3 1 0
1 1 0 1
0 0 2 2

注意: この入力はテストケースとしての制約を満たしていません。

出力例1Copy

0 0 3
0 1 3
1 1 2
0 0 4

初期状態から最終操作後までの各グリッドのビジュアライズ結果を以下に図示しています。

初期状態

操作 (0 0 3) 後

操作 (0 1 3) 後

操作 (1 1 2) 後

操作 (0 0 4) 後

完全解を達成しているので、このサンプルでの得点は、$4 + 4 + 4 + 4 + (1000 - 4) = 1012$ になります。

ジェネレータとテスターとサンプル入力データ

テストケースジェネレータ・テスター・サンプル入力データを次のリンクから提供しています。

ジェネレータ・テスター・サンプル入力データ

ヒント：サブグリッドを回転させる処理は、テスターの中に実装があります。参考にしてください。

ビジュアライザ

入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。

• このビジュアライザはデスクトップ版の Google Chrome および Mozilla Firefox の最新バージョン上で動作確認を行っています。全てのブラウザ環境で動作することを保証していません。
• このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。
• このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。

ビジュアライザは次のリンクからも提供しています。使用法についてもリンク先に記述があります。

ビジュアライザ