Edit Distance Yet Again

Have you ever heard of the edit distance problem? Given two strings of lowercase English letters, you must determine the minimum number of operations needed to transform the first one into the second one. A single operation can be one of the following:

• inserting a character into the sequence at any position,
• deleting any character from the sequence,
• substituting a character with another one.

Everyone at our university loves this problem, maybe a little too much, so we decided to create an easier one! You are given two strings $s = s_1 \ldots s_n$ and $t = t_1 \ldots t_m$, and an integer $k$. Find out whether the edit distance between the strings is at most $k$. If so, you must also output any sequence of the minimum possible number of operations that transforms the first string into the second one.

The first line contains the number of test cases $z$ ($1 \leq z \leq 100$). The descriptions of the test cases follow.

The first line of each test case contains three integers $n, m, k$ ($1 \leq n, m \leq 1\,000\,000$, $0 \leq k \leq 1000$), the lengths of the strings and the parameter from the problem. The second line contains a string of length $n$ consisting of lowercase English letters, the string $s$. The third line contains a string of length $m$ consisting of lowercase English letters, the string $t$.

The total length of all strings in all test cases does not exceed $10^7$.

For each test case, if the edit distance is greater than $k$, print a single line containing NO. Otherwise, print YES on the first line. On the second line, print the minimum number $r$ of operations needed to transform $s$ into $t$. Then print the $r$ operations, one per line.

• To insert a lowercase English letter $c$ into a sequence of size $w$ at position $p$ ($1 \leq p \leq w + 1$), print INSERT p c.
• To delete the character at position $p$ of a sequence of size $w$ ($1 \leq p \leq w$), print DELETE p.
• To substitute the character at position $p$ of a sequence of size $w$ ($1 \leq p \leq w$) with a lowercase English letter $c$, print REPLACE p c.