Чи чули ви коли-небудь про задачу на відстань редагування? За двома рядками з малих англійських літер потрібно визначити мінімальну кількість операцій, необхідних для перетворення першого рядка на другий. Одна операція може бути такою:
- Вставити символ у будь-якому місці послідовності.
- Видалити будь-який символ із послідовності.
- Замінити символ іншим.
Усі в нашому університеті дуже люблять цю задачу — можливо, навіть занадто, — тому ми вирішили створити простішу! Вам задано два рядки $s=s_1\ldots s_n$, $t=t_1\ldots 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