AT_future_fif_digital_days_open_a future_fif_digital_days_open_a

[problemUrl]: https://atcoder.jp/contests/future-fif-digital-days-open/tasks/future_fif_digital_days_open_a $ N\times\ N $ マスの盤面と $ B $ 種類のポリオミノがある。 一番左上のマスの座標を $ (0,\ 0) $ とし、そこから下へ $ i $ マス、右へ $ j $ マス移動した先のマスの座標を $ (i,\ j) $ と定める。 初期状態で全てのマスは通行不能であり、ポリオミノを盤面に配置するとその上が通行可能になる。 盤面上の $ K $ 個のマスに印が付いており、ポリオミノを配置することで全ての印が付けられたマスが連結になるようにしたい。  例えば、上の図では左上の印と右上の印は連結になっているが、下の印とは連結になっていない。 同一種類のポリオミノを任意個配置することが出来るが、回転させたり、盤面からはみ出すように配置することは出来ない。 また、1つのマスの上に2つ以上のポリオミノを重ねて配置することも出来ない。 各ポリオミノの種類 $ b $ ごとにコスト $ C_b $ が定まっており、ポリオミノ $ b $ を $ m_b $ 個配置したとき、合計コストは $ \sum_{b=1}^B\ C_b\ m_b $ となる。 出来るだけ小さい合計コストで全ての印が付けられたマスを連結にしてほしい。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ B $ $ i_1 $ $ j_1 $ $ \vdots $ $ i_K $ $ j_K $ $ n_1 $ $ m_1 $ $ C_1 $ $ s^1_{1,1} $ $ \ldots $ $ s^1_{1,m_1} $ $ \vdots $ $ s^1_{n_1,1} $ $ \ldots $ $ s^1_{n_1,m_1} $ $ \vdots $ $ n_B $ $ m_B $ $ C_B $ $ s^B_{1,1} $ $ \ldots $ $ s^B_{1,m_B} $ $ \vdots $ $ s^B_{n_B,1} $ $ \ldots $ $ s^B_{n_B,m_B} $ 一行目には盤面の縦・横の大きさを表す整数 $ N $、印が付けられたマスの総数 $ K $、ポリオミノの種類数 $ B $ が与えられる。全てのテストケースで $ N=50 $ で固定である。 続く $ K $ 行には印の付いたマスの情報が与えられ、その $ p $ 行目は $ p $ 番目の印の座標が $ (i_p,\ j_p) $ であることを表し、$ 0\leq\ i_p\leq\ N-1,\ 0\leq\ j_p\leq\ N-1 $ を満たす。 印の座標は全て異なる。 最後に $ B $ 種類のポリオミノに関する情報が一つずつ与えられる。 - $ n_b $ と $ m_b $ は $ b $ 番目のポリオミノを囲う最小の長方形(バウンディングボックス)の縦・横の大きさを表す。$ n_1=m_1=1 $ であることが保証されている。 - $ C_b $ は $ b $ 番目のポリオミノを1つ配置するのに必要なコストを表す正の整数である。 - $ s^b_{i,j} $ は $ b $ 番目のポリオミノのバウンディングボックスの上から $ i $ マス目、左から $ j $ マス目の情報を表し、`#` の場合はポリオミノに属し、`.` の場合はポリオミノに属さないことを表している。 - 各ポリオミノは連結であることが保証されている。

以下の形式で、一行目に使用するポリオミノの総数 $ m $ を、続く $ m $ 行には使用するポリオミノの種類を表す整数 $ b_i $ ($ 1\leq\ b_i\leq\ B $) とバウンディングボックスの左上の座標 $ (x_i,\ y_i) $ ($ 0\leq\ x_i\leq\ N-n_{b_i},\ 0\leq\ y_i\leq\ N-m_{b_i} $)を一行ずつ出力せよ。 > $ m $ $ b_1 $ $ x_1 $ $ y_1 $ $ \vdots $ $ b_m $ $ x_m $ $ y_m $

### 得点 合計コストを $ S $ とすると、$ \mathrm{round}(10^8\ /\ S) $ の得点が得られる。 不正な出力(印のついたマスが連結になっていない、ポリオミノが盤面からはみ出している、もしくは重なっている)がされた場合、WAと判定される。 1つ以上のテストケースでAC以外の判定がされた場合、提出の得点は0点となる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、その得点を獲得した提出の早い方が上位となる。 ### テストケース数 1 個 ### 入力生成方法 A問題のテストケース数は1つであり、入力例 1 と同一である。 手動等により事前に計算した出力のみを提出しても構わない。 ### ツール - [Web版ビジュアライザ・入力ジェネレータ](https://img.atcoder.jp/future-fif-digital-days/visYp.html?q=a) - [ローカル実行版ビジュアライザ・入力ジェネレータ](https://img.atcoder.jp/future-fif-digital-days/dd7a70773bb74f0570cdde81b1bf6ee3.zip): 使用するには、[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。