eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Архіватор

Архіватор

Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB

Вася вирішив покорити ринок кращих архіваторів світу. Зовсім нещодавно він придумав дуже нетривіальну ідею для стиснення тексту з маленьких латинських букв. А саме, він вирішив, що можна зберігати текст як послідовність команд. Команди бувають двох типів:

  • 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, починаючи з якого потрібно почати копіювання, та кількість символів, які потрібно скопіювати.

Приклад

Вхідні дані #1
abcdqwertyqwertyu
Вихідні дані #1
16 12
a
b
c
d
q
w
e
r
t
y
5 6
u
Автор Олег Ігнатьєв
Джерело Тринадцатая международная командная олимпиада школьников ЛКШ среди параллелей A, A' и B