你聽過編輯距離（edit distance）問題嗎？給定兩個由小寫英文字母組成的字串，你必須決定將第一個字串轉換為第二個字串所需的最少操作次數。單次操作可以是以下其中之一：

• 在序列中的任意位置插入一個字元。
• 刪除序列中的任意字元。
• 將一個字元替換為另一個字元。

我們大學裡的每個人都非常喜歡這個問題——或許喜歡得有點過頭了——所以我們決定出一個更簡單的問題！給定兩個字串 $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