Патрульний дрон
Ви плануєте викрасти з музею дуже цінну діамантову тіару. Завдяки скороченню бюджету, охорону музею здійснює лише один автоматичний дрон, який патрулює головний зал. Однак, дрон оснащений сучасною зброєю, і якщо ви привернете його увагу, це може бути небезпечно.
На щастя, ви добре підготувалися і знаєте, як працює дрон. Уявіть, що зал — це евклідова площина, розділена на одиничні квадратні клітинки. Центральна клітинка (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).