Czy słyszałeś kiedyś o problemie odległości edycyjnej? Mając dwa ciągi małych liter alfabetu angielskiego, musisz wyznaczyć minimalną liczbę operacji potrzebnych do przekształcenia pierwszego z nich w drugi. Pojedyncza operacja może polegać na:

• wstawieniu znaku do ciągu w dowolnym miejscu,
• usunięciu dowolnego znaku z ciągu,
• zamianie znaku na inny.

Wszyscy na naszej uczelni bardzo lubią ten problem – może nawet trochę za bardzo – więc postanowiliśmy stworzyć problem, który jest łatwiejszy! Dane są dwa ciągi $s = s_1 \dots s_n$, $t = t_1 \dots t_m$ oraz liczba całkowita $k$. Sprawdź, czy odległość edycyjna między tymi ciągami jest mniejsza lub równa $k$. Jeśli tak, poprosimy Cię również o podanie dowolnej sekwencji operacji o minimalnej możliwej liczbie kroków, która przekształca pierwszy ciąg w drugi.

Wejście

Pierwsza linia wejścia zawiera liczbę zestawów danych $z$ ($1 \le z \le 100$). Następnie następują opisy zestawów danych.

Pierwsza linia każdego zestawu danych zawiera trzy liczby całkowite $n, m, k$ ($1 \le n, m \le 1\,000\,000$, $0 \le k \le 1000$) – długości ciągów oraz parametr z opisu problemu.

Druga linia zawiera ciąg o długości $n$ składający się z małych liter alfabetu angielskiego – ciąg $s$ z opisu problemu.

Trzecia linia zawiera ciąg o długości $m$ składający się z małych liter alfabetu angielskiego – ciąg $t$ z opisu problemu.

Suma długości wszystkich ciągów we wszystkich zestawach danych nie przekroczy $10^7$.

Wyjście

Dla każdego zestawu danych, jeśli odległość edycyjna jest większa niż $k$, wypisz w pojedynczej linii słowo „NO”. W przeciwnym razie, w pierwszej linii wypisz słowo „YES”, a w kolejnych liniach opisz odpowiedź w następujący sposób:

W drugiej linii wypisz minimalną liczbę $r$ operacji wymaganych do przekształcenia $s$ w $t$. W kolejnych $r$ liniach wypisz operacje, po jednej w linii:

• Aby wstawić małą literę alfabetu angielskiego $c$ do ciągu o rozmiarze $w$ na pozycji $p$ ($1 \le p \le w + 1$), wypisz INSERT p c.
• Aby usunąć znak z ciągu o rozmiarze $w$ z pozycji $p$ ($1 \le p \le w$), wypisz DELETE p.
• Aby zamienić znak w ciągu o rozmiarze $w$ na pozycji $p$ ($1 \le p \le w$) na małą literę alfabetu angielskiego $c$, wypisz REPLACE p c.

Przykład

Wejście 1

2
3 4 3
kot
plot
5 7 3
zycie
porazka

Wyjście 1

YES
2
REPLACE 1 l
INSERT 1 p
NO