問題文

あなたと kaage 君(以降「あなたたち」とする)は、N*N のグリッド上において、二人組になって自転車でオリエンテーリングをしている。グリッドの上から(0-indexed で) i 行目、左から(0-indexed で) j 列目のマスは (i,j) と表される。以下に示されるオリエンテーリングのルールのもと、オリエンテーリングの終了時の「スコア」をなるべく高くすることが、あなたたちの目的である。

• あなたたちは、時刻 0 にマス (sx,sy) を出発する。
• オリエンテーリングをするフィールドは、0\leq i,j<N を満たす任意の整数 i,j を用いて (i,j) で表されるマス全体である。オリエンテーリングのあいだ、あなたたちはこの外に出ることはできない。
• フィールドのマスは、「陸」「海」の 2 種類に分かれている。「陸」マスにいるとき、あなたたちはそれぞれ別々に，1 分かけて上下左右に隣接する「陸」マスに移動するか，その場にとどまることができる。「海」マスに入ることはできない。
• あなたたちが「スコア」を獲得する方法は、最初に与えられる M 個の「ミッション」を達成することである。ミッションには次の 3 種類があり、それぞれを達成すると、ミッション 1 つにつき S_1, S_2, S_3 点が獲得できる。

---

• ミッション 1: あるマス (x, y) を、二人で同時に訪れる。
• ミッション 2: あるマス (x, y) を、二人のうちどちらかが訪れる。
• ミッション 3: あるマスの集合 (x_1, y_1),(x_2,y_2),\cdots,(x_k,y_k) に含まれるマス全部を、それぞれ二人のうちどちらかが訪れる。

---

制約

• 入力は v_{i,j} を除きすべて整数である。
• N=201
• sx=sy=100
• T=10000
• M=1000
• S_1=5,S_2=4,S_3=7
• \(v_{i,j}\) は . であるか、- であるかのいずれかである。
• 1\leq k_i \leq 5
• 0\leq x_i,x_{i,j},y_i,y_{i,j}\leq 200
• (x_i,y_i),(x_{i,j},y_{i,j}),(sx,sy) は「陸」のマスである。
• (sx,sy) から海のマスを通らずにすべての海以外のマスに到達できる。
• 「陸」のマスはフィールド全体の半分以上を占める。

テストケースの生成方法

テストケースは全部で 20 個あり、これらは次に示すアルゴリズムで生成される。

1. N*N のグリッドを考える。[0,N) から一様ランダムに x_i,y_i を、[0,70] から一様ランダムに h_i を選び、 (x,y) を中心として高さ h_i の山を構成してグリッドに足す。具体的には、(x,y) には max(0, h_i-|x_i-x|-|y_i-y|) が加算される。
2. 1. の操作を合計 50 回繰り返す。
3. 2. でできたグリッドに対し、あるマスの数を X としたとき、X<30 なら「海」、そうでなければ「陸」とする。
4. 3. でできたグリッドが制約を満たさない場合、1. に戻る。制約を満たせば、これが出力するグリッドとなる。
5. M 個のミッションを生成する。ミッション番号は [1,3] から一様ランダムに選ばれ、ミッション 3 の座標の個数は [1,5] から一様ランダムに選ばれる。座標は、「陸」のマス全体から一様ランダムに選ばれる。

採点

あなたのこの問題での得点は、20 個のテストケースに対する得点の和を 80 で割って小数点以下を切り捨てた値となる。

入力例1

4 5 2 2 2
7 3 6
....
....
...-
..--
3 2
1 2
2 1
2 1 1

出力例1

1 2 2 2
1 1 2 1
2 1 2 1
2 2 2 2
2 2 2 2