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