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