你有冇聽過編輯距離問題？畀出兩個由英文小寫字母組成嘅字串，你要確定將第一個變成第二個最少需要幾多次操作。每次操作可以係以下其中一種：

• 喺序列任何位置插入一個字元；
• 刪除序列入面任何一個字元；
• 將一個字元替換成另一個字元。

我哋大學所有人都好鍾意呢個問題，可能鍾意得有啲過火，所以我哋決定出一道更容易嘅題！畀出兩個字串 $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，之後各行按以下格式描述答案：

第二行輸出將 $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