Задано рядок \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}'