题目描述

编辑部正在校对两份只由小写英文字母组成的手稿。第一份手稿内容为字符串 s，第二份目标手稿内容为字符串 t。

校对员可以对当前手稿执行以下三种修改之一：

• 在任意位置插入一个小写英文字母；
• 删除当前手稿中的一个字符；
• 将当前手稿中的一个字符替换成另一个小写英文字母。

给定一个整数 k。你需要判断，是否能在不超过 k 次修改内把 s 变成 t。如果可以，还需要给出一组修改次数最少的具体修改方案。

输入格式

第一行包含一个整数 z，表示测试用例数量。

每个测试用例包含三行：

第一行包含三个整数 n, m, k，分别表示字符串 s 的长度、字符串 t 的长度和参数 k。

第二行包含一个长度为 n 的字符串 s。

第三行包含一个长度为 m 的字符串 t。

输出格式

对每个测试用例分别输出答案。

如果 s 到 t 的编辑距离大于 k，输出一行：

NO

否则先输出一行：

YES

下一行输出一个整数 r，表示把 s 变成 t 所需的最少修改次数。接下来输出 r 行，每行描述一个修改操作。操作必须按照实际执行顺序给出，并作用在当前字符串上。

可用操作格式如下：

• INSERT p c：在当前长度为 w 的字符串中，将字符 c 插入到位置 p，其中 1 <= p <= w + 1；
• DELETE p：删除当前字符串第 p 个字符，其中 1 <= p <= w；
• REPLACE p c：将当前字符串第 p 个字符替换为字符 c，其中 1 <= p <= w。

数据范围

• 1 <= z <= 100
• 1 <= n, m <= 1000000
• 0 <= k <= 1000
• 所有测试用例中，所有字符串长度之和不超过 10000000

样例

2
3 4 3
kot
plot
5 7 3
zycie
porazka

YES
2
REPLACE 1 l
INSERT 1 p
NO