% Источник: Сборы в Харькове, февраль 2013, контест Фефера/Агапова, задача J

\begin{problem}{Суффиксное дерево}
{suftree.in}{suftree.out}
{1 секунда}{256 мегабайт}{}

Дана строка $s$. Постройте сжатое суффиксное дерево для строки $s$ и выведите его.
Найдите такое дерево, которое содержит минимальное количество вершин.

\InputFile

В первой строке записана строка $s$ ($1 \le |s| \le 10^5$),
последний символ строки доллар <<\t{\$}>>, остальные символы строки маленькие латинские буквы.

\OutputFile

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

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

Описание вершины дерева $v$ состоит из трёх целых чисел: $p$, $lf$, $rf$, где $p$ ($0 \le p \le n, p \not= v$) --
номер родителя текущей вершины. На ребер ведущем из $p$ в $v$ написана подстрока $s[lf..rf)$ ($0 \le lf < rf \le |s|$).

\Examples

\begin{example}
\exmp{
aaa\$
}{
7
0 3 4
0 0 1
2 3 4
2 1 2
4 3 4
4 2 4
}%
\exmp{
b\$
}{
3
0 1 2
0 0 2
}%
\exmp{
ababa\$
}{
10
0 5 6
0 0 1
2 5 6
2 1 3
4 5 6
4 3 6
0 1 3
7 5 6
7 3 6
}%
\end{example}

\end{problem}
