你听说过编辑距离问题吗？给定两个由小写英文字母组成的字符串，你需要确定将第一个字符串转换为第二个字符串所需的最少操作次数。单次操作可以是以下三种之一：

• 在序列的任意位置插入一个字符；
• 删除序列中的任意字符；
• 将一个字符替换为另一个字符。

我们大学里的每个人都非常喜欢这个问题——甚至可能有点过度了——所以我们决定出一个更简单的问题！给定两个字符串 $s = s_1 \dots s_n$，$t = t_1 \dots 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”，接下来的行应按如下方式描述答案：

第二行输出将 $s$ 转换为 $t$ 所需的最少操作次数 $r$。在接下来的 $r$ 行中，每行输出一个操作。

• 若要在大小为 $w$ 的序列中，在位置 $p$ ($1 \le p \le w + 1$) 处插入一个小写英文字母 $c$，请输出 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