Məsələlər
Архиватор
Архиватор
Вася решил покорить рынок лучших архиваторов мира. Совсем недавно он придумал очень нетривиальную идею для сжатия текста из маленьких латинских букв. А именно, он решил, что можно хранить текст как последовательность команд. Команды бывают двух типов:
\begin{itemize}
\item \textbf{c}: дописать к текущей строке символ \textbf{c}.
\item \textbf{i k}: дописать к текущей строке \textbf{k} символов один за другим. При этом первый дописываемый символ совпадает с символом \textbf{i} текущей строки, второй с символом \textbf{i+1} и так далее, \textbf{k}-ый добавляемый символ совпадает с символом \textbf{i+k-1}. Гарантируется, что \textbf{i} не превосходит текущей длины строки.
\end{itemize}
Например последовательность команд \textbf{a, b, 1 3} кодирует строку \textbf{ababa}, а последовательность команд \textbf{a, 1 3, b, 3 3 }кодирует строку \textbf{aaaabaab}.
На хранение команды первого типа Васе требуется \textbf{1} байт, а второго типа \textbf{5} байт. К сожалению, пока Вася умеет только по командам восстановить исходную строку, а наоборот не умеет. Вам предлагается помочь бедному Васе в покорении архиваторного рынка.
Найдите последовательность команд, которая архивирует заданную строку указанным способом, при этом потратив как можно меньше байт на ее хранение.
\InputFile
Во входном файле вам задана строка \textbf{s} из строчных латинских букв длиной не более \textbf{4000} символов.
\OutputFile
В первой строке выходного файла вы должны вывести количество байт, которое потребуется для хранения последовательности команд и количество команд в последовательности. На следующих строках выведите саму последовательность, по одной команде на строке. Если команда первого типа, то выведите просто букву, иначе выведите два числа: позиция символа (символы нумеруются начиная с единицы) в строке \textbf{s}, начиная с которого надо начать копирование, и количество символов, которое надо скопировать.
Giriş verilənləri #1
abcdqwertyqwertyu
Çıxış verilənləri #1
16 12 a b c d q w e r t y 5 6 u