Вася решил покорить рынок лучших архиваторов мира. Совсем недавно он придумал очень нетривиальную идею для сжатия текста из маленьких латинских букв. А именно, он решил, что можно хранить текст как последовательность команд. Команды бывают двух типов: \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}, начиная с которого надо начать копирование, и количество символов, которое надо скопировать.