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

Очень сложная

Ограничение по времени выполнения 1 секунда

Ограничение по использованию памяти 256 мегабайт

Дана строка s. Постройте сжатое суффиксное дерево для строки s и выведите его.

Найдите такое дерево, которое содержит минимальное количество вершин.

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

В первой строке записана строка s (1 ≤ |s| ≤ 10^5), последний символ строки доллар "$", остальные символы строки маленькие латинские буквы.

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

Пронумеруйте вершины дерева от 0 до n-1 в порядке обхода в глубину, обходя поддеревья в порядке лексикографической сортировки исходящих из вершины ребер. Используйте ASCII-коды символов для определения их порядка.

В первой строке выведите целое число n — количество вершин дерева. В следующих n-1 строках выведите описание вершин дерева, кроме корня, в порядке увеличения их номеров.

Описание вершины дерева v состоит из трех целых чисел: p, lf, rg, где p (0 ≤ p < n, p ≠ v) — номер родителя текущей вершины. На ребре, ведущем из p в v, написана подстрока s[lf...rg-1] (0 ≤ lf < rg ≤ |s|).

Примеры

Ввод #1

Ответ #1

Ввод #2

Ответ #2

Ввод #3

Ответ #3

Примечание

Подстрокой s[l...r] (0 ≤ l ≤ r < |s|) строки s = s_0s_1...s_{|s|-1} (где |s| — длина строки s) называется строка s_ls_{l+1}...s_r.

Отправки 707