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

Суффиксное дерево

Суффиксное дерево

Лимит времени 2 секунды
Лимит использования памяти 256 MiB

Постройте суффиксное дерево для заданной строки s.

Входные данные

Первая строка входного файла содержит строку s (1|s|100000). Строка состоит из строчных латинских букв.

Выходные данные

В первой строке выходного файла выведите два натуральных числа n и m, разделённых пробелом - число вершин и рёбер в суффиксном дереве соответственно. В следующих m строках выведите описания рёбер в формате <родитель> <потомок> <l> <r>. Эта запись означает, что на ребре написана строка s[l..r], при этом значение l должно быть минимально возможным. Корнем дерева должна быть вершина с номером 1. Вершины должны быть занумерованы натуральными числами, не превышающими n,

Пример

Входные данные #1
ababb
Выходные данные #1
7 6
1 4 1 2
1 6 2 2
4 2 3 5
4 5 5 5
6 3 3 5
6 7 5 5