運営者Note

問題文

サイズ $N\times N$ のグリッドがあります．グリッドのセルは，純白か漆黒に塗られています．
上から $y$ 番目左から $x$ 番目のセル $(y,x)$ が純白であるとき $A_{y,x} = 0$ ，漆黒である時 $A_{y,x} = 1$ です．

このグリッドに対して$K$回の操作を行います．
$i$ 回目の操作では，グリッド内の高さ $L_i$ 幅 $1$ 、または高さ $1$ 幅 $L_i$ の長方形（すなわち縦長・横長のどちらか）を選択し，
長方形の領域内の純白のセルを漆黒に，漆黒のセルを純白に反転させます．

操作前の純白のセルの数を$W_0$，$K$ 回の操作後の純白のセルの数を$W_K$とすると，得点は $W_K-W_0$ になります．
得点がなるべく高くなるような長方形の配置を求めてください．

スコア問題なので，最適解を求める必要はありません．

スコアは全ケースの得点の合計になります。テストケースは32個です。

入力

$N$ $K$
$L_1$ $\ldots$ $L_K$
$A_{1,1}$ $\ldots$ $A_{1,N}$
$\ldots$
$A_{N,1}$ $\ldots$ $A_{N,N}$

$N = 60$
$K = 500$
$1 \le L_i \le 25$
$A_{i,j} \in \{0,1\}$

全て整数である．
$A_{i,j}$, $A_{i,k}$間はスペースなどの区切りはない.

テストケース生成方法について

テストケースは全てランダムに生成されたものです．人為的なテストケース（真っ白等）はありません．

• $L_i$ は制約を満たす値の中で等確率で選ばれます．
• 各セルは1/2の確率で漆黒のセルとして生成されます．

出力

$a_1$ $b_1$ $c_1$ $d_1$
$\ldots$
$a_K$ $b_K$ $c_K$ $d_K$

$1 \le a_i \le c_i \le N$
$1 \le b_i \le d_i \le N$
$a_i=c_i, d_i-b_i+1=L_i$ または $b_i=d_i, c_i-a_i+1=L_i$ を満たす必要がある．

$K$ 行出力してください．
$i$ 行目は， $i$ 番目の操作として $長方形(a_i,b_i,c_i,d_i)$ を選択することを意味します．
ただし $長方形(a,b,c,d)$ とは，セルの集合 $\{(y,x)|a\le y\le c,b \le x\le d\}$ です．

スコア問題です．
フォーマットを満たせばACしますが，なるべく高いスコアを目指してください．

ビジュアライザ

ビジュアライザはこちら

注意:標準出力の末尾には改行をつけてください. つけないと動かない可能性があります.
2018/05/26 10:26 末尾改行の有無に関わらず動作するようになりました．

サンプル

3 3
2 1 3
001
110
000

1 3 2 3
2 1 2 1
2 1 2 3

000
111
000

000
011
000

000
100
000