Já ouviu falar do problema da distância de edição? Dadas duas cadeias de letras minúsculas do alfabeto inglês, deve determinar o número mínimo de operações necessárias para transformar a primeira na segunda. Uma operação pode ser:

• Inserir um carácter em qualquer posição da sequência;
• Eliminar qualquer carácter da sequência;
• Substituir um carácter por outro.

Todos na nossa universidade adoram este problema, talvez até um pouco demais, por isso decidimos criar um problema mais fácil! São dadas duas cadeias $s=s_1\ldots s_n$, $t=t_1\ldots t_m$ e um inteiro $k$. Determine se a distância de edição entre as cadeias é menor ou igual a $k$. Se for, deve também fornecer qualquer sequência com o menor número possível de operações que transforme a primeira cadeia na segunda.

Entrada

A primeira linha da entrada contém o número de casos de teste $z$ ($1 \le z \le 100$). Seguem-se as descrições dos casos de teste.

A primeira linha de cada caso de teste contém três inteiros $n,m,k$ ($1 \le n,m \le 1\,000\,000$, $0 \le k \le 1000$): os comprimentos das cadeias e o parâmetro da descrição do problema.

A segunda linha contém uma cadeia de comprimento $n$ composta por letras minúsculas do alfabeto inglês: a cadeia $s$ da descrição do problema.

A terceira linha contém uma cadeia de comprimento $m$ composta por letras minúsculas do alfabeto inglês: a cadeia $t$ da descrição do problema.

O comprimento total de todas as cadeias de todos os casos de teste não excederá $10^7$.

Saída

Para cada caso de teste, se a distância de edição for superior a $k$, imprima uma única linha com a palavra NO. Caso contrário, a primeira linha deve conter a palavra YES, e as linhas seguintes devem descrever a resposta da seguinte forma:

Na segunda linha, imprima o número mínimo $r$ de operações necessárias para transformar $s$ em $t$. Nas $r$ linhas seguintes, imprima as operações, uma por linha.

• Para inserir um carácter minúsculo do alfabeto inglês $c$ na posição $p$ ($1 \le p \le w+1$) de uma sequência de tamanho $w$, imprima INSERT p c.
• Para eliminar o carácter na posição $p$ ($1 \le p \le w$) de uma sequência de tamanho $w$, imprima DELETE p.
• Para substituir o carácter na posição $p$ ($1 \le p \le w$) de uma sequência de tamanho $w$ por um carácter minúsculo do alfabeto inglês $c$, imprima REPLACE p c.

Exemplos

Entrada 1

2
3 4 3
kot
plot
5 7 3
zycie
porazka

Saída 1

YES
2
REPLACE 1 l
INSERT 1 p
NO