問題文

妖精研究家のXは、とある庭園に出現する虹色に光り輝く妖精の研究に長年打ち込んでいます。
妖精は毎夜、庭園のある場所に出現し、別のある場所へと最短経路で飛んでいき、そこで消えるという習性を持っていることがわかっています。
長年の研究の結果、妖精の出現パターンを完璧に予想できるようになったXは、今度はできるだけ長い時間妖精を観察したいと考えています。
具体的には庭園に壁を作ったり壊したりして妖精の移動経路を操作し、後述の満足度をできるだけ大きくしようとしています。
ただし、1日に1つの壁しか作ったり壊したりできないため、Xはすぐれた作業計画を考えようとしています。

Xが行おうとしている妖精の観察は以下のような条件になっています。

• 妖精の出現する庭園は N × N のグリッドからなっており、グリッドの各セルは空か壁のどちらかである。
  • 上から r 行目、左から c 列目のセルを (r,\ c) と表す。( 0 ≤ r,\ c < N )
• 初期状態ではすべてのセルは空である。また、満足度は 0 である。
• 妖精の観察は K 日間行い、各日に作業と満足度の計算を以下の順番で行う。
1. 任意のセルを1つ選んでそのセルが空だったら壁に、壁だったら空に変化させる。もしくはなにもしない。セルの状態は次の日以降も引き継がれる。
2. 妖精の出現するセル (a_{i},\ b_{i}) から消えるセル (c_{i},\ d_{i}) まで、妖精が空のセルだけを上下左右に1セルずつ辿って到達する経路があれば、その最短経路の (出現するセルと消えるセルを含めて通過したセルの数\ -\ 1)^2 を満足度として加える。
   • 到達できない場合は妖精は出現せず、満足度は変化しない。
   • (a_{i},\ b_{i}) と (c_{i},\ d_{i}) の少なくとも一方が壁の場合は妖精は出現せず、満足度は変化しない。
   • 妖精はグリッドの外を通過できない。

テストケースの生成について

各ケースはテストケースジェネレータによって生成されています。
テストケースジェネレータは一様乱数にしたがってケースを生成しています。
テストケースジェネレータはページ下部のリンクより提供しています。

入力例1

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

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

出力例1

3 0
-1 -1
4 1
4 1

出力された操作に基づいた各日の庭園の状態と妖精の飛行経路は以下のようになります。

2日目は妖精の出現するセルから消えるセルまで到達できないので、妖精は出現せず、満足度は変化しません。
このテストケースの得点は最終日の満足度 86 を 10000 で割って切り上げした値なので 1 になります。
（画像中のSとGはそれぞれ妖精の出現するセルと消えるセルを表しています）

ジェネレータとテスター

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

ジェネレータ・テスター

ビジュアライザ

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

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

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

ビジュアライザ