この問題には添付ファイルがあります。ロボットの移動をシミュレートおよび可視化するために使用できます。

VegiCat は無限に広がる 2 次元グリッド上にロボットを持っています。彼はロボットをマス $s = (s_x, s_y)$ からマス $t = (t_x, t_y)$ まで移動させたいと考えています。各マスは整数座標を持ちます。マス $s$ と $t$ は同じである場合もあります。

ロボットは命令の文字列 $p$ に従います。各文字は L, R, U, D のいずれかです。$p$ の長さを $|p|$ と表します。

ロボットは $s$ から出発します。ロボットが命令を実行する前に、異なるマスに最大 $|p|$ 個の障害物を配置できます。各障害物の座標 $(x, y)$ は $-2 \cdot 10^9 \le x, y \le 2 \cdot 10^9$ を満たさなければなりません。$s$ と $t$ のどちらにも障害物を置くことはできません。各障害物は 1 つのマスを占め、過程を通じて固定されたままになります。他のすべてのマスには障害物がありません。

ロボットは命令 $p_1, p_2, \ldots, p_{|p|}$ を順番に実行します。各命令について、現在のマス $(x, y)$ から出発し、以下のマスの列に沿って移動します：

• L: $(x, y) \to (x - 1, y) \to (x - 2, y) \to \cdots$;
• R: $(x, y) \to (x + 1, y) \to (x + 2, y) \to \cdots$;
• U: $(x, y) \to (x, y + 1) \to (x, y + 2) \to \cdots$;
• D: $(x, y) \to (x, y - 1) \to (x, y - 2) \to \cdots$.

ロボットは、指定された方向の次のマスに障害物がない限り、その方向に 1 歩ずつ繰り返し進みます。そして、その方向にある最初の障害物の直前のマスで停止します。命令が始まる前に指定された方向の次のマスにすでに障害物がある場合、ロボットはその場に留まりますが、命令自体は完了したものとみなされます。その方向の前方に障害物が存在しない場合、ロボットは永遠に移動し続けることになり、そのような配置は無効です。

すべての命令が完了する前にロボットが $t$ に到達することがあります。その場合でも、残りのすべての命令を実行しなければなりません。最後の命令の後にロボットが $t$ で終了するような、上記の要件を満たす障害物の配置を 1 つ構築するか、そのような配置が存在しないことを報告してください。

入力

最初の行には、テストケースの数を表す整数 $T$（$1 \le T \le 10^5$）が含まれます。続いて各テストケースの説明が与えられます。

各テストケースの 1 行目には、開始マスの座標を表す 2 つの整数 $s_x$ と $s_y$（$-10^9 \le s_x, s_y \le 10^9$）が含まれます。

2 行目には、目標マスの座標を表す 2 つの整数 $t_x$ と $t_y$（$-10^9 \le t_x, t_y \le 10^9$）が含まれます。

3 行目には、文字 L, R, U, D のみからなる命令文字列 $p$（$1 \le |p| \le 10^5$）が含まれます。

すべてのテストケースにおける $|p|$ の総和は $10^5$ を超えないことが保証されています。

出力

各テストケースについて、入力順に答えを出力してください。異なるテストケースに対する障害物の配置は互いに独立です。

有効な配置が存在しない場合は、NO を 1 行に出力してください。

そうでない場合は、1 行目に YES を出力してください。2 行目には、障害物の個数を表す整数 $k$（$0 \le k \le |p|$）を出力してください。

その後、$k$ 行を出力してください。これらのうち $i$ 行目には、マス $(x_i, y_i)$ に障害物を配置することを表す 2 つの整数 $x_i$ と $y_i$（$-2 \cdot 10^9 \le x_i, y_i \le 2 \cdot 10^9$）を含めなければなりません。

$k$ 個の座標の組はすべて互いに異なり、いずれも $s$ や $t$ と等しくてはなりません。配置はすべての命令が終了し、最後の命令の後にロボットが $t$ に残るようなものでなければなりません。複数の解がある場合は、そのうちのどれを出力しても構いません。

yes または no の判定結果は大文字・小文字を問わず出力できます。たとえば、yEs, yes, Yes, YES はすべて肯定の応答として受理されます。

入出力例

入力 1

6
0 0
1 0
RL
0 0
-1 0
URD
0 0
8 0
RLR
0 0
0 0
UDUD
0 0
2 5
RDULR
0 0
1 1
RURURU

出力 1

NO
NO
YES
2
-1 0
9 0
YES
2
0 -1
0 1
YES
5
-1 5
2 -1
2 6
3 0
3 5
YES
3
1 2
2 0
2 1