A - Group Commands and Wall Planning

18 min read Original article ↗

A - Group Commands and Wall Planning Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

N\times N マスの盤面がある。 左上のマスの座標を (0, 0) とし、下方向に i、右方向に j マス進んだ位置の座標を (i, j) とする。 一部の隣接マス間には壁が存在する。

盤面上には K 台のロボットが存在する。 k 番目のロボットの初期位置は (i_k, j_k) で、目的地は (i_k', j_k') である。 高橋くんはこれらのロボットを操作して、すべてのロボットが目的地に到達した状態を達成したい。

まずはじめに、以下の二種類の準備を行う。

  1. 最初からある壁に加え、任意の隣接マス間に壁を設置できる。
  2. ロボットをグループに分割する。各ロボットは1つのグループに属し、同じグループのロボットは同時に操作することができる。

これらの準備は最初の操作を行う前に行い、それ以降に新たに壁を設置したりグループを変更することはできない。

次に、以下の2種類の操作を繰り返し行うことでロボットを移動させる。

  1. グループ命令: 1つのグループと上下左右の方向を指定し、そのグループに属するすべてのロボットがその方向に1マス移動する。移動先のマスとの間に壁があったり、移動先に他のロボットが存在する場合は移動しない。指定されたグループに属するロボットのうちで、指定した方向に最も進んだ先にあるものから順に移動する。例えば (1,0) と (2,0) にロボットがいる状態で上方向を指定した場合、i 座標の小さい順に移動するため、まず (1,0) のロボットが (0,0) に移動し、次に (2,0) のロボットが空いた (1,0) のマスに移動する。

  2. 個別命令: 1台のロボットと上下左右の方向を指定し、指定したロボットがその方向に1マス移動する。移動先のマスとの間に壁があったり、移動先に他のロボットが存在する場合は移動しない。

一度目的地に到達しても、その後の操作によって目的地から離れた場合は、目的地に到達した状態とはみなされない。

操作は最大で K N^2 回行うことができる。 できるだけ少ない操作回数で、すべてのロボットを目的地へ誘導せよ。

得点

操作回数を T、ロボット k の最終位置と目的地とのマンハッタン距離を d_k としたとき、以下の絶対スコアを獲得する。 \[ T + 100 \times \sum_k d_k \]

絶対スコアは小さければ小さいほど良い。

各テストケース毎に、\mathrm{round}(10^9\times \frac{全参加者中の最小絶対スコア}{自身の絶対スコア}) の相対評価スコアが得られ、その和が提出の得点となる。

最終順位はコンテスト終了後に実施されるより多くの入力に対するシステムテストにおける得点で決定される。 暫定テスト、システムテストともに、一部のテストケースで不正な出力や制限時間超過をした場合、そのテストケースの相対評価スコアは0点となり、そのテストケースにおいては「全参加者中の最小絶対スコア」の計算から除外される。 システムテストは CE 以外の結 果を得た一番最後の提出に対してのみ行われるため、最終的に提出する解答を間違えないよう注意せよ。

テストケース数

  • 暫定テスト: 50個
  • システムテスト: 2000個、コンテスト終了後に seeds.txt (sha256=063a84b1c0dc9388b0996eed0bc645529c931c139bee6b8e0e84a4faf3e06c40) を公開

相対評価システムについて

暫定テスト、システムテストともに、CE 以外の結果を得た一番最後の提出のみが順位表に反映される。 相対評価スコアの計算に用いられる各テストケース毎の全参加者中の最小絶対スコアの算出においても、順位表に反映されている最終提出のみが用いられる。

順位表に表示されているスコアは相対評価スコアであり、新規提出があるたびに、相対評価スコアが再計算される。 一方、提出一覧から確認出来る各提出のスコアは各テストケース毎の絶対スコアをそのまま足し合わせたものであり、相対評価スコアは表示されない。 最新以外の提出の、現在の順位表における相対評価スコアを知るためには、再提出が必要である。 不正な出力や制限時間超過をした場合、提出一覧から確認出来るスコアは0となるが、順位表には正解したテストケースに対する相対スコアの和が表示されている。

