外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

X - Tough, Invincible, and Ultimate Cat Tower!

作成者 nekooooooo、siooisi、jammy、trueryob

テスター siooisi、tau0529、trueryob

配点 1200 点

実行時間制限
1.8 秒
メモリ制限
222 MiB

問題文

やさしいわりとねこくんは、ねこたちのためにとても豪華なキャットタワーを建てることにしました。

建設予定地は NN 行 NN 列のマス目で、はじめはすべてのマスの高さが 00 です。上から ii 行目、左から jj 列目のマスを (i,j)(i,j) とします。わりとねこくんは、マス (i,j)(i,j) の最終的な高さを Ai,jA_{i,j} にしたいと考えています。

盤面の各マスに、L、R、U、D のいずれかの杭を ちょうど1本 打ち込みます。盤面の外に杭を打ち込むことはできません。杭の配置は、次の条件を満たす必要があります。

  • 各行について、左から右に L と R の杭だけを取り出します。L を開き括弧(、R を閉じ括弧)とみなすと、正しい括弧列になっていなければなりません。
  • 各列について、上から下に U と D の杭だけを取り出します。U を開き括弧(、D を閉じ括弧)とみなすと、正しい括弧列になっていなければなりません。

空の括弧列も正しい括弧列とします。

すべての杭を打ち込んだあと、各括弧列で対応する開き括弧と閉じ括弧をペアにし、次のように高さを増やします。

  • 同じ行で対応する L と R のペアごとに、その行で2本の間にあるすべてのマスの高さを 11 増やします。
  • 同じ列で対応する U と D のペアごとに、その列で2本の間にあるすべてのマスの高さを 11 増やします。

どちらの場合も、そのペアの両端のマスには高さを加えません。22 本の間にあるマスには、そこに打ち込まれた杭の種類にかかわらず高さを加えます。あるマスが複数のペアの間にある場合は、ペアごとに高さが 11 ずつ増えます。

建設後のすべてのマスの高さが指定どおりになるような、杭の配置を 11 つ求めてください。

制約

  • 2≤N≤6002 \le N \le 600
  • 0≤Ai,j≤N0 \le A_{i,j} \le N
  • 入力はすべて整数
  • 条件を満たす杭の配置が少なくとも1つ存在する

入力

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

NN A1,1A1,2⋯A1,NA_{1,1} \quad A_{1,2} \quad \cdots \quad A_{1,N} A2,1A2,2⋯A2,NA_{2,1} \quad A_{2,2} \quad \cdots \quad A_{2,N} ⋮\vdots AN,1AN,2⋯AN,NA_{N,1} \quad A_{N,2} \quad \cdots \quad A_{N,N}

出力

条件を満たす杭の配置を、長さ NN の文字列 NN 個として、上の行から順に1行に1個ずつ出力してください。ii 行目の jj 文字目は、マス (i,j)(i,j) に打ち込む杭を表す L、R、U、D のいずれかとします。

条件を満たす配置が複数ある場合は、どれを出力してもかまいません。

入出力例

入力例 1

4
0 1 1 0
0 2 2 0
0 2 2 0
0 1 1 0

出力例 1

LUUR
LUUR
LDDR
LDDR

各行では、1列目と4列目の杭がペアになり、2列目と3列目の高さがそれぞれ 11 増えます。

2列目と3列目では、どちらも1行目と4行目の杭、2行目と3行目の杭がそれぞれペアになります。外側のペアによって、2行目と3行目の高さがさらに 11 増えます。内側のペアの間にはマスがありません。


入力例 2

2
0 0
0 0

出力例 2

LR
LR

各行の L と R は隣り合っており、その間にマスがありません。したがって、すべてのマスの高さは 00 のままです。


入力例 3

4
0 1 1 0
0 0 0 0
0 1 2 1
0 0 0 0

出力例 3

LLRR
LRUU
LLRR
LRDD

1行目と3行目では、1列目と4列目の杭がペアになり、2列目と3列目の高さを 11 増やします。また、3列目と4列目では、2行目の U と4行目の D がペアになり、3行目の高さを 11 増やします。

例えば、マス (3,3)(3,3) の高さは横と縦のペアからそれぞれ 11 ずつ増えて 22 になります。盤面の右端にあるマス (3,4)(3,4) の高さは、縦のペアによって 11 になります。

スペシャルジャッジ問題です。

参加受付は終了しました。