Pseudo automaton

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. Each state of the automtaton is nal. Starting state has number 1.

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 fr rst line, two numbers N and K — are amount of states and transitions. t's 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| ≤ 5000

1 ≤ a_i, b_i ≤ N

'a' ≤ c_i ≤ 'z'

Examples