/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
うさぎは昨年や一昨年のように，Xmas Contest 2020 を記念した看板を作ろうとしている．
そういえば，去年はたくさんの種類のスタンプを使って遊んだなあ……．
問題文
与えられたスタンプだけを高々 20\,000 回使うことで，以下の領域マップに沿った画像を作り上げよ．後述の達成条件を満たしていれば，カラフルな画像にしてもよい．
キャンバスとスタンプ
画像を作るためのキャンバスは横 800 px，縦 400 px であり，画素の位置は整数の組 (x, y) (0 \le x < 800，0 \le y < 400) で表される．x 座標が増える方向が左から右へ，y 座標が増える方向が上から下へであることに注意せよ．各画素は色を表す R, G, B の 3 要素を持つ．はじめ，キャンバスのどの要素も R, G, B の値はすべて 0 である．
スタンプは大きさ s と，色情報 r, g, b の 4 つの整数によって表される．1 回のスタンプ操作では，キャンバスの指定した位置にスタンプを押すか，指定した位置からスタンプを引くことができる．
より詳細には，あるスタンプ (s, r, g, b) を位置 (x_i, y_i) に 押した／引いた 場合，x_i \le x < x_i + s かつ y_i \le y < y_i + s を満たすすべての画素 (x, y) に対し，その画素の R, G, B の値にそれぞれ r, g, b が 加算／減算 される．操作の結果，ある画素の値が 255 を上回った場合は 255 に，0 を下回った場合は 0 になる．
達成条件
領域マップにおいて，同じ色からなる画素の 4 方向に連結な成分を領域と呼ぶ．ある画像が「領域マップに沿った」とみなされるためには次のようになっている必要がある．
- それぞれの領域内はある程度同じ色で塗られている．
- 隣り合う領域はある程度異なる色で塗られている．
厳密には，画像が以下の 2 条件をどちらも満たしていればよい：
- 領域内条件：それぞれの領域に対し，領域内の画素すべての R の値の分散が 700 以下であること．また，G の分散と B の分散も同様に 700 以下であること．
- 隣接領域条件：ある領域の平均色を，領域内の画素すべての R, G, B の (要素ごとの) 平均値とする．領域マップにおいて隣接する 2 つの領域の平均色をそれぞれ (R_1, G_1, B_1) および (R_2, G_2, B_2) とすると，(R_1 - R_2)^2 + (G_1 - G_2)^2 + (B_1 - B_2)^2 \ge 80^2 が成り立つこと．
データ
この問題を解くために必要なデータをまとめた zip ファイルがこちらからダウンロードできる．zip 内には以下のファイルが入っている．
stamps/map.png: 領域マップを表す画像．画像サイズは横 800 px，縦 400 px である．stamps/map.txt: 領域マップに対応する，各画素にその領域 ID を振ったテキストファイル．- 400 行からなり，各行に 800 個の整数が書かれている．
stamps/stampset.txt: 使えるスタンプの一覧を表すテキストファイル．- 1 行目にはスタンプの種類数 K が書かれている．
- 続く K 行には，各行に 5 個の整数 k, s, r, g, b が書かれている．これはスタンプ ID が k であるスタンプが (s, r, g, b) で表されることを意味する．スタンプはスタンプ ID の昇順に書かれている．
stamps/play.html: ビジュアライザ兼手作業用ツール．操作列の可視化や，達成条件の判定などの機能も備えているので，少なくとも提出前には使うことが推奨される．- 左下に「スタンプ操作をロードする」機能がある．これは正しいスタンプ操作を表す行だけをすべて読み込む (よって，後述の出力形式に従ったものを入れたときは，最初の行は単に読み飛ばされる)．
stamps/play.js: ビジュアライザ兼手作業用ツールのソースコード．
制約
上記のデータが満たす条件のうち，一部の重要な情報を以下に示す．
- 画像サイズは横 800 px，縦 400 px である．
- 領域の個数は 30 であり，領域 ID は 0, \ldots, 29 である．
- 同じ領域 ID が振られた画素の集合は 4 方向に連結である．
- スタンプの種類数は 18 であり，スタンプ ID は 0, \ldots, 17 である．
- 各スタンプにおいて，以下が成り立つ：
- 7 \le s \le 50．
- 0 \le r \le 40．
- 0 \le g \le 40．
- 0 \le b \le 40．
入力
この問題では入力は与えられない．
出力
p k_1 x_1 y_1 t_1 \vdots k_p x_p y_p t_p
1 行目に，スタンプ操作の回数を表す整数 p (0 \le p \le 20\,000) を出力せよ．
続く p 行のうち i (1 \le i \le p) 行目には，i 回目のスタンプ操作を表す 4 つの整数 k_i, x_i, y_i, t_i を空白区切りで出力せよ．これは，i 回目の操作では位置 (x_i, y_i) に ID k_i のスタンプを使うことを表す．t_i = 1 の場合はスタンプを押す操作，t_i = -1 の場合はスタンプを引く操作を表す．
スタンプは少なくとも 1 個の画素を覆う位置で使わなければならない．すなわち，ID k_i のスタンプの大きさが s のとき，-s < x_i < 800 かつ -s < y_i < 400 でなければならない．
入力例 1
出力例 1
4 0 100 200 1 1 -10 5 1 2 799 300 -1 0 100 200 1
これは上記の書式の条件を満たす出力の例である (ただし，この出力は達成条件を満たしていないので WA になる)．