Редактирование расстояния еще раз
Вы когда-нибудь слышали о проблеме расстояния редактирования? По двум строкам из английских букв необходимо найти минимальное количество операций, необходимых для преобразования первой строки во вторую. Одной операцией может быть:
вставка символа в последовательность в любом месте,
удаление любого символа из последовательности,
замена одного символа другим.
Все в нашем университете очень любят эту задачу, может быть, даже слишком, поэтому мы решили создать задачу попроще! Вам даны две строки s = s[1]...s[n], t = t[1]...t[m] и целое число k. Определите, меньше или равно k расстояние редактирования между строками. Если это так, вас также просят указать любую последовательность минимально возможного количества операций для преобразования первой строки во вторую.
Входные данные
Первая строка содержит количество тестов z (1 ≤ z ≤ 100). Далее следуют описания тестов.
Первая строка каждого теста содержит три целых числа n, m, k (1 ≤ n, m ≤ 10^6 , 0 ≤ k ≤ 1000) — длины строк и параметр из описания задачи.
Во второй строке находится строка длины n, состоящая из строчных латинских букв - строка s из описания задачи.
В третьей строке находится строка длины m, состоящая из строчных латинских букв - строка t из описания задачи.
Суммарная длина всех строк во всех тестах не превышает 10^7.
Выходные данные
Для каждого теста, если расстояние редактирования больше k, выведите одну строку, содержащую слово "NO". В противном случае первая строка должна содержать слово "YES", а следующие строки должны описывать ответ следующим образом:
Во второй строке выведите минимальное количество r операций, необходимых для преобразования s в t. В следующих r строках выведите операции, по одной в строке.
Чтобы вставить символ c в последовательность размером w в позицию p (1 ≤ p ≤ w + 1), выведите INSERT p c.
Чтобы удалить символ из последовательности размера w в позиции p (1 ≤ p ≤ w), выведите DELETE p .
Чтобы заменить символ в последовательности размером w в позиции p (1 ≤ p ≤ w) символом c, выведите REPLACE p c.