Текстовий редактор
Всесвітньо відома компанія розробила новий, спрощений варіант свого популярного текстового редактора. У розпорядженні користувача є всього 4 можливі операції, які можна робити в текстовому редакторі (кожна операція виконується одним натисканням на відповідну клавішу):
Надрукувати в редакторі символ "А" - клавіша "А" (символ додається в кінець поточного рядка)
Виділити весь рядок - клавіша "S" (select)
Скопіювати всі виділені символи в буфер - клавіша "C" (copy)
Додати вміст буфера в кінець поточного рядка - клавіша "P" (paste), при цьому вставка затирає виділений рядок.
Визначити максимальну кількість символів "А", які можна надрукувати в редакторі за N натискань і вказати послідовність операцій, яка призводить до цього результату.
Вхідні дані
Вхідними даними для задачі є ціле число N (0 < N < 50).
Вихідні дані
У стандартний потік виводу в перший рядок вивести ціле число - максимальну кількість символів "А", які можна надрукувати в редакторі за N натискань, а у другий рядок - послідовність операцій, яка призводить до цього результату. Якщо така послідовність не одна, то привести ту, яка мінімізує кількість символів у буфері обміну.
Примітка: Три рази натискаємо клавішу "А" - отримуємо рядок AAA. Натискаємо клавішу "S" - виділяємо всі символи, натискаємо клавішу "С" - копіюємо їх в буфер, натискаємо клавішу "Р" - вставляємо замість виділеного рядка зміст буфера, ще два рази натискаємо клавішу "Р" - додаємо зміст буфера до поточного рядка. Разом зробили 8 натискань і отримали рядок з 9 символів "А".