هل سمعت من قبل بمسألة مسافة التحرير؟ عند إعطاء سلسلتين من الأحرف الإنجليزية الصغيرة، يجب تحديد أقل عدد من العمليات اللازمة لتحويل الأولى إلى الثانية. يمكن أن تكون العملية الواحدة أحد ما يلي:

• إدراج محرف في المتتالية في أي موضع.
• حذف أي محرف من المتتالية.
• استبدال محرف بمحرف آخر.

يحب الجميع في جامعتنا هذه المسألة كثيرًا، وربما أكثر قليلًا مما ينبغي، ولذلك قررنا إعداد مسألة أسهل! تُعطى سلسلتان $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، وتصف الأسطر التالية الإجابة كما يلي:

اطبع في السطر الثاني أقل عدد $r$ من العمليات اللازمة لتحويل $s$ إلى $t$. وفي الأسطر $r$ التالية، اطبع العمليات، عملية واحدة في كل سطر.

• لإدراج محرف إنجليزي صغير $c$ في متتالية طولها $w$ عند الموضع $p$، حيث $1 \le p \le w+1$، اطبع INSERT p c.
• لحذف محرف من متتالية طولها $w$ من الموضع $p$، حيث $1 \le p \le w$، اطبع DELETE p.
• لاستبدال المحرف في الموضع $p$ من متتالية طولها $w$ بمحرف إنجليزي صغير $c$، حيث $1 \le p \le w$، اطبع 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