Дана строка \textbf{s}. Постройте сжатое суффиксное дерево для строки \textbf{s} и выведите его. Найдите такое дерево, которое содержит минимальное количество вершин. \InputFile В первой строке записана строка \textbf{s} (\textbf{1} ≤ \textbf{|s|} ≤ \textbf{10^5}), последний символ строки доллар "\textbf{\$}", остальные символы строки маленькие латинские буквы. \OutputFile Пронумеруйте вершины дерева от \textbf{0} до \textbf{n-1} в порядке обхода в глубину, обходя поддеревья в порядке лексикографической сортировки исходящих из вершины ребер. Используйте ASCII-коды символов для определения их порядка. В первой строке выведите целое число \textbf{n} --- количество вершин дерева. В следующих \textbf{n-1} строках выведите описание вершин дерева, кроме корня, в порядке увеличения их номеров. Описание вершины дерева \textbf{v} состоит из трех целых чисел: \textbf{p}, \textbf{lf}, \textbf{rg}, где \textbf{p} (\textbf{0} ≤ \textbf{p} < \textbf{n}, \textbf{p} ≠ \textbf{v}) --- номер родителя текущей вершины. На ребре, ведущем из \textbf{p} в \textbf{v}, написана подстрока \textbf{s\[lf...rg-1\]} (\textbf{0} ≤ \textbf{lf} < \textbf{rg} ≤ \textbf{|s|}). \Note \textit{Подстрокой} \textbf{s\[l...r\]} (\textbf{0} ≤ \textbf{l} ≤ \textbf{r} < \textbf{|s|}) строки \textbf{s = s_0s_1...s_\{|s|-1\}} (где \textbf{|s|} --- длина строки \textbf{s}) называется строка \textbf{s_ls_\{l+1\}...s_r}.