Problems
Текстовый редактор
Текстовый редактор
Всемирно известная кампания разработала новый, упрощённый вариант своего популярного текстового редактора. В распоряжении пользователя есть всего \textbf{4} возможные операции, которые можно выполнять в текстовом редакторе (каждая операция выполняется одним нажатием на соотвествующую клавишу):
\begin{enumerate}
\item Напечатать в редакторе символ "\textbf{А}" - клавиша "\textbf{А}" (символ прибавлятся в конец текущей строки)
\item Выделить всю строку - клавиша "\textbf{S}" (select)
\item Скопировать все выделенные символы в буфер - клавиша "\textbf{C}" (copy)
\item Добавить содержимое буфера в конец текущей строки - клавиша "\textbf{P}" (paste), при этом вставка затирает выделенную строку.
\end{enumerate}
Определить максимальное количество символов "\textbf{А}", которые можно напечатать в редакторе за \textbf{N} нажатий и указать последовательность операций, приводящих к этому результату.
\InputFile
Входными данными к задаче является целое число \textbf{N} (\textbf{0} < \textbf{N} < \textbf{50}).
\OutputFile
В стандартный поток вывода в первой строке вывести целое число - максимальное количество символов "\textbf{А}", которые можно напечатать в редакторе за \textbf{N} нажатий, а во вторую строку - последовательность операций, которые приводят к этому результату. Если такая последовательность не одна, то вывести ту, которая минимизирует количество символов в буфере обмена.
\textit{\textbf{Примечание}}: Три рази нажимаем клавишу "\textbf{А}" - получаем строку \textbf{AAA}. Нажимаем клавишу "\textbf{S}" - выделяем все символы, нажимаем клавишу "\textbf{С}" - копируем их в буфер, нажимаем клавишу "\textbf{Р}" - вставляем вместо выделенной строки содержимое буфера, ещё два раза нажимаем клавишу "\textbf{Р}" - прибавляем содержимое буфера к текущей строке. Всего сделали \textbf{8} нажатий и получили строку из \textbf{9} символов "\textbf{А}".
Input example #1
1
Output example #1
1 A