Patrol Drone#11110
You are overseeing a valuable artifact at a museum, protected by an advanced patrol drone. Due to recent budget cuts, all security except for an automatic drone has been removed, and the main hall is now supervised by this single machine. The drone is equipped with modern detection systems, so any attempt to breach its protocols would trigger an alarm and deploy countermeasures.
Fortunately, you have access to the drone's operational routines and have learned how its software works. The museum hall can be mapped as a Euclidean plane, divided into unit square cells. The central cell contains the artifact. The drone's processor keeps track of two things: its current position and an instruction sequence, represented by the letters , , , . Every minute, the drone moves to an adjacent cell according to the first letter of the sequence (North, South, West, or East), updates its position, then moves that letter to the end of the sequence for the next minute. If the instruction sequence is empty, the drone does nothing. These instructions always form a closed loop, and the drone never enters the cell.
At the moment, the drone is at position (x_0, y_0) and is following instruction sequence . You can reprogram the drone's memory—your goal is to change the current instruction sequence into a new sequence T', with the drone remaining at position (x_0, y_0). However, your changes are limited: each minute, you can access only the two first letters of the sequence and perform any of the following operations, any number of times:
Remove the two front letters, but only if they are , , , or ;
Add , , , or at the front of the sequence;
Swap the first two letters (any combination).
The drone's collision system will detect if the current instruction set would ever lead the drone to —in that case, an alarm is triggered, which must be avoided at all costs.
Find a sequence of operations to convert into T' while keeping the drone at (x_0, y_0) at every stage and never allowing its path to pass through .
The first line consists of a single number (1 \le z \le 100), denoting the number of test cases. Then follow the descriptions of the test cases.
For each test case, the first line consists of two integers x_0, y_0 (-1000 \le x_0, y_0 \le 1000), denoting the initial position of the drone. At least one of x_0, y_0 is not zero.
The next line contains two integers , (2 \le n, m \le 2000)—the lengths of the current sequence and the target sequence T'.
The following two lines each contain one string of length and , respectively, consisting only of , , , and , representing and T'.
The current and target sequences are guaranteed to be different. Both describe closed loops, and neither loop ever passes through .
The total number of letters in all test cases does not exceed .
For each test case, if it is impossible to achieve the goal, output "NO" in a single line. Otherwise, output "YES", and then a solution description on the next line. The solution must consist only of symbols \{C, N, S, E, W, -, R\}, where each character indicates a single operation:
: add at the front;
, , : add , , at the front, respectively;
: remove the first two letters, but only if they are , , , or ;
: swap the first two letters;
: wait for the rest of the minute (until the drone moves to the next instruction).
Several operations may be performed in a single minute. You do not need to minimize the solution length, but the action description must be no longer than 2 \times 10^7 characters. At the end of the last minute, the drone's position and instruction sequence must match T' at (x_0, y_0). Removing or swapping string elements is only allowed if there are at least two letters. At no point can the sequence cause the drone's path to include .
Example 1