Magic Path

$N\times M$ のグリッドの各マスには、人が住んでいるか、住んでいないかのいずれかです。行には上から順に $0,1,\cdots,N-1$、列には左から順に $0,1,\cdots,M-1$ の番号が付けられています。格子点の座標を $(i,j)$ と表し、$0\le i\le N$、$0\le j\le M$ です。

$(0,0)$ から $(N,M)$ まで、グリッドの辺に沿って移動する経路を一つ出力してください。1 回の移動では、上下左右に隣接する格子点へ移動できます。グリッドの外へ出ることはできません。

人が住んでいる各マスについて、そのマスを構成する四つの頂点のうち一つ以上を経路が訪れた場合、そのマスでコスト $1$ が発生します。同じマスの頂点を複数回訪れても、そのマスのコストは一度しか数えません。経路のコストは、コストが発生したマスの個数です。

具体的な得点の計算方法については、Scoring セクションを参照してください。

入力は次の形式で与えられます。

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

各テストケースについて、次の 2 行を出力してください。

$C\ K$ $S$

$S$ は長さ $K$ の文字列であり、各文字は U, D, L, R のいずれかです。それぞれ、現在の格子点から上、下、左、右に隣接する格子点へ移動することを表します。

$S$ が表す移動は から始まり、常にグリッド内になければならず、最後には に到達しなければなりません。

• $1\le T\le 100\,000$.
• $1\le N,M\le 1\,000$.
• すべてのテストケースにおける の総和は 以下です。

この問題の採点はサブタスクごとに独立して行われ、以下の近似比に関する基準はすべてのサブタスクに同様に適用されます。

各テストケースの最適コストを $o$、参加者が出力した有効な経路の実際のコストを $a$ とします。近似比 $c$ を次のように定義します。