Задано рядок \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}. Переходи можна виводити у довільному порядку. Якщо розв'язків декілька, можете вивести довільний з них.