Редагування відстані ще раз
Чи чули ви про задачу обчислення відстані редагування? Для двох рядків, що складаються з англійських літер, потрібно визначити мінімальну кількість операцій, необхідних для перетворення першого рядка в другий. Операції можуть бути такими:
вставка символу в будь-яке місце послідовності,
видалення будь-якого символу з послідовності,
заміна одного символу іншим.
У нашому університеті всі дуже захоплюються цією задачею, можливо, навіть занадто, тому ми вирішили створити простішу задачу! Вам дано два рядки 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 символом c, виведіть REPLACE p c.