Pernahkah kamu mendengar soal jarak edit? Diberikan dua string yang terdiri atas huruf kecil bahasa Inggris, kamu harus menentukan jumlah minimum operasi yang diperlukan untuk mengubah string pertama menjadi string kedua. Satu operasi dapat berupa:

• menyisipkan sebuah karakter ke dalam urutan, di posisi mana pun;

• menghapus karakter mana pun dari urutan;

• mengganti sebuah karakter dengan karakter lain.

Semua orang di universitas kami sangat menyukai soal ini, mungkin sedikit terlalu menyukainya, sehingga kami memutuskan untuk membuat soal yang lebih mudah! Kamu diberi dua string $s=s_1\ldots s_n$, $t=t_1\ldots t_m$ dan sebuah bilangan bulat $k$. Tentukan apakah jarak edit antara kedua string tidak lebih dari $k$. Jika ya, kamu juga diminta memberikan urutan operasi mana pun dengan jumlah operasi minimum yang mengubah string pertama menjadi string kedua.

Masukan

Baris pertama masukan berisi banyaknya kasus uji $z$ ($1\le z\le 100$). Deskripsi kasus-kasus uji menyusul.

Baris pertama setiap kasus uji berisi tiga bilangan bulat $n,m,k$ ($1\le n,m\le 1\,000\,000$, $0\le k\le 1000$), yaitu panjang kedua string dan parameter dari deskripsi soal.

Baris kedua berisi string sepanjang $n$ yang terdiri atas huruf kecil bahasa Inggris, yaitu string $s$ dari deskripsi soal.

Baris ketiga berisi string sepanjang $m$ yang terdiri atas huruf kecil bahasa Inggris, yaitu string $t$ dari deskripsi soal.

Jumlah panjang semua string dalam semua kasus uji tidak melebihi $10^7$.

Keluaran

Untuk setiap kasus uji, jika jarak edit lebih besar dari $k$, cetak satu baris berisi kata NO. Jika tidak, baris pertama harus berisi kata YES, dan baris-baris berikutnya mendeskripsikan jawaban sebagai berikut:

Pada baris kedua, cetak jumlah minimum $r$ operasi yang diperlukan untuk mengubah $s$ menjadi $t$. Pada $r$ baris berikutnya, cetak operasi-operasi tersebut, satu per baris.

• Untuk menyisipkan huruf kecil bahasa Inggris $c$ ke dalam urutan berukuran $w$ pada posisi $p$ ($1\le p\le w+1$), cetak INSERT p c.

• Untuk menghapus karakter pada posisi $p$ dari urutan berukuran $w$ ($1\le p\le w$), cetak DELETE p.

• Untuk mengganti karakter pada posisi $p$ dalam urutan berukuran $w$ ($1\le p\le w$) dengan huruf kecil bahasa Inggris $c$, cetak REPLACE p c.

Contoh

Masukan 1

2
3 4 3
kot
plot
5 7 3
zycie
porazka

Keluaran 1

YES
2
REPLACE 1 l
INSERT 1 p
NO