実行時間について

実行時間には多少のブレが生じます。 また、システムテストでは同時に大量の実行を行うため、暫定テストに比べて数%程度実行時間が伸びる現象が確認されています。 そのため、実行時間制限ギリギリの提出がシステムテストでTLEとなる可能性がありま す。 プログラム内で時間を計測して処理を打ち切るか、実行時間に余裕を持たせるようお願いします。

入力

入力は以下の形式で標準入力から与えられる。

N K
i_0 j_0 i_0' j_0'
\vdots
i_{K-1} j_{K-1} i_{K-1}' j_{K-1}'
v_{0,0} \cdots v_{0,N-2}
\vdots
v_{N-1,0} \cdots v_{N-1,N-2}
h_{0,0} \cdots h_{0,N-1}
\vdots
h_{N-2,0} \cdots h_{N-2,N-1}
  • すべてのテストケースにおいて、N=30 に固定されている。
  • 10 \leq K \leq 100 を満たす。
  • (i_k, j_k) は k 台目のロボットの初期位置を表す。
  • (i_k', j_k') は k 台目のロボットの目的地を表す。
  • すべての初期位置、すべての目的地はそれぞれ相異なるが、ロボット k の初期位置とロボット k' の目的地が等しい可能性はある。
  • v_{i,0} \cdots v_{i,N-2} は長さ N-1 の 01 からなる文字列であり、その j 文字目 v_{i,j} はマス (i, j) とマス (i, j+1) の間に壁がある (1) かない (0) かを表す。
  • h_{i,0} \cdots h_{i,N-1} は長さ N の 01 からなる文字列であり、その j 文字目 h_{i,j} はマス (i, j) とマス (i+1, j) の間に壁がある (1) かない (0) かを表す。
  • すべてのマスは互いに到達可能であることが保証されている。

出力

まず、設置する壁の情報を以下の形式で標準出力に出力せよ。

v'_{0,0} \cdots v'_{0,N-2}
\vdots
v'_{N-1,0} \cdots v'_{N-1,N-2}
h'_{0,0} \cdots h'_{0,N-1}
\vdots
h'_{N-2,0} \cdots h'_{N-2,N-1}
  • v_{i,0}' \cdots v_{i,N-2}' は長さ N-1 の 01 からなる文字列であり、その j 文字目 v_{i,j}' はマス (i, j) とマス (i, j+1) の間に壁を設置する（1）かしない（0）かを表す。
  • h_{i,0}' \cdots h_{i,N-1}' は長さ N の 01 からなる文字列であり、その j 文字目 h_{i,j}' はマス (i, j) とマス (i+1, j) の間に壁を設置する（1）かしない（0）かを表す。
  • 最初から壁が存在する箇所は 0 と 1 のどちらを出力しても構わない。

次に、グループ分けの情報を以下の形式で標準出力に出力せよ。

