¿Alguna vez has oído hablar del problema de la distancia de edición? Dadas dos cadenas de letras minúsculas en inglés, debes determinar el número mínimo de operaciones necesarias para transformar la primera en la segunda. Una sola operación puede ser cualquiera de las siguientes:

• insertar un carácter en la secuencia, en cualquier lugar,
• eliminar cualquier carácter de la secuencia,
• sustituir un carácter por otro.

A todos en nuestra universidad les encanta este problema —quizás un poco demasiado—, así que decidimos crear un problema que sea más fácil. Se te dan dos cadenas $s = s_1 \dots s_n$, $t = t_1 \dots t_m$ y un entero $k$. Averigua si la distancia de edición entre las cadenas es menor o igual a $k$. Si es así, también se te pide proporcionar cualquier secuencia del número mínimo posible de operaciones para transformar la primera cadena en la segunda.

Entrada

La primera línea de la entrada contiene el número de casos de prueba $z$ ($1 \le z \le 100$). A continuación siguen las descripciones de los casos de prueba.

La primera línea de cada caso de prueba contiene tres enteros $n, m, k$ ($1 \le n, m \le 1\,000\,000$, $0 \le k \le 1000$), las longitudes de las cadenas y el parámetro del problema.

La segunda línea contiene una cadena de longitud $n$ que consiste en letras minúsculas en inglés, la cadena $s$ del problema.

La tercera línea contiene una cadena de longitud $m$ que consiste en letras minúsculas en inglés, la cadena $t$ del problema.

La longitud total de todas las cadenas en todos los casos de prueba no excederá $10^7$.

Salida

Para cada caso de prueba, si la distancia de edición es mayor que $k$, imprime una sola línea que contenga la palabra “NO”. De lo contrario, la primera línea debe contener la palabra “YES”, y las siguientes líneas deben describir la respuesta de la siguiente manera:

En la segunda línea, imprime el número mínimo $r$ de operaciones requeridas para transformar $s$ en $t$. En las siguientes $r$ líneas, imprime las operaciones, una por línea:

• Para insertar un carácter minúsculo en inglés $c$ en una secuencia de tamaño $w$ en la posición $p$ ($1 \le p \le w + 1$), imprime INSERT p c.
• Para eliminar un carácter de una secuencia de tamaño $w$ en la posición $p$ ($1 \le p \le w$), imprime DELETE p.
• Para sustituir un carácter en una secuencia de tamaño $w$ en la posición $p$ ($1 \le p \le w$) por un carácter minúsculo en inglés $c$, imprime REPLACE p c.

Ejemplos

Entrada 1

2
3 4 3
kot
plot
5 7 3
zycie
porazka

Salida 1

YES
2
REPLACE 1 l
INSERT 1 p
NO