האם שמעתם פעם על בעיית מרחק העריכה? בהינתן שתי מחרוזות של אותיות אנגליות קטנות, עליכם לקבוע את מספר הפעולות המינימלי הנדרש כדי להפוך את הראשונה לשנייה. פעולה יחידה יכולה להיות אחת מאלה:

• הכנסת תו לסדרה, בכל מקום שהוא,
• מחיקת תו כלשהו מהסדרה,
• החלפת תו בתו אחר.

כולם באוניברסיטה שלנו אוהבים מאוד את הבעיה הזו — אולי קצת יותר מדי — ולכן החלטנו ליצור בעיה קלה יותר! נתונות לכם שתי מחרוזות $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.
• כדי למחוק תו ממקום $p$ בסדרה בגודל $w$ ($1 \le p \le w$), הדפיסו DELETE p.
• כדי להחליף תו במקום $p$ בסדרה בגודל $w$ ($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