Məsafəni yenidən redaktə etmək
Heç vaxt redaktə məsafəsi problemi haqqında eşitmisiniz? İngilis hərflərindən ibarət iki sətir verilir və birinci sətiri ikinciyə çevirmək üçün lazım olan minimal əməliyyat sayını tapmaq tələb olunur. Bir əməliyyat aşağıdakılardan biri ola bilər:
ardıcıllığa istənilən yerdə simvol əlavə etmək,
ardıcıllıqdan istənilən simvolu silmək,
bir simvolu digəri ilə əvəz etmək.
Universitetimizdə hər kəs bu məsələyə çox maraq göstərir, bəlkə də həddindən artıq, buna görə də biz daha sadə bir məsələ yaratmağa qərar verdik! Sizə iki sətir s = s[1]...s[n], t = t[1]...t[m] və tam ədəd k verilir. Sətirlər arasındakı redaktə məsafəsinin k-dən az və ya bərabər olub-olmadığını müəyyənləşdirin. Əgər belədirsə, sizdən həmçinin birinci sətiri ikinciyə çevirmək üçün minimal mümkün əməliyyatların hər hansı bir ardıcıllığını göstərməyiniz xahiş olunur.
Giriş məlumatları
Birinci sətir testlərin sayı z (1 ≤ z ≤ 100) ehtiva edir. Sonra testlərin təsvirləri gəlir.
Hər testin birinci sətiri üç tam ədəd n, m, k (1 ≤ n, m ≤ 10^6, 0 ≤ k ≤ **1000`) ehtiva edir — sətirlərin uzunluqları və məsələnin təsvirindəki parametr.
İkinci sətirdə məsələnin təsvirindəki s sətiri olan kiçik latın hərflərindən ibarət uzunluğu n olan sətir yerləşir.
Üçüncü sətirdə məsələnin təsvirindəki t sətiri olan kiçik latın hərflərindən ibarət uzunluğu m olan sətir yerləşir.
Bütün testlərdə bütün sətirlərin ümumi uzunluğu 10^7-dən çox deyil.
Çıxış məlumatları
Hər test üçün, əgər redaktə məsafəsi k-dən böyükdürsə, bir sətir çıxarın, "NO" sözünü ehtiva edən. Əks halda, birinci sətir "YES" sözünü ehtiva etməlidir və növbəti sətirlər cavabı aşağıdakı kimi təsvir etməlidir:
İkinci sətirdə s-i t-yə çevirmək üçün lazım olan minimal r əməliyyatını çıxarın. Növbəti r sətirdə əməliyyatları, hər sətirdə bir əməliyyat olmaqla çıxarın.
w ölçüsündə ardıcıllığa p mövqeyində (1 ≤ p ≤ w + 1) c simvolunu əlavə etmək üçün INSERT p c çıxarın.
w ölçüsündə ardıcıllıqdan p mövqeyində (1 ≤ p ≤ w) simvolu silmək üçün DELETE p çıxarın.
w ölçüsündə ardıcıllıqda p mövqeyində (1 ≤ p ≤ w) simvolu c ilə əvəz etmək üçün REPLACE p c çıxarın.