Haben Sie schon einmal vom Editierdistanzproblem gehört? Gegeben sind zwei Zeichenketten aus englischen Kleinbuchstaben. Sie sollen die minimale Anzahl von Operationen bestimmen, um die erste in die zweite umzuwandeln. Eine einzelne Operation kann sein:

• Ein Zeichen an einer beliebigen Stelle in die Folge einfügen,
• ein beliebiges Zeichen aus der Folge löschen,
• ein Zeichen durch ein anderes ersetzen.

Alle an unserer Universität lieben diese Aufgabe sehr, vielleicht ein wenig zu sehr. Deshalb haben wir beschlossen, eine einfachere Aufgabe zu stellen! Gegeben sind zwei Zeichenketten $s=s_1\ldots s_n$, $t=t_1\ldots t_m$ und eine ganze Zahl $k$. Bestimmen Sie, ob ihre Editierdistanz höchstens $k$ beträgt. Wenn ja, geben Sie außerdem eine beliebige Folge mit der kleinstmöglichen Anzahl von Operationen an, die die erste Zeichenkette in die zweite umwandelt.

Eingabe

Die erste Eingabezeile enthält die Anzahl der Testfälle $z$ ($1 \le z \le 100$). Darauf folgen die Beschreibungen der Testfälle.

Die erste Zeile jedes Testfalls enthält drei ganze Zahlen $n,m,k$ ($1 \le n,m \le 1\,000\,000$, $0 \le k \le 1000$), die Längen der Zeichenketten und den Parameter aus der Aufgabenstellung.

Die zweite Zeile enthält eine Zeichenkette der Länge $n$ aus englischen Kleinbuchstaben, die Zeichenkette $s$ aus der Aufgabenstellung.

Die dritte Zeile enthält eine Zeichenkette der Länge $m$ aus englischen Kleinbuchstaben, die Zeichenkette $t$ aus der Aufgabenstellung.

Die Gesamtlänge aller Zeichenketten in allen Testfällen überschreitet $10^7$ nicht.

Ausgabe

Ist die Editierdistanz in einem Testfall größer als $k$, geben Sie eine einzelne Zeile mit dem Wort NO aus. Andernfalls enthält die erste Zeile das Wort YES, und die folgenden Zeilen beschreiben die Antwort wie folgt:

Geben Sie in der zweiten Zeile die minimale Anzahl $r$ von Operationen aus, um $s$ in $t$ umzuwandeln. Geben Sie in den nächsten $r$ Zeilen die Operationen aus, eine pro Zeile.

• Um einen englischen Kleinbuchstaben $c$ an Position $p$ ($1 \le p \le w+1$) in eine Folge der Länge $w$ einzufügen, geben Sie INSERT p c aus.
• Um aus einer Folge der Länge $w$ das Zeichen an Position $p$ ($1 \le p \le w$) zu löschen, geben Sie DELETE p aus.
• Um in einer Folge der Länge $w$ das Zeichen an Position $p$ ($1 \le p \le w$) durch den englischen Kleinbuchstaben $c$ zu ersetzen, geben Sie REPLACE p c aus.

Beispiele

Eingabe 1

2
3 4 3
kot
plot
5 7 3
zycie
porazka

Ausgabe 1

YES
2
REPLACE 1 l
INSERT 1 p
NO