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

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

1 секунда
256 мегабайт
Very hard

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

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

Input

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

Output

Пронумеруйте вершины дерева от 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|).

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Note

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