編集距離の問題を聞いたことはありますか？小文字の英字からなる2つの文字列が与えられたとき、最初の文字列を2番目の文字列に変換するために必要な最小の操作回数を求める必要があります。1回の操作は以下のいずれかです。

• シーケンスの任意の場所に文字を挿入する
• シーケンスから任意の文字を削除する
• ある文字を別の文字に置換する

私たちの大学では皆この問題が大好きで、少し熱中しすぎているかもしれません。そこで、より簡単な問題を作成することにしました！2つの文字列 $s = s_1 \dots s_n$、$t = t_1 \dots t_m$ と整数 $k$ が与えられます。これら2つの文字列間の編集距離が $k$ 以下であるかどうかを判定してください。もしそうであれば、最初の文字列を2番目の文字列に変換するための最小回数の操作手順も出力してください。

入力

入力の最初の行には、テストケースの数 $z$ ($1 \le z \le 100$) が含まれます。続いて各テストケースの説明が続きます。

各テストケースの最初の行には、3つの整数 $n, m, k$ ($1 \le n, m \le 1\,000\,000, 0 \le k \le 1000$) が含まれます。これらは文字列の長さと、問題文で説明されたパラメータです。

2行目には、問題文で説明された文字列 $s$ である、長さ $n$ の小文字の英字からなる文字列が含まれます。

3行目には、問題文で説明された文字列 $t$ である、長さ $m$ の小文字の英字からなる文字列が含まれます。

すべてのテストケースにおける文字列の長さの合計は $10^7$ を超えません。

出力

各テストケースについて、編集距離が $k$ より大きい場合は、"NO" という単語を含む1行を出力してください。そうでない場合は、最初の行に "YES" という単語を含め、続く行で以下のように回答を記述してください。

2行目には、$s$ を $t$ に変換するために必要な最小の操作回数 $r$ を出力してください。続く $r$ 行には、操作を1行につき1つずつ出力してください。

• サイズ $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