คุณเคยได้ยินโจทย์ระยะห่างการแก้ไขหรือไม่? กำหนดสตริงตัวอักษรภาษาอังกฤษตัวพิมพ์เล็กสองสตริงมาให้ คุณต้องหาจำนวนการดำเนินการน้อยที่สุดที่ใช้เปลี่ยนสตริงแรกให้เป็นสตริงที่สอง การดำเนินการหนึ่งครั้งเป็นอย่างใดอย่างหนึ่งต่อไปนี้:
- แทรกอักขระหนึ่งตัวลงในลำดับที่ตำแหน่งใดก็ได้
- ลบอักขระใดก็ได้หนึ่งตัวออกจากลำดับ
- แทนที่อักขระหนึ่งตัวด้วยอีกตัวหนึ่ง
ทุกคนในมหาวิทยาลัยของเราชอบโจทย์นี้มาก — อาจมากเกินไปเล็กน้อย — เราจึงตัดสินใจสร้างโจทย์ที่ง่ายกว่า! กำหนดสตริงสองสตริง $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$ ($1 \le p \le w$) ออกจากลำดับขนาด $w$ ให้พิมพ์
DELETE p - หากต้องการแทนที่อักขระที่ตำแหน่ง $p$ ($1 \le p \le w$) ในลำดับขนาด $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