A - Replace() は Replace() されました

解説を見る
  • 実行時間制限：3000 ms
  • メモリ制限：1073741824 Bytes
  • 配点：1000000000 点
  • ジャッジ：Batch

問題文

あなたは、サイズ N×NN \times N の数値グリッドを扱います。
各マス (i,j)(i, j) には整数値が書かれており、初期状態のグリッドを AA、目標状態のグリッドを BB とします。

あなたの目的は、与えられた一連の操作を用いて、グリッド AA をできるだけ BB に近づけることです。

操作

あなたには TT 種類の置換操作 Replace が与えられます。
それぞれの操作は次の形式で表されます：

ReplaceH,W,a,bReplace_{H, W, a, b}

この操作は次の手順で適用できます：

  1. グリッド上の任意のマス (x,y)(x, y) を選ぶ。
  2. その位置を左上とする H×WH \times W の矩形領域を考える（ただし範囲外に出る場合は選べない）。
  3. その矩形内に含まれるすべてのセルのうち、値が aa であるものを bb に変更する。

制約

  • 各操作 ReplaceH,W,a,bReplace_{H, W, a, b} は 最大3回まで 使用することができます。
  • 操作の順番や適用位置は自由に選べます。

目標

最終的に得られたグリッドを A′A' とします。
あなたの目的は、A′A' を BB にできるだけ近づけることです。

スコア

操作回数の総和を LL 、テストケースの個数を QQ として、スコアは次の式で計算されます：

Score=109Q×N2N2+L+∑i=0N−1∑j=0N−1(Ai,j′−Bi,j)2\text{Score} = \frac{10^9}{Q} \times \frac{N^2}{N^2 + L + \sum_{i=0}^{N-1} \sum_{j=0}^{N-1} (A'_{i,j} - B_{i,j})^2}

スコアは高いほどよいです。
後述のビジュアライザで表示される点数は、この QQ 倍です。

入力

N TN~T


A0,0 A0,1 ⋯ A0,N−1A_{0,0}~A_{0,1}~\cdots~A_{0,N-1}


⋮\vdots


AN−1,0 ⋯ AN−1,N−1A_{N-1,0}~\cdots~A_{N-1,N-1}


B0,0 B0,1 ⋯ B0,N−1B_{0,0}~B_{0,1}~\cdots~B_{0,N-1}


⋮\vdots


BN−1,0 ⋯ BN−1,N−1B_{N-1,0}~\cdots~B_{N-1,N-1}


H0 W0 a0 b0H_0~W_0~a_0~b_0


⋮\vdots


HT−1 WT−1 aT−1 bT−1H_{T-1}~W_{T-1}~a_{T-1}~b_{T-1}

出力

<Length><Length>


<opid> <x> <y><op_id>~<x>~<y>


⋮\vdots

Length≤105\text{Length} \leq 10^5 である必要があります。

制約

  • 15≤N≤6015\leq N\leq 60
  • T=3000T=3000
  • 0≤Ai,j,Bi,j,a,b<500\leq A_{i, j}, B_{i, j}, a, b< 50
  • 0<H,W≤N0< H, W\leq N

ビジュアライザ

この問題をシミュレーションする ビジュアライザ が利用可能です。
また、このビジュアライザで使用可能なシード値によるジャッジが行われます。

システムジャッジ

テストケースに偏りがあるのを防ぐため、最終的に 300 個のシードによりジャッジを行うことを予定しています。
もしかしたらやるし、もしかしたらやらないです。
やる場合はコンテスト中に提出された最後の CE 以外の提出に対して行われます。
そのシード値を載せたリスト（seeds.txt）は終了後に公開されます。