Problems
Суффиксное дерево
Суффиксное дерево
Постройте суффиксное дерево для заданной строки \textbf{s}.
\InputFile
Первая строка входного файла содержит строку \textbf{s} (\textbf{1} ≤ \textbf{|s|} ≤ \textbf{100000}). Строка состоит из строчных латинских букв.
\OutputFile
В первой строке выходного файла выведите два натуральных числа \textbf{n} и \textbf{m}, разделённых пробелом - число вершин и рёбер в суффиксном дереве соответственно. В следующих \textbf{m} строках выведите описания рёбер в формате <\textbf{родитель}> <\textbf{потомок}> <\textbf{l}> <\textbf{r}>. Эта запись означает, что на ребре написана строка \textbf{s\[l..r\]}, при этом значение \textbf{l} должно быть минимально возможным. Корнем дерева должна быть вершина с номером \textbf{1}. Вершины должны быть занумерованы натуральными числами, не превышающими \textbf{n},
Input example #1
ababb
Output example #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