以下のような正方形のマスからなる無限に広いグリッドがあります。

各マスは整数 $x,y$ を用いて $(x,y)$ と表されます。マス $(x,y)$ に対して東・西・南・北のマスはそれぞれ次のように表されます。

• 東: $(x+1,y)$
• 西: $(x-1,y)$
• 南: $(x,y-1)$
• 北: $(x,y+1)$

はじめ、マス $(s_x, s_y)$ に立方体が置かれています。立方体の「上面」には青い印があり、それ以外の面には何も書かれていません。

あなたは立方体を隣接するマスに $1$ マスずつ転がすことで次の目的を達成したいです。

目的

• 立方体はマス $(g_x, g_y)$ にあり、青い印のある面が「底面」になっている。

上記の目的を達成するような立方体の転がし方の手順を $1$ つ出力してください。

ただし、立方体の各面の面積はグリッドの $1$ マスの面積と等しく、立方体は底面の各辺がグリッドの軸と平行になるように置くものとします。

Hard (100点)

• $-10^9 \leq s_x,s_y,g_x,g_y \leq 10^9$
• 入力はすべて整数

Normal (75点)

• Hard の制約に以下の制約を追加
• $-250 \leq s_x,s_y,g_x,g_y \leq 250$

Easy (25点)

• Hard の制約に以下の制約を追加
• $s_x = s_y = 0$
• $0 \leq g_x, g_y \leq 2$

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

以下の形式で、整数 $N$、 移動方向を表す文字 $D_1, D_2, \ldots, D_N$、および移動距離を表す整数 $L_1, L_2, \ldots, L_N$ を出力せよ。

ここで、$N$ は $1$ 以上 $10^5$ 以下の整数、$D_i$ は L、R、U、D のいずれか、$L_i$ は $1$ 以上 $10^{10}$ 以下の整数でなければならない。

また、$L_1$ 文字の $D_1$、$L_2$ 文字の $D_2$、$\cdots$、$L_N$ 文字の $D_N$ をこの順番に並べてできる文字列を $S$ とし、$S$ を以下の通り解釈し操作を最後まで行った後、目的を達成している必要がある。

上記の条件を満たす答えが複数存在する場合、どれを出力しても構わない。

なお、本問題の制約下で条件を満たす答えが必ず存在することが証明できる。