Вы когда-нибудь слышали о задаче на редакционное расстояние (расстояние Левенштейна)? Даны две строки из строчных латинских букв, необходимо определить минимальное количество операций, необходимых для преобразования первой строки во вторую. Одной операцией может быть:
- вставка символа в последовательность в любое место;
- удаление любого символа из последовательности;
- замена одного символа на другой.
Все в нашем университете очень любят эту задачу — возможно, даже слишком сильно — поэтому мы решили создать задачу попроще! Вам даны две строки $s = s_1 \dots s_n$, $t = t_1 \dots t_m$ и целое число $k$. Выясните, является ли редакционное расстояние между строками меньше или равным $k$. Если это так, вас также просят предоставить любую последовательность операций минимально возможной длины для преобразования первой строки во вторую.
Входные данные
Первая строка входных данных содержит количество тестов $z$ ($1 \le z \le 100$). Далее следуют описания тестов.
Первая строка каждого теста содержит три целых числа $n, m, k$ ($1 \le n, m \le 1\,000\,000$, $0 \le k \le 1000$) — длины строк и параметр из условия задачи.
Вторая строка содержит строку длины $n$, состоящую из строчных латинских букв — строку $s$ из условия задачи.
Третья строка содержит строку длины $m$, состоящую из строчных латинских букв — строку $t$ из условия задачи.
Суммарная длина всех строк во всех тестах не превышает $10^7$.
Выходные данные
Для каждого теста, если редакционное расстояние больше $k$, выведите одну строку, содержащую слово «NO». В противном случае, первая строка должна содержать слово «YES», а следующие строки должны описывать ответ следующим образом:
Во второй строке выведите минимальное количество операций $r$, необходимых для преобразования $s$ в $t$. В следующих $r$ строках выведите операции, по одной в строке:
- Чтобы вставить строчную латинскую букву $c$ в последовательность размера $w$ на позицию $p$ ($1 \le p \le w + 1$), выведите
INSERT p c. - Чтобы удалить символ из последовательности размера $w$ на позиции $p$ ($1 \le p \le w$), выведите
DELETE p. - Чтобы заменить символ в последовательности размера $w$ на позиции $p$ ($1 \le p \le w$) на строчную латинскую букву $c$, выведите
REPLACE p c.
Примеры
Входные данные 1
2 3 4 3 kot plot 5 7 3 zycie porazka
Выходные данные 1
YES 2 REPLACE 1 l INSERT 1 p NO