Задано рядок \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|}). \textbf{Примітка} \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}.