g_0 \cdots g_{K-1}
  • g_k は k 番目のロボットの属するグループを表す 0 以上 K-1 以下の整数値である。g_k = g_{k'} のとき、ロボット k と k' は同じグループに属する。

最後に、操作列を次の形式で標準出力に出力せよ。

a_0 b_0 d_0
\vdots
a_{T-1} b_{T-1} d_{T-1}
  • a_t は t ターン目の操作の種類を指定する1文字である。グループ命令の場合は g、個別命令の場合は i である。
  • b_t は t ターン目の操作対象のグループ番号もしくはロボット番号を表す 0 以上 K-1 以下の整数値である。ロボットが1台も属さないグループが指定された場合は、何も起こらない。
  • d_t は t ターン目の操作の方向を指定し、以下の1文字である。
  • 上: U
  • 下: D
  • 左: L
  • 右: R

例を見る

入力生成方法

\mathrm{rand}(L, U) を、L 以上 U 以下の整数値を一様ランダムに生成する関数とする。

ロボットの生成

ロボットの台数 K を K = \mathrm{rand}(10, 100) により決定する。
ロボットの初期位置は、N^2 個の座標の中から重複しないように一様ランダムに K 個選んで生成する。
ロボットの目的地も同様に、N^2 個の座標の中から重複しないように一様ランダムに K 個選んで生成する。

壁の生成

壁の線分数 W を W = \mathrm{rand}(0, 2) により生成する。

以下を W 回繰り返す。

  1. 壁を生成する方向を上下左右からランダムに決定する。
  2. 壁の長さを L = \mathrm{rand}(10, 20) により生成する。
  3. 縦方向の壁の場合、始点 (i, j) を i = \mathrm{rand}(5, N-5),\ j = \mathrm{rand}(4, N-6) により選択する。ただし、これまでに生成された縦壁に使用された j と絶対値の差が 4 以下の j が選ばれた場合は、方向の選択からやり直す。
    上方向の場合は v_{i-L+1, j}, \cdots, v_{i, j} を、下方向の場合は v_{i, j}, \cdots, v_{i+L-1, j} を 1 に設定する。ただし、盤面外にはみ出した部分は無視する。
  4. 横方向の壁の場合、始点 (i, j) を i = \mathrm{rand}(4, N-6),\ j = \mathrm{rand}(5, N-5) により選択する。ただし、これまでに生成された横壁に使用された i と絶対値の差が 4 以下の i が選ばれた場合は、方向の選択からやり直す。
    左方向の場合は h_{i, j-L+1}, \cdots, h_{i, j} を、右方向の場合は h_{i, j}, \cdots, h_{i, j+L-1} を 1 に設定する。ただし、盤面外にはみ出した部分は無視する。
  5. 生成した壁に対し、すべてのマスが到達可能であるかを判定する。到達不能な場合は壁を初期化し、W 回の反復をやり直す。

ツール(入力ジェネレータ・ビジュアライザ)

コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。

入力例 1

30 59
8 18 11 17
8 23 17 15
1 12 11 7
19 17 24 22
23 9 8 20
21 17 26 10
4 19 12 29
19 29 7 7
19 24 12 19
24 26 19 10
12 23 4 18
8 22 26 11
23 18 16 26
28 14 8 14
6 12 21 12
28 18 13 21
21 28 17 3
5 14 11 20
28 13 19 28
27 18 18 8
7 21 28 23
25 13 0 17
15 17 4 24
15 19 7 0
3 26 10 25
26 20 7 6
17 10 28 17
8 9 5 21
2 26 12 9
18 29 21 10
7 20 10 24
23 5 11 18
24 12 4 9
9 19 26 13
1 0 15 12
9 8 3 8
29 9 15 24
22 14 3 18
15 16 15 1
1 29 19 4
9 12 27 21
2 23 9 4
18 24 14 18
22 7 8 1
20 29 24 3
3 2 12 17
10 11 15 20
16 6 24 0
6 5 29 17
29 20 26 16
14 18 0 9
29 11 26 20
24 22 1 13
1 5 15 9
26 10 27 26
20 20 2 6
6 28 15 2
22 6 0 0
6 17 16 13
00000000000000000000000000000
00000000000000000000000000000
00000000000000000000000000000
00000000000000000000000000000
00000000000000000000000000000
00000000000000000000000000000
00000000000000000000000000000
00000000000000000000000000000
00000000000000000000000000000
00000000000000000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000000000000000000000
00000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000

出力例 1

00000000000000000000000000000
01000000000000000000000000000
00000000000000000000000000000
00000000000000000000001000000
00000000000100000000000000000
00000000000000000000000000001
00000000000000000000000000000
00000000000000000000000000000
00000000000000000000000000000
00000000000000000000000000000
00000000000100000000000000000
00000000000100000000010000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100001000000000000
00000000000100000000000100000
00000000000100000000000001000
00010000000100000000000000000
00000000000100000000000000000
00000010000100000000000000000
01000000000100000000000000000
00000000000100000000000000100
00000000000100000000000000000
00000001000100000000000000000
00000000000100000000000000000
00000000000100000000000001010
00000000000100000000000000000
00000000000100000000000000000
00000000000000000000000000000
00000000000000000000000000000
000000100000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000100000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000001000000
000000000000000000000000000000
000000000000000000000000000100
000001000000000000000000000000
000000000000000000000100100000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000010000000000000
000000000000000000000000100000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000010000
000000100000000000000000000000
000000000000000000000000000000
000000000000000010000000000000
000000000000000100000000000000
000000000000000000000000000000
000000000000000000000000000000
000000001000000000000000000000
6 2 3 3 8 9 0 1 8 0 9 7 5 6 3 6 7 5 4 6 7 3 0 1 5 8 3 4 5 6 7 0 0 3 9 5 4 6 2 8 8 6 6 0 9 7 2 1 3 9 3 6 2 6 5 4 0 3 8
i 16 D
g 0 U
i 27 U
g 1 L
i 0 D
g 5 D
i 58 D
i 52 U
i 44 D
i 17 D
g 0 U
g 4 U
i 32 U
g 2 U
i 31 U
g 9 L
g 0 U
g 2 L
i 30 D
g 3 D
i 48 D
g 2 L
i 14 D
i 1 D
g 7 D
g 3 D
i 14 D
g 1 L
i 32 U
i 57 U
i 56 D
i 21 U
g 6 D
i 4 U
i 20 D
g 7 D
i 7 U
i 39 D
i 42 U
g 7 D
i 15 U
i 32 U
i 6 D
g 6 D
i 50 U
g 5 D
g 4 U
g 2 L
i 40 D
g 2 L
i 29 D
i 1 D
g 7 D
g 7 D
i 41 D
g 9 L
i 48 D
i 16 D
g 8 L
g 5 D
g 6 D
i 14 D
i 50 L
g 6 U
i 29 D
i 46 R
g 6 L
i 9 D
g 6 D
i 16 L
i 7 U
i 2 D
g 9 D
g 5 D
g 8 L
g 8 L
i 4 R
i 40 D
i 10 U
g 4 R
i 50 L
g 9 L
i 28 L
i 32 U
g 3 D
i 4 U
i 6 D
i 35 U
i 33 D
g 0 U
g 7 R
i 23 U
g 4 R
g 6 D
i 7 U
i 57 U
g 0 U
g 5 D
g 6 D
g 3 D

Problem Statement

There is an N \times N grid. The coordinate of the top-left cell is (0, 0), and the coordinate of the cell i rows down and j columns to the right is (i, j). There are walls between some adjacent cells.

There are K robots on the grid. The initial position of the k-th robot is (i_k, j_k), and its destination is (i_k', j_k'). Takahashi wants to operate these robots to bring all of them to their respective destinations.

Before making any moves, the following two types of preparations can be made:

  1. In addition to the existing walls, you may add walls between any adjacent cells.
  2. Divide the robots into groups. Each robot belongs to exactly one group, and all robots in the same group can be operated simultaneously.

These preparations must be completed before the first move. After that, no additional walls can be placed and the group assignments cannot be changed.

Next, the robots can be moved by repeatedly performing the following two types of operations:

  1. Group Command: Specify a group and a direction (up, down, left, or right). All robots in that group will attempt to move one cell in the specified direction. If there is a wall between the current and target cells, or if another robot is occupying the target cell, the robot does not move. Among the robots belonging to the group, those farthest in the direction of movement will attempt to move first. For example, if robots are at (1, 0) and (2, 0) and the direction is up, the robot at (1, 0) will move to (0, 0) first (since it has a smaller i coordinate), and then the robot at (2, 0) will move to the now-empty (1, 0).

  2. Individual Command: Specify a robot and a direction (up, down, left, or right). The specified robot will attempt to move one cell in the specified direction. If there is a wall between the current and target cells, or if another robot is occupying the target cell, the robot does not move.

Even if a robot reaches its destination once, if it moves away from the destination due to subsequent operations, it is not considered to have reached its destination.

You may perform at most K N^2 operations. Guide all robots to their destinations using as few operations as possible.

Scoring

Let T be the number of operations performed, and let d_k be the Manhattan distance between the final position and the destination of robot k. Then, you obtain the following absolute score: \[ T + 100 \times \sum_k d_k \]

The lower the absolute score, the better.

For each test case, we compute the relative score \mathrm{round}(10^9\times \frac{\mathrm{MIN}}{\mathrm{YOUR}}), where YOUR is your absolute score and MIN is the lowest absolute score among all competitors obtained on that test case. The score of the submission is the sum of the relative scores.

The final ranking will be determined by the system test with more inputs which will be run after the contest is over. In both the provisional/system test, if your submission produces illegal output or exceeds the time limit for some test cases, only the score for those test cases will be zero, and your submission will be excluded from the MIN calculation for those test cases.

The system test will be performed only for the last submission which received a result other than CE . Be careful not to make a mistake in the final submission.

Number of test cases

  • Provisional test: 50
  • System test: 2000. We will publish seeds.txt (sha256=063a84b1c0dc9388b0996eed0bc645529c931c139bee6b8e0e84a4faf3e06c40) after the contest is over.

About relative evaluation system

In both the provisional/system test, the standings will be calculated using only the last submission which received a result other than CE. Only the last submissions are used to calculate the MIN for each test case when calculating the relative scores.

The scores shown in the standings are relative, and whenever a new submission arrives, all relative scores are recalculated. On the other hand, the score for each submission shown on the submissions page is the sum of the absolute score for each test case, and the relative scores are not shown. In order to know the relative score of submission other than the latest one in the current standings, you need to resubmit it. If your submission produces illegal output or exceeds the time limit for some test cases, the score shown on the submissions page will be 0, but the standings show the sum of the relative scores for the test cases that were answered correctly.

About execution time

Execution time may vary slightly from run to run. In addition, since system tests simultaneously perform a large number of executions, it has been observed that execution time increases by several percent compared to provisional tests. For these reasons, submissions that are very close to the time limit may result in TLE in the system test. Please measure the execution time in your program to terminate the process, or have enough margin in the execution time.

Input

Input is given from Standard Input in the following format.

N K
i_0 j_0 i_0' j_0'
\vdots
i_{K-1} j_{K-1} i_{K-1}' j_{K-1}'
v_{0,0} \cdots v_{0,N-2}
\vdots
v_{N-1,0} \cdots v_{N-1,N-2}
h_{0,0} \cdots h_{0,N-1}
\vdots
h_{N-2,0} \cdots h_{N-2,N-1}
  • In all test cases, N=30 is fixed.
  • 10 \leq K \leq 100
  • (i_k, j_k) represents the initial position of the k-th robot.
  • (i_k', j_k') represents the destination of the k-th robot.
  • All initial positions and all destinations are each mutually distinct, but the initial position of robot k may coincide with the destination of robot k'.
  • Each v_{i,0} \cdots v_{i,N-2} is a binary string of length N-1. The j-th character v_{i,j} indicates whether there is a wall (1) or not (0) between cells (i, j) and (i, j+1).
  • Each h_{i,0} \cdots h_{i,N-1} is a binary string of length N. The j-th character h_{i,j} indicates whether there is a wall (1) or not (0) between cells (i, j) and (i+1, j).
  • It is guaranteed that all cells are mutually reachable.

Output

First, output the wall placement information in the following format to Standard Output.

v'_{0,0} \cdots v'_{0,N-2}
\vdots
v'_{N-1,0} \cdots v'_{N-1,N-2}
h'_{0,0} \cdots h'_{0,N-1}
\vdots
h'_{N-2,0} \cdots h'_{N-2,N-1}
  • Each v_{i,0}' \cdots v_{i,N-2}' is a binary string of length N-1. The j-th character v_{i,j}' indicates whether a wall is placed (1) or not (0) between cells (i, j) and (i, j+1).
  • Each h_{i,0}' \cdots h_{i,N-1}' is a binary string of length N. The j-th character h_{i,j}' indicates whether a wall is placed (1) or not (0) between cells (i, j) and (i+1, j).
  • For positions where a wall already exists, either 0 or 1 may be output.

Next, output the group assignment information to Standard Output in the following format.

g_0 \cdots g_{K-1}
  • g_k is an integer between 0 and K-1 representing the group to which the k-th robot belongs. If g_k = g_{k'}, then robot k and robot k' belong to the same group.

Finally, output the sequence of operations to Standard Output in the following format.

a_0 b_0 d_0
\vdots
a_{T-1} b_{T-1} d_{T-1}
  • a_t is a single character specifying the type of operation on turn t. Use g for a group command and i for an individual command.
  • b_t is an integer between 0 and K-1 representing the group number or robot number targeted by the operation on turn t. If a group with no robots is specified, nothing happens.
  • d_t is a single character indicating the direction of the operation on turn t, as follows:
    • Up: U
    • Down: D
    • Left: L
    • Right: R

Show example

Input Generation

Let \mathrm{rand}(L, U) be a function that generates a uniformly random integer between L and U, inclusive.

Robot Generation

The number of robots K is determined by K = \mathrm{rand}(10, 100).
The initial positions of the robots are chosen by selecting K distinct coordinates uniformly at random from the N^2 cells.
The destinations of the robots are similarly chosen by selecting K distinct coordinates uniformly at random from the N^2 cells.

Wall Generation

The number of wall segments W is determined by W = \mathrm{rand}(0, 2).

Repeat the following W times:

  1. Randomly choose the direction of the wall from up, down, left, or right.
  2. Determine the wall length L = \mathrm{rand}(10, 20).
  3. For vertical walls, choose the starting point (i, j) by i = \mathrm{rand}(5, N-5),\ j = \mathrm{rand}(4, N-6).
    If the chosen j is within an absolute distance of 4 from any j used in previously generated vertical walls, redo the direction selection.
    For upward walls, set v_{i-L+1, j}, \cdots, v_{i, j} to 1. For downward walls, set v_{i, j}, \cdots, v_{i+L-1, j} to 1. Ignore any part that goes out of bounds.
  4. For horizontal walls, choose the starting point (i, j) by i = \mathrm{rand}(4, N-6),\ j = \mathrm{rand}(5, N-5).
    If the chosen i is within an absolute distance of 4 from any i used in previously generated horizontal walls, redo the direction selection.
    For leftward walls, set h_{i, j-L+1}, \cdots, h_{i, j} to 1. For rightward walls, set h_{i, j}, \cdots, h_{i, j+L-1} to 1. Ignore any part that goes out of bounds.
  5. After generating the wall, check whether all cells are still mutually reachable. If not, reset the wall and restart the W iterations.

Tools (Input generator and visualizer)

Please be aware that sharing visualization results or discussing solutions/ideas during the contest is prohibited.

Sample Input 1

30 59
8 18 11 17
8 23 17 15
1 12 11 7
19 17 24 22
23 9 8 20
21 17 26 10
4 19 12 29
19 29 7 7
19 24 12 19
24 26 19 10
12 23 4 18
8 22 26 11
23 18 16 26
28 14 8 14
6 12 21 12
28 18 13 21
21 28 17 3
5 14 11 20
28 13 19 28
27 18 18 8
7 21 28 23
25 13 0 17
15 17 4 24
15 19 7 0
3 26 10 25
26 20 7 6
17 10 28 17
8 9 5 21
2 26 12 9
18 29 21 10
7 20 10 24
23 5 11 18
24 12 4 9
9 19 26 13
1 0 15 12
9 8 3 8
29 9 15 24
22 14 3 18
15 16 15 1
1 29 19 4
9 12 27 21
2 23 9 4
18 24 14 18
22 7 8 1
20 29 24 3
3 2 12 17
10 11 15 20
16 6 24 0
6 5 29 17
29 20 26 16
14 18 0 9
29 11 26 20
24 22 1 13
1 5 15 9
26 10 27 26
20 20 2 6
6 28 15 2
22 6 0 0
6 17 16 13
00000000000000000000000000000
00000000000000000000000000000
00000000000000000000000000000
00000000000000000000000000000
00000000000000000000000000000
00000000000000000000000000000
00000000000000000000000000000
00000000000000000000000000000
00000000000000000000000000000
00000000000000000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100000000000000000
00000000000000000000000000000
00000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000

Sample Output 1

00000000000000000000000000000
01000000000000000000000000000
00000000000000000000000000000
00000000000000000000001000000
00000000000100000000000000000
00000000000000000000000000001
00000000000000000000000000000
00000000000000000000000000000
00000000000000000000000000000
00000000000000000000000000000
00000000000100000000000000000
00000000000100000000010000000
00000000000100000000000000000
00000000000100000000000000000
00000000000100001000000000000
00000000000100000000000100000
00000000000100000000000001000
00010000000100000000000000000
00000000000100000000000000000
00000010000100000000000000000
01000000000100000000000000000
00000000000100000000000000100
00000000000100000000000000000
00000001000100000000000000000
00000000000100000000000000000
00000000000100000000000001010
00000000000100000000000000000
00000000000100000000000000000
00000000000000000000000000000
00000000000000000000000000000
000000100000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000100000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000001000000
000000000000000000000000000000
000000000000000000000000000100
000001000000000000000000000000
000000000000000000000100100000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000000000
000000000000000010000000000000
000000000000000000000000100000
000000000000000000000000000000
000000000000000000000000000000
000000000000000000000000010000
000000100000000000000000000000
000000000000000000000000000000
000000000000000010000000000000
000000000000000100000000000000
000000000000000000000000000000
000000000000000000000000000000
000000001000000000000000000000
6 2 3 3 8 9 0 1 8 0 9 7 5 6 3 6 7 5 4 6 7 3 0 1 5 8 3 4 5 6 7 0 0 3 9 5 4 6 2 8 8 6 6 0 9 7 2 1 3 9 3 6 2 6 5 4 0 3 8
i 16 D
g 0 U
i 27 U
g 1 L
i 0 D
g 5 D
i 58 D
i 52 U
i 44 D
i 17 D
g 0 U
g 4 U
i 32 U
g 2 U
i 31 U
g 9 L
g 0 U
g 2 L
i 30 D
g 3 D
i 48 D
g 2 L
i 14 D
i 1 D
g 7 D
g 3 D
i 14 D
g 1 L
i 32 U
i 57 U
i 56 D
i 21 U
g 6 D
i 4 U
i 20 D
g 7 D
i 7 U
i 39 D
i 42 U
g 7 D
i 15 U
i 32 U
i 6 D
g 6 D
i 50 U
g 5 D
g 4 U
g 2 L
i 40 D
g 2 L
i 29 D
i 1 D
g 7 D
g 7 D
i 41 D
g 9 L
i 48 D
i 16 D
g 8 L
g 5 D
g 6 D
i 14 D
i 50 L
g 6 U
i 29 D
i 46 R
g 6 L
i 9 D
g 6 D
i 16 L
i 7 U
i 2 D
g 9 D
g 5 D
g 8 L
g 8 L
i 4 R
i 40 D
i 10 U
g 4 R
i 50 L
g 9 L
i 28 L
i 32 U
g 3 D
i 4 U
i 6 D
i 35 U
i 33 D
g 0 U
g 7 R
i 23 U
g 4 R
g 6 D
i 7 U
i 57 U
g 0 U
g 5 D
g 6 D
g 3 D