Este problema tiene un archivo adjunto. Puedes usarlo para simular y visualizar los movimientos del robot.

VegiCat tiene un robot en una cuadrícula bidimensional infinita. Quiere que se mueva desde la celda $s = (s_x, s_y)$ hasta la celda $t = (t_x, t_y)$. Cada celda tiene coordenadas enteras. Las celdas $s$ y $t$ pueden ser la misma.

El robot sigue una cadena $p$ de instrucciones. Cada carácter es L, R, U o D. Sea $|p|$ la longitud de $p$.

El robot comienza en $s$. Antes de que ejecute cualquier instrucción, puedes colocar a lo sumo $|p|$ obstáculos en celdas distintas. Las coordenadas $(x, y)$ de cada obstáculo deben satisfacer $-2 \cdot 10^9 \le x, y \le 2 \cdot 10^9$. Ni $s$ ni $t$ pueden contener un obstáculo. Cada obstáculo ocupa una celda y permanece fijo durante todo el proceso; todas las demás celdas están libres de obstáculos.

El robot ejecuta las instrucciones $p_1, p_2, \ldots, p_{|p|}$ en orden. Para cada instrucción, comenzando desde su celda actual $(x, y)$, se mueve a lo largo de la siguiente secuencia de celdas:

• L: $(x, y) \to (x - 1, y) \to (x - 2, y) \to \cdots$;
• R: $(x, y) \to (x + 1, y) \to (x + 2, y) \to \cdots$;
• U: $(x, y) \to (x, y + 1) \to (x, y + 2) \to \cdots$;
• D: $(x, y) \to (x, y - 1) \to (x, y - 2) \to \cdots$.

El robot da repetidamente un paso en la dirección especificada mientras la siguiente celda no contenga ningún obstáculo. Se detiene en la celda inmediatamente anterior al primer obstáculo en esa dirección. Si la siguiente celda en la dirección especificada ya contiene un obstáculo antes de que comience la instrucción, el robot permanece en su lugar, pero la instrucción igualmente se completa. Si no hay ningún obstáculo más adelante en esa dirección, el robot se movería para siempre y la colocación es inválida.

El robot puede llegar a $t$ antes de que se completen todas las instrucciones. Aun así, debe ejecutar todas las instrucciones restantes. Construye cualquier colocación de obstáculos que satisfaga los requisitos anteriores de modo que el robot termine en $t$ después de la última instrucción, o informa que no existe tal colocación.

Entrada

La primera línea contiene un entero $T$ ($1 \le T \le 10^5$), el número de casos de prueba. A continuación sigue la descripción de los casos de prueba.

La primera línea de cada caso de prueba contiene dos enteros $s_x$ y $s_y$ ($-10^9 \le s_x, s_y \le 10^9$), las coordenadas de la celda inicial.

La segunda línea contiene dos enteros $t_x$ y $t_y$ ($-10^9 \le t_x, t_y \le 10^9$), las coordenadas de la celda objetivo.

La tercera línea contiene la cadena de instrucciones $p$ ($1 \le |p| \le 10^5$), formada únicamente por los caracteres L, R, U y D.

Se garantiza que la suma de $|p|$ en todos los casos de prueba no supera $10^5$.

Salida

Para cada caso de prueba, imprime una respuesta en el orden de entrada. Las colocaciones de obstáculos para diferentes casos de prueba son independientes.

Si no existe ninguna colocación válida, imprime NO en una línea por sí sola.

En caso contrario, imprime YES en la primera línea. En la segunda línea, imprime un entero $k$ ($0 \le k \le |p|$), el número de obstáculos.

Luego imprime $k$ líneas. La $i$-ésima de estas líneas debe contener dos enteros $x_i$ e $y_i$ ($-2 \cdot 10^9 \le x_i, y_i \le 2 \cdot 10^9$), especificando un obstáculo en la celda $(x_i, y_i)$.

Todos los $k$ pares de coordenadas deben ser distintos, y ninguno puede ser igual a $s$ o a $t$. La colocación debe permitir que cada instrucción termine y dejar al robot en $t$ después de la última instrucción. Si hay múltiples soluciones, imprime cualquiera de ellas.

Puedes imprimir el veredicto yes o no usando mayúsculas o minúsculas indistintamente. Por ejemplo, yEs, yes, Yes y YES se aceptan todas como respuestas positivas.

Ejemplos

Entrada 1

6
0 0
1 0
RL
0 0
-1 0
URD
0 0
8 0
RLR
0 0
0 0
UDUD
0 0
2 5
RDULR
0 0
1 1
RURURU

Salida 1

NO
NO
YES
2
-1 0
9 0
YES
2
0 -1
0 1
YES
5
-1 5
2 -1
2 6
3 0
3 5
YES
3
1 2
2 0
2 1