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

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

Входные данные

Первая строка входного файла содержит строку s (1 ≤ |s| ≤ 100000). Строка состоит из строчных латинских букв.

Выходные данные

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

Примеры