Патрульный дрон
Вы пытаетесь украсть из музея очень ценную бриллиантовую тиару. Это делает заманчивым тот факт, что из-за сокращения бюджета всех охранников заменил один автоматический дрон, который патрулирует главный зал музея. Однако этот дрон оснащен современным вооружением, и Вы будете уничтожены, если привлечете его внимание.
К счастью, Вы сделали домашнее задание и довольно хорошо понимаете, как работает дрон. Представьте себе, что зал представляет собой евклидову плоскость, разделенную на единичные квадратные ячейки. Центральная ячейка (0, 0) содержит тиару. Дрон имеет простой процессор, который хранит две вещи: его текущее положение (x, y) и последовательность инструкций, обозначаемую буквами 'N', 'E', 'S', 'W'. Каждую минуту дрон перемещается в соседнее место в соответствии с первой буквой последовательности (север, юг, запад или восток), соответствующим образом меняя текущую позицию. Затем дрон перемещает эту первую букву в конец последовательности, получая доступ к следующей в следующую минуту. Если последовательность инструкций пуста, дрон ничего не делает. Гарантируется, что эти инструкции описывают замкнутый цикл и что дрон никогда не входит в ячейку (0, 0).
Прямо сейчас дрон находится в позиции (x[0], y[0]) и имеет строку T инструкций. Вы можете модифицировать память дрона с помощью хитрого трюка: Ваша цель - достичь ситуации, в которой дрон находится в той же позиции (x[0], y[0]), но с другой строкой T'. Ваша стратегия взлома, к сожалению, несколько ограничена - каждую минуту Вы можете получить доступ только к двум первым буквам строки и выполнить любое количество следующих операций:
удалить две начальные буквы из строки, но только если это "NS", "SN", "EW" или "WE";
добавить две буквы "NS", "SN", "EW" или "WE" в начало строки;
поменять местами две начальные буквы строки (можно поменять местами любую комбинацию букв).
Кроме того, на дроне реализована система обнаружения столкновений, которая определяет, может ли текущий набор инструкций привести дрон к (0, 0). В этом случае поднимается тревога - это ситуация, которую Вы хотите избежать любой ценой.
Найдите последовательность операций взлома, которая приведет дрон к (x[0], y[0]) с желаемой последовательностью T' в его памяти.
Входные данные
Первая строка содержит количество тестов z (1 ≤ z ≤ 100). Далее следуют описания тестов.
Первая строка каждого теста состоит из двух целых чисел x[0], y[0] (-1000 ≤ x[0], y[0] ≤ 1000), обозначающее начальное положение дрона. По крайней мере одно из чисел x[0], y[0] не равно нулю.
Вторая строка содержит два числа n, m (2 ≤ n, m ≤ 2000) - длина текущей (T) и целевой (T') строки соответственно.
Следующие две строки содержат по одной строке длины n и m соответственно, обозначающие T и T', состоящие только из букв N, S, E и W.
Гарантируется, что текущая и целевая последовательности различны. Более того, обе описывают некоторые замкнутые петли, и ни одна из этих петель не пересекает (0, 0) ни в какой момент маршрута.
Общее количество букв во всех тестах не превышает 20 000.
Выходные данные
Для каждого теста, если выполнить требования задачи невозможно, в отдельной строке выведите "NO". В противном случае выведите "YES", а затем описание решения на следующей строке. Решение должно состоять только из символов {C, N, S, E, W , −, R}, где каждый символ указывает на одну операцию взлома:
Символ 'N' означает добавление "NS" в начале строки.
Точно так же символы 'S', 'E' и 'W' означают добавление "SN", "EW" и "WE" спереди.
Символ 'R' означает удаление двух первых букв из строки - это разрешено, только если это буквы "NS", "SN", "EW" или "WE".
Символ 'C' означает перестановку двух первых букв.
Символ '-' означает, что Вы ждете остаток минуты (пока дрон не перейдет к следующей инструкции).
Обратите внимание, что за одну минуту можно совершить несколько взломов. Вам не следует минимизировать длину решения, однако описание действий должно содержать не более 2 * 10^7 символов. К концу последней минуты Вашего вывода строка и положение дрона должны совпадать с желаемыми. Удаление или замена элементов строки, содержащих не более одной буквы, не допускается. Ни в коем случае петля, описанная последовательностью дрона, не может пройти через (0, 0).