/ 
実行時間制限: 4 sec / メモリ制限: 256 MB
配点 : 2100 点
問題文
縦 N 行、横 N 列のマス目が書かれたボードと N \times N 枚のタイルがあります。
外側に面したマスの辺には、タイルの差込口がついています。 つまり、ボードの上下左右の辺にはそれぞれ N 個の差込口がついており、合計で 4 \times N 個の差込口があることになります。 それぞれの差込口には以下のように番号が付けられています。
- 上辺の差込口：左から順に U1, U2, ..., UN
- 下辺の差込口：左から順に D1, D2, ..., DN
- 左辺の差込口：上から順に L1, L2, ..., LN
- 右辺の差込口：上から順に R1, R2, ..., RN
各差込口からはタイルを差し込むことが出来ます。 タイルが差し込まれたマスにすでにタイルが置かれていた場合は、置かれていたタイルは 1 つ先のマスに押し出され、さらにその 1 つ先のマスにタイルが置かれていた場合も同様に押し出されていきます。 ただし、押し出されたタイルがボードの外に出てしまう場合はタイルを差し込むことができません。 タイルを差し込んだときの挙動に関する詳しい例については入出力例 1 を参考にしてください。
すぬけくんは、N \times N 枚のタイルを 1 枚ずつ差込口から差し込むことによって、各マスに 1 枚ずつタイルが置かれている状態にしようとしています。 ただし、差込口 Ui からはちょうど U_i 枚、差込口 Di からはちょうど D_i 枚、差込口 Li からはちょうど L_i 枚、差込口 Ri からはちょうど R_i 枚のタイルを差し込まなければなりません。 このような差し込み方が可能かどうかを判定してください。また、可能な場合は差し込む順番を出力してください。
制約
- 1≦N≦300
- U_i,D_i,L_i,R_i は 0 以上の整数である。
- U_i,D_i,L_i,R_i の和は N \times N と等しい。
部分点
- N≦40 を満たすデータセットに正解した場合は、2000 点が与えられる。
- 追加制約のないデータセットに正解した場合は、上記とは別に 100 点が与えられる。
入力
入力は以下の形式で標準入力から与えられる。
N U_1 U_2 ... U_N D_1 D_2 ... D_N L_1 L_2 ... L_N R_1 R_2 ... R_N
出力
各マスに 1 枚ずつタイルが置かれるようにタイルを差し込むことが可能ならば、差込口の番号を差し込むべき順番で 1 行にひとつずつ出力せよ。不可能な場合は、代わりに NO と出力せよ。また、差し込む順番が複数考えられる場合は、そのうちの 1 つを出力すれば良い。
入力例 1
3 0 0 1 1 1 0 3 0 1 0 1 1
出力例 1
L1 L1 L1 L3 D1 R2 U3 R3 D2
下図の通りに差し込めば良いです。矢印は差し込む場所を、丸はタイルを、丸の中に書かれた番号はそのタイルが何番目に差し込まれたかを表しています。
入力例 2
2 2 0 2 0 0 0 0 0
出力例 2
NO
Score : 2100 points
Problem Statement
Snuke has a board with an N \times N grid, and N \times N tiles.
Each side of a square that is part of the perimeter of the grid is attached with a socket. That is, each side of the grid is attached with N sockets, for the total of 4 \times N sockets. These sockets are labeled as follows:
- The sockets on the top side of the grid: U1, U2, ..., UN from left to right
- The sockets on the bottom side of the grid: D1, D2, ..., DN from left to right
- The sockets on the left side of the grid: L1, L2, ..., LN from top to bottom
- The sockets on the right side of the grid: R1, R2, ..., RN from top to bottom
Snuke can insert a tile from each socket into the square on which the socket is attached. When the square is already occupied by a tile, the occupying tile will be pushed into the next square, and when the next square is also occupied by another tile, that another occupying tile will be pushed as well, and so forth. Snuke cannot insert a tile if it would result in a tile pushed out of the grid. The behavior of tiles when a tile is inserted is demonstrated in detail at Sample Input/Output 1.
Snuke is trying to insert the N \times N tiles one by one from the sockets, to reach the state where every square contains a tile. Here, he must insert exactly U_i tiles from socket Ui, D_i tiles from socket Di, L_i tiles from socket Li and R_i tiles from socket Ri. Determine whether it is possible to insert the tiles under the restriction. If it is possible, in what order the tiles should be inserted from the sockets?
Constraints
- 1≦N≦300
- U_i,D_i,L_i and R_i are non-negative integers.
- The sum of all values U_i,D_i,L_i and R_i is equal to N \times N.
Partial Scores
- 2000 points will be awarded for passing the test set satisfying N≦40.
- Additional 100 points will be awarded for passing the test set without additional constraints.
Input
The input is given from Standard Input in the following format:
N U_1 U_2 ... U_N D_1 D_2 ... D_N L_1 L_2 ... L_N R_1 R_2 ... R_N
Output
If it is possible to insert the tiles so that every square will contain a tile, print the labels of the sockets in the order the tiles should be inserted from them, one per line. If it is impossible, print NO instead. If there exists more than one solution, print any of those.
Sample Input 1
3 0 0 1 1 1 0 3 0 1 0 1 1
Sample Output 1
L1 L1 L1 L3 D1 R2 U3 R3 D2
Snuke can insert the tiles as shown in the figure below. An arrow indicates where a tile is inserted from, a circle represents a tile, and a number written in a circle indicates how many tiles are inserted before and including the tile.
Sample Input 2
2 2 0 2 0 0 0 0 0
Sample Output 2
NO