Suffix tree

Construct a suffix tree for the given string (s).

Input

The first line of the input contains the string (s) ((1 $\le$ |s| $\le$ 100000)). The string is composed of lowercase Latin letters.

Output

On the first line of the output, print two natural numbers (n) and (m), separated by a space, representing the number of vertices and edges in the suffix tree, respectively. In the following (m) lines, provide the descriptions of the edges in the format: <ancestor> <descendant> <l> <r>. This indicates that the edge is labeled with the substring (s[l..r]), where (l) is the smallest possible value. The root of the tree should be the vertex numbered (1). Vertices should be numbered using natural numbers not exceeding (n).

Examples