Суфіксне дерево
Задано рядок 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|).
Примітка
Підрядком s[l...r] (0 ≤ l ≤ r < |s|) рядка s = s_0s_1...s_{|s|-1} (де |s| — довжина рядка s) називається рядок s_ls_{l+1}...s_r.