Програмчлалын олимпиадын бодлогын архив

Та үсэг өрдөг хэвлэх машин дээр N ширхэг үгийг хэвлэх ёстой. Үсэг өрдөг хэвлэх машин гэдэг нь үг үүсгэхийн тулд жижиг тугалган хэсгүүдийг (тус бүр нь нэг үсэг агуулах) нийлүүлж өрдөг хуучин машин юм. Үүний дараа үгийг хэвлэхийн тулд цаасан дээр өрсөн тугалган хэсгүүдээ дарна.
Танд байгаа машин дараах үйлдлүүдийг гүйцэтгэж чадна:
• Машинд өрөгдсөн байгаа үгийн төгсгөлд нэг үсэг нэмэх.
• Машинд өрөгдсөн байгаа үгийн хамгийн сүүлийн үсгийг арилгах. Энэ үйлдлийг машинд дор хаяж нэг үсэг байгаа тохиолдолд хийх боломжтой.
• Машинд өрөгдсөн байгаа үгийг хэвлэх.
Анх машин нь ганц ч тугалган хэсэггүй хоосон байна. Үгийг хэвлэсний дараа машинд зарим үсгийг нь устгахгүй орхиж болно. Мөн үгсийг ямар ч дарааллаар хэвлэж болно.
Үйлдэл бүрд хугацаа зарцуулах тул та үйлдлүүдийн нийт тоог хамгийн цөөн байлгахыг хүсч байгаа.
ДААЛГАВАР
Хэвлэх ёстой N үг өгөгдсөн үед бүх үгсийг дараалал харгалзахгүйгээр хэвлэхэд шаардлагатай үйлдлүүдийн нийт тоо хамгийн багадаа хэд байхыг олж, ийм тооны үйлдлийг гүйцэтгэж болох нэг дарааллыг хэвлэх програмыг бич.
ХЯЗГААРЛАЛТУУД 1 <= N <= 25,000 Таны хэвлэх ёстой үгсийн тоо.

Input

Таны програм стандарт оролтоос дараах өгөгдлийг унших ёстой:
• Нэгдүгээр мөр таны хэвлэх ёстой үгийн тоо болох N бүхэл тоог агуулна.
• Дараагийн N ширхэг мөр тус бүрт нэг үг агуулагдана. Үг бүр нь зөвхөн жижиг үсгүүдээс (‘a’ – ‘z’) тогтох ба 1-ээс багагүй, 20-оос ихгүй урттай байна. Ижил үгс байхгүй.

Output

Таны програм стандарт гаралт руу дараах өгөгдлийг гаргах ёстой:
• Нэгдүгээр мөр нь N үгийг хэвлэхэд шаардлагатай үйлдлүүдийн тооны хамгийн бага утга болох M бүхэл тоог агуулах ёстой.
• Дараагийн M ширхэг мөр тус бүр нэг тэмдэгт агуулах ёстой. Эдгээр тэмдэгтүүд нь хийгдэх үйлдлүүдийн дарааллыг илэрхийлнэ. Үйлдлүүдийг дараах байдлаар илэрхийлнэ:
o Үсэг нэмэх үйлдлийг уг үсгийн жижиг хувилбараар дүрслэнэ
o Сүүлийн үсгийг хасах үйлдлийг ‘-‘ тэмдэгтээр илэрхийлнэ (хасах, ASCII код нь 45).
o Өрөгдсөн байгаа үгийг хэвлэх үйлдлийг ‘P’ тэмдэгтээр илэрхийлнэ (том P үсэг)
Зөвхөн нэг утгатай тестүүдээр шалгаж байгаа болно. Бүрэн тестүүдээр шалгуулъя гэвэл энд дарж ороод бодолтоо илгээнэ үү.

Example

Input:
3
print
the
poem


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