Suffix tree

Input

The input consists of a single line containing the string $s$ (1 \leq |s| \leq 10^5). The string ends with a dollar sign "$\$$", and all other characters are lowercase Latin letters.

Output

Number the vertices of the tree from $0$ to n-1 using a depth-first search order, traversing subtrees based on the lexicographical order of the outgoing edges from each vertex. The order is determined by the ASCII values of the characters.

First, output an integer $n$ — the total number of vertices in the tree. Then, for the next n-1 lines, provide the description of each tree vertex, excluding the root, in ascending order of their numbers.

Each vertex $v$ is described by three integers: $p$, $lf$, $rg$. Here, $p$ (0 \leq p < n, p \neq v) is the number of the parent vertex of $v$. The edge from $p$ to $v$ is labeled with the substring s[lf \ldots rg-1] (0 \leq lf < rg \leq |s|).

Examples

Note

A substring s[l \ldots r] (0 \leq l \leq r < |s|) of the string s = s_0s_1 \ldots s_{|s|-1} (where $|s|$ is the length of the string $s$) is the sequence s_ls_{l+1} \ldots s_r.