Estás intentando robar una valiosa tiara de diamantes de un museo. Lo que la hace tentadora es que (debido a recortes presupuestarios) todos los guardias han sido reemplazados por un único dron automático que patrulla el salón principal del museo. Sin embargo, lo que la hace menos tentadora es que este dron está equipado con armamento muy moderno y es probable que seas desintegrado si atraes su atención.
Afortunadamente, has hecho tu tarea y tienes una idea bastante clara de cómo funciona el dron. Imagina que el salón es un plano euclidiano, dividido en celdas de cuadrícula unitaria. La celda central, $(0, 0)$, contiene la tiara. El dron tiene una unidad de procesamiento simple que almacena dos cosas: su posición actual $(x, y)$ y la secuencia de instrucciones, denotada por las letras 'N', 'E', 'S', 'W'. Cada minuto, el dron se mueve a un punto adyacente según la primera letra de la secuencia (Norte, Sur, Oeste o Este), cambia la posición almacenada en consecuencia y luego mueve esta primera letra al final de la secuencia para acceder a la siguiente en el próximo minuto. Si la secuencia de instrucciones está vacía, el dron simplemente no hace nada. Se garantiza que estas instrucciones describen un bucle cerrado y que el dron nunca entra en la celda $(0, 0)$.
En este momento, el dron está en la posición $(x_0, y_0)$ y tiene una cadena $T$ de instrucciones. Puedes modificar la memoria del dron mediante un hábil hackeo; tu objetivo es llegar a una situación en la que el dron esté en la misma posición $(x_0, y_0)$, pero con una cadena diferente $T'$. Tu estrategia de hackeo, desafortunadamente, es algo limitada: cada minuto, solo puedes acceder a las dos primeras letras de la cadena y realizar cualquier número de las siguientes operaciones:
- eliminar las dos primeras letras de la cadena, pero solo si son "NS", "SN", "EW" o "WE";
- añadir dos letras "NS", "SN", "EW" o "WE" al frente de la cadena;
- intercambiar las dos primeras letras de la cadena (cualquier combinación de letras puede ser intercambiada).
Además, existe un sistema de detección de colisiones implementado en el dron, que detecta si el conjunto actual de instrucciones podría llevar al dron a $(0, 0)$. En este caso se activa una alarma; esta es la situación que quieres evitar a toda costa.
Encuentra una secuencia de operaciones de hackeo que lleve al dron a $(x_0, y_0)$ con la secuencia deseada $T'$ en su memoria.
Entrada
La primera línea de la entrada consiste en un solo número $z$ ($1 \le z \le 100$), que denota el número de casos de prueba. A continuación siguen las descripciones de los casos de prueba.
La primera línea de cada caso de prueba consiste en dos enteros $x_0, y_0$ ($-1000 \le x_0, y_0 \le 1000$), que denotan la posición inicial del dron. Al menos uno de los números $x_0, y_0$ no es cero.
La segunda línea contiene dos números $n, m$ ($2 \le n, m \le 2000$), la longitud de la cadena actual ($T$) y la cadena objetivo ($T'$), respectivamente.
Las siguientes dos líneas contienen una cadena cada una, de longitud $n$ y $m$ respectivamente, que denotan $T$ y $T'$, consistiendo solo en las letras N, S, E y W.
Se garantiza que las secuencias actual y objetivo son diferentes. Además, ambas describen bucles cerrados y ninguno de estos bucles cruza $(0, 0)$ en ningún momento de la ruta.
El número total de letras en todos los casos de prueba no supera los 20 000.
Salida
Para cada caso de prueba, si es imposible cumplir con los requisitos de la tarea, imprime "NO" en una sola línea. De lo contrario, imprime "YES" y luego una descripción de la solución en la siguiente línea. La solución debe consistir únicamente en símbolos $\{N, S, E, W, R, C, -\}$, donde cada carácter indica una única operación de hackeo:
- El símbolo 'N' significa añadir "NS" al frente de la cadena.
- De manera similar, los símbolos 'S', 'E' y 'W' significan añadir "SN", "EW" y "WE" al frente.
- El símbolo 'R' significa eliminar las dos primeras letras de la cadena; esto solo está permitido si estas letras son "NS", "SN", "EW" o "WE".
- El símbolo 'C' significa intercambiar las dos primeras letras.
- El símbolo '-' significa que esperas el resto del minuto (hasta que el dron se mueva a la siguiente instrucción).
Ten en cuenta que se pueden realizar múltiples hackeos en un solo minuto. No necesitas minimizar la longitud de la solución, pero la descripción de las acciones debe tener no más de $2 \cdot 10^7$ caracteres. Al final del último minuto de tu salida, la cadena y la posición del dron deben coincidir con las deseadas. No está permitido eliminar o intercambiar elementos de una cadena con menos de dos letras. En ningún momento el bucle descrito por la secuencia del dron puede pasar por $(0, 0)$.
Ejemplos
Entrada 1
2 1 0 10 10 NNWWSSSEEN NWWSSSEENN -1 0 8 8 NEESSWWN SEENNWWS
Salida 1
YES -C-C-R--S-C-C--- NO