Дана строка \textbf{s}. Построить детерминированный конечный автомат, принимающий все суффиксы строки \textbf{s }(и возможно другие конечные строки). Автомат должен состоять из минимального числа состояний - \textbf{n }и не более чем \textbf{2n }переходов. Каждое состояние автомата объявляется финальным. Начальное состояние имеет номер \textbf{1}. На изображении ниже показан автомат из тестового примера для строки "\textbf{abacaba}". \includegraphics{https://static.e-olymp.com/content/ad/ad266ea3cdf4b1f28aec982569d4aa6f2b059b6f.jpg} \InputFile В единственной строке слово \textbf{s} (\textbf{1} ≤ |\textbf{s|} ≤ \textbf{10^5}), состоящее из строчных латинских букв. \OutputFile В первой строке два числа \textbf{n }и \textbf{k }(\textbf{1} ≤ \textbf{k} ≤ \textbf{2n}) - количество состояний и количество переходов. Далее \textbf{k }строк, в каждой из которых по два числа \textbf{a_i}, \textbf{b_i} (\textbf{1} ≤ \textbf{a_i}, \textbf{b_i} ≤ \textbf{n}) и буква \textbf{c_i} ('\textbf{a}' ≤ \textbf{c_i} ≤ '\textbf{z}'), означающие наличие перехода из состояния \textbf{a_i} в \textbf{b_i} по букве \textbf{c_i}. Переходы можно выводить в любом порядке. Если решений несколько, можете вывести любое из них.