Архіватор#5238
Вася вирішив підкорити ринок кращих архіваторів світу. Зовсім нещодавно він придумав дуже нетривіальну ідею для стиснення тексту з маленьких латинських букв. А саме, він вирішив, що можна зберігати текст як послідовність команд. Команди бувають двох типів:
c: дописати до поточного рядка символ c.
i k: дописати до поточного рядка символів один за одним. При цьому перший символ, що дописується, співпадає з символом поточного рядка, другий — з символом i + 1 і так далі, -ий символ, що дописується, співпадає з символом i + k - 1. Гарантується, що не перевищує поточну довжину рядка.
Наприклад, послідовність команд a, b, 1 3 кодує рядок ababa, а послідовність команд a, 1 3, b, 3 3 кодує рядок aaaabaab.
На збереження команди першого типу Васі потрібно байт, а другого типу — байт. На жаль, поки що Вася вміє лише за командами відновити вихідний рядок, а навпаки не вміє. Вам пропонується допомогти бідному Васі у підкоренні архіваторного ринку.
Знайдіть послідовність команд, яка архівує заданий рядок вказаним способом, при цьому витративши якомога менше байтів на його зберігання.
У вхідному файлі задано рядок з рядкових латинських букв довжиною не більше символів.
У першому рядку вихідного файлу ви повинні вивести кількість байтів, які знадобиться для зберігання послідовності команд, та кількість команд у послідовності. У наступних рядках виведіть саму послідовність, по одній команді у рядку. Якщо команда першого типу, то виведіть просто букву, інакше виведіть два числа: позицію символу (символи нумеруються починаючи з одиниці) у рядку , починаючи з якого потрібно почати копіювання, та кількість символів, які потрібно скопіювати.
Приклад 1