Редагування відстані ще раз#11099
Чи чули ви про задачу обчислення відстані редагування? Для двох рядків, що складаються з англійських літер, потрібно визначити мінімальну кількість операцій, необхідних для перетворення першого рядка в другий. Операції можуть бути такими:
вставка символу в будь-яке місце послідовності,
видалення будь-якого символу з послідовності,
заміна одного символу іншим.
У нашому університеті всі дуже захоплюються цією задачею, можливо, навіть занадто, тому ми вирішили створити простішу задачу! Вам дано два рядки s = s_1, \ldots, s_n, t = t_1, \ldots, t_m і ціле число . Необхідно визначити, чи є відстань редагування між рядками меншою або рівною . Якщо це так, вас також просять вказати будь-яку послідовність мінімально можливої кількості операцій для перетворення першого рядка в другий.
Перша строка містить кількість тестів (1 \leq z \leq 100). Далі йдуть описи тестів.
Перша строка кожного тесту містить три цілі числа , , (1 \leq n, m \leq 10^6, 0 \leq k \leq 1000) — довжини рядків і параметр з опису задачі.
У другій строчці знаходиться рядок довжини , що складається з малих латинських літер - рядок з опису задачі.
У третій строчці знаходиться рядок довжини , що складається з малих латинських літер - рядок з опису задачі.
Сумарна довжина всіх рядків у всіх тестах не перевищує 10^7.
Для кожного тесту, якщо відстань редагування перевищує , виведіть один рядок, що містить слово "NO". В іншому випадку перший рядок повинен містити слово "YES", а наступні рядки повинні описувати відповідь наступним чином:
У другій строчці виведіть мінімальну кількість операцій, необхідних для перетворення в . У наступних рядках виведіть операції, по одній в рядку.
Щоб вставити символ в послідовність розміром у позицію (1 \leq p \leq w + 1), виведіть INSERT p c.
Щоб видалити символ з послідовності розміром у позиції (1 \leq p \leq w), виведіть DELETE p.
Щоб замінити символ у послідовності розміром у позиції символом , виведіть REPLACE p c.
Приклад 1