คุณต้องพิมพ์คำทั้งหมด N คำด้วยเครื่องพิมพ์แบบโบราณ โดยเครื่องพิมพ์ชนิดนี้ใช้เทคโนโลยีเรียงพิมพ์แบบเก่า ซึ่งต้องวางแผ่นโลหะตัวอักษร (แต่ละแผ่นมีหนึ่งตัวอักษร) หลายตัวเรียงต่อกันเป็นคำ แล้วจึงกดแผ่นโลหะตัวอักษรเหล่านั้นลงบนกระดาษเพื่อเป็นการพิมพ์ เครื่องพิมพ์ชนิดนี้รองรับการดำเนินการที่กำหนดให้สามแบบดังต่อไปนี้

-         เพิ่มตัวอักษรหนึ่งตัวอักษรต่อท้ายคำที่มีอยู่แล้วในเครื่องพิมพ์

-         ลบตัวอักษรตัวสุดท้ายจากคำที่มีอยู่แล้วในเครื่องพิมพ์ คุณสามารถทำอย่างนี้ได้ถ้ามีอย่างน้อยหนึ่งตัวอักษรอยู่ในเครื่องพิมพ์

-         พิมพ์คำที่มีอยู่แล้วในเครื่องพิมพ์

เมื่อเริ่มต้น เครื่องพิมพ์จะไม่มีแผ่นโลหะตัวอักษรใดๆอยู่เลย  และเมื่อจบการพิมพ์ คุณสามารถปล่อยตัวอักษรให้ค้างอยู่ในเครื่องพิมพ์ได้ นอกจากนี้คุณสามารถเลือกพิมพ์คำใดก่อนหรือหลังได้

เนื่องจากทุกการดำเนินการต้องใช้เวลาประมวลผล ดังนั้นคุณต้องการใช้จำนวนการดำเนินการให้น้อยที่สุด

โจทย์

คุณต้องเขียนโปรแกรมเพื่อรับคำทั้งหมด N คำที่คุณต้องพิมพ์ แล้วหาจำนวนการดำเนินการที่น้อยที่สุดที่จะพิมพ์คำได้ทั้งหมด และแสดงผลลัพธ์ในรูปของลำดับของการดำเนินการแบบหนึ่ง ถ้ามีหลายแบบสามารถตอบแบบใดก็ได้

เงื่อนไข

1 ≤ N ≤ 25,000            N  คือจำนวนคำทั้งหมดที่คุณต้องพิมพ์

ข้อมูลนำเข้า

โปรแกรมของคุณต้องอ่านข้อมูลเข้าต่อไปนี้จาก standard input

-         บรรทัดที่ ๑ เป็นจำนวนเต็ม N ซึ่ง N เป็นคำทั้งหมดที่คุณต้องพิมพ์

-     บรรทัดต่อจากนั้น  N บรรทัด โดยแต่ละบรรทัดจะมีคำหนึ่งคำ ซึ่งแต่ละคำประกอบด้วยตัวอักษรตัวพิมพ์เล็ก (‘a’—‘z’) เท่านั้น  และมีความยาวของคำตั้งแต่ 1 ถึง 20 ตัวอักษร  โดยคำทั้งหมดไม่ซ้ำกัน

ข้อมูลส่งออก

โปรแกรมของคุณต้องแสดงผลลัพธ์เป็นข้อมูลต่อไปนี้ออกทาง standard output

-         บรรทัดที่ ๑ เป็นจำนวนเต็ม M ซึ่ง M เป็นจำนวนครั้งของการดำเนินการที่น้อยที่สุดในการพิมพ์คำที่เป็นข้อมูลนำเข้า N คำ

-     ต่อจากนั้น M บรรทัด โดยแต่ละบรรทัดจะแสดงตัวอักขระหนึ่งตัว โดยตัวอักขระเหล่านี้ แทนลำดับของการดำเนินการเพื่อพิมพ์นั่นเอง  ซึ่งแต่ละการดำเนินการสามารถแทนได้ดังนี้

            การเพิ่มตัวอักษรหนึ่งตัว แสดงโดยตัวอักษรที่ต้องการเพิ่มที่เป็นตัวพิมพ์เล็ก

            การลบตัวอักษรตัวสุดท้าย แสดงโดยเครื่องหมาย ‘-‘ (เครื่องหมายลบ, ASCII code 45)

            การพิมพ์คำล่าสุดที่เรียงค้างไว้ในเครื่องพิมพ์ แสดงโดยตัวอักษร ‘P’ (ตัวพิมพ์ใหญ่ P)

การให้คะแนน

มีคะแนนรวมให้ 40 คะแนน สำหรับชุดทดสอบที่ N ไม่เกิน 18

ที่มา: 20th International Olympiad in Informatics; Cairo, Egypt (Day 1)