Automaton

For a given string S, create determinstic nite-state automaton, that accepts all suxes of S (and probably other nite strings). Automaton must consist of minimal number of states — N and no more than 2N transitions.

Image below shows automaton from test sample for string "abacaba".

Input

The only line contains string S, consisting of lowercase latin letters.

Output

In the rst line print two numbers N and K — are amount of states and transitions, followed by K lines, each having two numbers a_i, b_i and letter c_i, meaning transtion from state a_i to b_i by letter c_i. You can output transitions in any order. If there are multiple solutions, output any of them.

Limits

1 ≤ |S| ≤ 10^5

1 ≤ K ≤ 2N

1 ≤ a_i, b_i ≤ N

'a' ≤ c_i ≤ 'z'

Examples