Avez-vous déjà entendu parler du problème de la distance d'édition ? Étant donné deux chaînes de lettres anglaises minuscules, vous devez déterminer le nombre minimum d'opérations nécessaires pour transformer la première en la seconde. Une opération unique peut être :

• l'insertion d'un caractère dans la séquence, à n'importe quel endroit,
• la suppression de n'importe quel caractère de la séquence,
• la substitution d'un caractère par un autre.

Tout le monde dans notre université adore ce problème – peut-être un peu trop – alors nous avons décidé de créer un problème plus facile ! On vous donne deux chaînes $s = s_1 \dots s_n$, $t = t_1 \dots t_m$ et un entier $k$. Déterminez si la distance d'édition entre les chaînes est inférieure ou égale à $k$. Si c'est le cas, vous devez également fournir une séquence quelconque du nombre minimum possible d'opérations pour transformer la première chaîne en la seconde.

Entrée

La première ligne de l'entrée contient le nombre de cas de test $z$ ($1 \le z \le 100$). Les descriptions des cas de test suivent.

La première ligne de chaque cas de test contient trois entiers $n, m, k$ ($1 \le n, m \le 1\,000\,000$, $0 \le k \le 1000$) – les longueurs des chaînes et le paramètre de la description du problème.

La deuxième ligne contient une chaîne de longueur $n$ composée de lettres anglaises minuscules – la chaîne $s$ de la description du problème.

La troisième ligne contient une chaîne de longueur $m$ composée de lettres anglaises minuscules – la chaîne $t$ de la description du problème.

La longueur totale de toutes les chaînes dans tous les cas de test ne dépassera pas $10^7$.

Sortie

Pour chaque cas de test, si la distance d'édition est supérieure à $k$, affichez une seule ligne contenant le mot « NO ». Sinon, la première ligne doit contenir le mot « YES », et les lignes suivantes doivent décrire la réponse comme suit :

Sur la deuxième ligne, affichez le nombre minimum $r$ d'opérations nécessaires pour transformer $s$ en $t$. Dans les $r$ lignes suivantes, affichez les opérations, une par ligne.

• Pour insérer un caractère anglais minuscule $c$ dans une séquence de taille $w$ à la position $p$ ($1 \le p \le w + 1$), affichez INSERT p c.
• Pour supprimer un caractère d'une séquence de taille $w$ à la position $p$ ($1 \le p \le w$), affichez DELETE p.
• Pour substituer un caractère dans une séquence de taille $w$ à la position $p$ ($1 \le p \le w$) par un caractère anglais minuscule $c$, affichez REPLACE p c.

Exemples

Entrée 1

2
3 4 3
kot
plot
5 7 3
zycie
porazka

Sortie 1

YES
2
REPLACE 1 l
INSERT 1 p
NO