Суфіксне дерево

Побудуйте суфіксне дерево для заданого рядка s.

Вхідні дані

Перший рядок вхідного файлу містить рядок s (1 ≤ |s| ≤ 100000). Рядок складається з маленьких латинських букв.

Вихідні дані

У першому рядку вихідного файлу виведіть два натуральних числа n та m, відокремлених пропуском - число вершин та ребер у суфіксному дереві відповідно. У наступних m рядках виведіть описи ребер у форматі <предок> <потомок> <l> <r>. Цей запис означає, що на ребрі записано рядок s[l..r], при цьому значення l повинно бути мінімально можливим. Коренем дерева повинна бути вершина з номером 1. Вершини повинні бути пронумеровані натуральними числами, які не перевищують n,

Приклади