配点 : $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 \leq N \leq 300$
• $U_i,D_i,L_i,R_i$ は $0$ 以上の整数である。
• $U_i,D_i,L_i,R_i$ の和は $N \times N$ と等しい。

部分点

• $N \leq 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$ つを出力すれば良い。

3
0 0 1
1 1 0
3 0 1
0 1 1

L1
L1
L1
L3
D1
R2
U3
R3
D2

下図の通りに差し込めば良いです。矢印は差し込む場所を、丸はタイルを、丸の中に書かれた番号はそのタイルが何番目に差し込まれたかを表しています。

2
2 0
2 0
0 0
0 0

NO