Патрульний дрон#11110
Ви наглядаєте за цінним артефактом у музеї, який охороняє сучасний патрульний дрон. Через нещодавні скорочення бюджету всю охорону, окрім автоматичного дрона, було знято, і головний зал тепер наглядається лише цією однією машиною. Дрон оснащений найсучаснішою системою виявлення, тому будь-яка спроба порушити його протоколи спровокує сигнал тривоги й активацію протидії.
На щастя, у вас є доступ до операційних рутин дрона, і ви вивчили принцип роботи його програмного забезпечення. Зал музею можна зобразити у вигляді евклідової площини, розбитої на клітинки розміром 1\times1. Центральна клітинка містить артефакт. Процесор дрона відстежує дві речі: його поточну позицію та послідовність інструкцій, представлену літерами , , , . Щохвилини дрон переходить у сусідню клітинку згідно з першою літерою послідовності (північ, південь, захід чи схід), оновлює свою позицію, після чого переносить цю літеру в кінець послідовності на наступну хвилину. Якщо послідовність інструкцій порожня, дрон не рухається. Ці інструкції завжди утворюють замкнений цикл, і дрон ніколи не заходить у клітинку .
Наразі дрон знаходиться у позиції (x_0, y_0) та виконує послідовність інструкцій . Ви можете перепрограмувати пам'ять дрона—ваше завдання перетворити поточну послідовність інструкцій на нову T', залишивши дрона у позиції (x_0, y_0). Однак ваші можливості обмежені: щохвилини ви маєте доступ лише до двох перших літер послідовності й можете виконати будь-яку з наступних операцій у будь-якій кількості разів:
Видалити дві перші літери, але лише якщо це , , або ;
Додати , , або на початок послідовності;
Поміняти місцями дві перші літери (у будь-якому поєднанні).
Система зіткнень дрона виявить, якщо чинна послідовність інструкцій змусить дрона потрапити у —у такому разі зразу спрацює сигнал тривоги, чого треба уникнути за будь-яку ціну.
Знайдіть послідовність операцій, щоб перетворити у T', причому дрон повинен залишатися у (x_0, y_0) на кожному етапі й жоден проміжний маршрут дрона не повинен проходити через .
У першому рядку записано одне число (1 \le z \le 100)—кількість тестових випадків. Далі наведено описи тестів.
У кожному тестовому випадку у першому рядку два цілих числа x_0, y_0 (-1000 \le x_0, y_0 \le 1000)—початкова позиція дрона. Принаймні одне з x_0, y_0 не дорівнює нулю.
У наступному рядку два цілих числа , (2 \le n, m \le 2000)—довжина поточної послідовності та цільової послідовності T'.
У наступних двох рядках записані рядки довжиною та відповідно, що складаються лише з літер , , , , та відповідають та T'.
Поточна та цільова послідовності гарантовано різні. Обидві утворюють замкнені цикли, і жодна не проходить через .
Загальна кількість літер у всіх тестах не перевищує .
Для кожного тесту, якщо виконати завдання неможливо, виведіть у одному рядку "NO". Інакше виведіть "YES", а у наступному рядку—опис розв’язку. Розв’язок має складатися лише з символів \{C, N, S, E, W, -, R\}, де кожен символ означає окрему дію:
: додати на початок;
, , : додати , , на початок відповідно;
: забрати перші дві літери, але лише якщо це , , або ;
: поміняти місцями дві перші літери;
: чекати до кінця хвилини (доки дрон перейде до наступної інструкції).
Кілька операцій можна виконати за одну хвилину. Вам не потрібно мінімізувати довжину розв’язку, але опис дій має містити не більше 2 \times 10^7 символів. У кінці останньої хвилини позиція дрона і послідовність інструкцій мають відповідати T' у (x_0, y_0). Видаляти або міняти місцями елементи рядка дозволяється лише якщо у рядку є принаймні дві літери. На жодному етапі послідовність не повинна призвести до потрапляння дрона у .
Приклад 1