あなたは博物館から非常に価値のあるダイヤモンドのティアラを盗もうとしています。この計画が魅力的なのは、（予算削減により）すべての警備員が博物館のメインホールを巡回する単一の自動ドローンに置き換えられているからです。しかし、このドローンには非常に近代的な兵器が装備されており、注意を引くと粉砕される可能性が高いため、あまり魅力的とは言えません。
幸いなことに、あなたは事前の調査により、このドローンの仕組みをかなり正確に把握しています。ホールはユークリッド平面であり、単位正方形のセルに分割されていると想像してください。中心のセル $(0, 0)$ にティアラがあります。ドローンは、現在の位置 $(x, y)$ と、文字 'N', 'E', 'S', 'W' で表される命令のシーケンスを格納する単純な処理ユニットを持っています。毎分、ドローンはシーケンスの最初の文字（北、南、西、東）に従って隣接する地点へ移動し、それに応じて格納されている位置を変更し、この最初の文字をシーケンスの最後尾に移動させて、次の分に次の命令にアクセスできるようにします。命令シーケンスが空の場合、ドローンは何もしません。これらの命令は閉じたループを記述しており、ドローンが $(0, 0)$ のセルに入ることは決してないことが保証されています。
現在、ドローンは位置 $(x_0, y_0)$ にあり、命令の文字列 $T$ を持っています。あなたは巧妙なハッキングによってドローンのメモリを修正できます。あなたの目標は、ドローンが同じ位置 $(x_0, y_0)$ にありながら、異なる文字列 $T'$ を持っている状況に到達することです。残念ながら、あなたのハッキング戦略はいくぶん制限されており、毎分、文字列の先頭の2文字にのみアクセスでき、以下の操作を任意の回数実行できます。
- 文字列の先頭2文字が "NS", "SN", "EW", "WE" のいずれかである場合に限り、その2文字を削除する。
- 文字列の先頭に "NS", "SN", "EW", "WE" のいずれか2文字を追加する。
- 文字列の先頭2文字を入れ替える（任意の文字の組み合わせを入れ替え可能）。
また、ドローンには衝突検知システムが実装されており、現在の命令セットがドローンを $(0, 0)$ に導く可能性があるかどうかを検知します。その場合、警報が鳴ります。これは何としても避けたい状況です。
ドローンを $(x_0, y_0)$ に留めつつ、メモリ内の命令シーケンスを目的の $T'$ に変更するハッキング操作のシーケンスを見つけてください。
入力
入力の最初の行は、テストケースの数 $z$ ($1 \le z \le 100$) を表す単一の整数です。続いて各テストケースの説明が続きます。
各テストケースの最初の行は、ドローンの初期位置を表す2つの整数 $x_0, y_0$ ($-1000 \le x_0, y_0 \le 1000$) です。$x_0, y_0$ の少なくとも一方はゼロではありません。
2行目には、現在の文字列 $T$ と目標の文字列 $T'$ の長さを表す2つの数値 $n, m$ ($2 \le n, m \le 2000$) が含まれています。
続く2行には、それぞれ長さ $n$ と $m$ の文字列 $T$ と $T'$ が含まれており、これらは 'N', 'S', 'E', 'W' の文字のみで構成されています。
現在のシーケンスと目標のシーケンスは異なることが保証されています。さらに、両者とも閉じたループを記述しており、どちらのループも経路上のいかなる時点でも $(0, 0)$ を通過しません。
すべてのテストケースにおける文字の総数は 20,000 を超えません。
出力
各テストケースについて、タスクの要件を満たすことが不可能な場合は、1行で "NO" と出力してください。可能な場合は "YES" と出力し、次の行に解決策の説明を出力してください。解決策は、以下の単一のハッキング操作を表す記号 $\{N, S, E, W, R, -, C\}$ のみで構成される必要があります。
- 記号 'N' は、文字列の先頭に "NS" を追加することを意味します。
- 同様に、記号 'S', 'E', 'W' は、文字列の先頭に "SN", "EW", "WE" を追加することを意味します。
- 記号 'R' は、文字列の先頭2文字を削除することを意味します。これは、これらの文字が "NS", "SN", "EW", "WE" である場合にのみ許可されます。
- 記号 'C' は、先頭2文字を入れ替えることを意味します。
- 記号 '-' は、その分の残りの時間（ドローンが次の命令に移動するまで）待機することを意味します。
1分間に複数のハッキングを行えることに注意してください。解決策の長さを最小化する必要はありませんが、アクションの説明は $2 \cdot 10^7$ 文字以下でなければなりません。出力の最後の分の終わりまでに、文字列とドローンの位置が目的のものと一致している必要があります。1文字以下の文字列に対して要素を削除または入れ替えることは許可されません。ドローンのシーケンスが記述するループは、いかなる時点でも $(0, 0)$ を通過してはなりません。
入出力例
入力 1
2 1 0 10 10 NNWWSSSEEN NWWSSSEENN -1 0 8 8 NEESSWWN SEENNWWS
出力 1
YES -C-C-R--S-C-C--- NO