Архиватор
Вася решил покорить рынок лучших архиваторов мира. Совсем недавно он придумал очень нетривиальную идею для сжатия текста из маленьких латинских букв. А именно, он решил, что можно хранить текст как последовательность команд. Команды бывают двух типов:
c: дописать к текущей строке символ c.
i k: дописать к текущей строке k символов один за другим. При этом первый дописываемый символ совпадает с символом i текущей строки, второй с символом i+1 и так далее, k-ый добавляемый символ совпадает с символом i+k-1. Гарантируется, что i не превосходит текущей длины строки.
Например последовательность команд a, b, 1 3 кодирует строку ababa, а последовательность команд a, 1 3, b, 3 3 кодирует строку aaaabaab.
На хранение команды первого типа Васе требуется 1 байт, а второго типа 5 байт. К сожалению, пока Вася умеет только по командам восстановить исходную строку, а наоборот не умеет. Вам предлагается помочь бедному Васе в покорении архиваторного рынка.
Найдите последовательность команд, которая архивирует заданную строку указанным способом, при этом потратив как можно меньше байт на ее хранение.
Входные данные
Во входном файле вам задана строка s из строчных латинских букв длиной не более 4000 символов.
Выходные данные
В первой строке выходного файла вы должны вывести количество байт, которое потребуется для хранения последовательности команд и количество команд в последовательности. На следующих строках выведите саму последовательность, по одной команде на строке. Если команда первого типа, то выведите просто букву, иначе выведите два числа: позиция символа (символы нумеруются начиная с единицы) в строке s, начиная с которого надо начать копирование, и количество символов, которое надо скопировать.