Bạn cần in \(N\) từ bằng một chiếc máy in chữ rời. Đây là loại máy in cổ, trong đó người dùng xếp các miếng kim loại nhỏ, mỗi miếng mang một chữ cái, để tạo thành từ. Sau đó, một tờ giấy được ép lên các miếng kim loại để in từ đó. Chiếc máy của bạn cho phép thực hiện ba thao tác:

• Thêm một chữ cái vào cuối từ hiện đang có trong máy.
• Xóa chữ cái cuối cùng của từ hiện đang có trong máy. Chỉ được thực hiện thao tác này khi trong máy có ít nhất một chữ cái.
• In từ hiện đang có trong máy.

Ban đầu máy trống, không chứa miếng kim loại mang chữ cái nào. Khi in xong, bạn được phép để lại một số chữ cái trong máy. Bạn cũng có thể in các từ theo thứ tự tùy ý.

Mỗi thao tác đều tốn thời gian, nên bạn muốn thực hiện ít thao tác nhất có thể. Hãy tìm số thao tác ít nhất để in tất cả \(N\) từ đã cho, đồng thời đưa ra một dãy thao tác đạt được số lượng đó.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa số nguyên \(N\), là số từ cần in.
• Mỗi dòng trong \(N\) dòng tiếp theo chứa một từ. Mỗi từ chỉ gồm các chữ cái tiếng Anh viết thường từ a đến z và có độ dài từ \(1\) đến \(20\), kể cả hai đầu mút. Các từ đôi một khác nhau.

Dữ liệu ra

Ghi ra đầu ra chuẩn:

• Dòng đầu tiên chứa số nguyên \(M\), là số thao tác ít nhất cần thực hiện để in \(N\) từ.
• Mỗi dòng trong \(M\) dòng tiếp theo chứa đúng một ký tự mô tả một thao tác, theo thứ tự thực hiện:
  • Thêm một chữ cái: ghi chính chữ cái đó ở dạng viết thường.
  • Xóa chữ cái cuối cùng: ghi ký tự - (dấu trừ, mã ASCII \(45\)).
  • In từ hiện tại: ghi ký tự P (chữ P viết hoa).

Ràng buộc

• \(1 \le N \le 25\,000\).
• Độ dài mỗi từ nằm trong đoạn \([1,20]\).
• Các từ đôi một khác nhau và chỉ chứa chữ cái tiếng Anh viết thường.

Chấm điểm trên hệ thống

Lưu ý: Cách chia nhóm và tính điểm dưới đây là bản điều chỉnh để luyện tập trên hệ thống, không khẳng định tương đương cách chấm tại IOI gốc.

Mỗi nhóm được chấm độc lập: chỉ nhận điểm của nhóm khi vượt qua tất cả bộ kiểm thử trong nhóm; nếu có bộ kiểm thử không đạt thì nhóm nhận 0 điểm. Tổng điểm tối đa là 100.

Nhãn nhóm là phần số trong tên tệp dữ liệu gốc. Tất cả tệp cùng nhãn, kể cả các hậu tố chữ và pf, đều thuộc nhóm đó.

Các ví dụ trong đề không tính điểm. Các tệp ví dụ gốc có nhãn 0 được giữ lại riêng và có trọng số 0.

Tệp ví dụ gốc: typ/typ0.in.

Ví dụ

3
print
the
poem

20
t
h
e
P
-
-
-
p
o
e
m
P
-
-
-
r
i
n
t
P

Nguồn

IOI 2008.