Given string \textbf{S}. Create determinstic nite-state automaton, that accepts all suxes of \textbf{S} (and probably other nite strings). Automaton must consist of minimal number of states. Each state of the automtaton is nal. Starting state has number \textbf{1}. Image below shows automaton from test sample for string "\textbf{abacaba}". \includegraphics{https://static.e-olymp.com/content/87/87be8ea7c4398240c259821a077a1d1245f2eb37.jpg} \InputFile The only line contains string \textbf{S}, consisting of lowercase latin letters. \OutputFile In the fr rst line, two numbers \textbf{N} and \textbf{K} --- are amount of states and transitions. t's followed by \textbf{K} lines, each having two numbers \textbf{a_i}, \textbf{b_i} and letter \textbf{c_i}, meaning transtion from state \textbf{a_i} to \textbf{b_i} by letter \textbf{c_i}. You can output transitions in any order. If there are multiple solutions, output any of them. \textbf{Limits} \textbf{1} ≤ \textbf{|S|} ≤ \textbf{5000} \textbf{1} ≤ \textbf{a_i}, \textbf{b_i} ≤ \textbf{N} '\textbf{a}' ≤ \textbf{c_i} ≤ '\textbf{z}'