Suffix tree

Given a string (s), your task is to construct a compressed suffix tree for this string and output it.

The goal is to create a tree with the minimum number of vertices.

Input

The input consists of a single line containing the string (s) ((1 $\le$ |s| $\le$ 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 $\le$ p < n), (p $\ne$ v)) is the number of the parent vertex of (v). The edge from (p) to (v) is labeled with the substring (s[lf...rg-1]) ((0 $\le$ lf < rg $\le$ |s|)).

Examples

Note

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