Suffix tree of two strings

Input

The first line contains the string $\text{s}$ (1 \leq |\textbf{s}| \leq 10^5), where the last character is "$\text{\$}$", and all other characters are lowercase Latin letters.

The second line contains the string $\text{t}$ (1 \leq |\textbf{t}| \leq 10^5), where the last character is "\textbf{#}", and all other characters are lowercase Latin letters.

Output

Number the vertices of the tree from $0$ to n - 1 in depth-first search order, traversing subtrees in lexicographical order of outgoing edges from each vertex. Use ASCII codes to determine the order of characters.

On the first line, output an integer $n$ — the number of vertices in the tree. In the next n - 1 lines, output the description of each vertex (except the root), in increasing order of their numbers.

Each vertex description consists of four integers: $p$, $w$, $lf$, $rg$, where $p$ (0 \leq p < n, p \neq v) is the parent of the current vertex $v$, $w$ (0 \leq w \leq 1) is the index of the string for edge substring identification. If w = 0, the edge from $p$ to $v$ contains substring \textbf{s}[lf \ldots rg - 1] (0 \leq lf < rg \leq |\textbf{s}|), and if w = 1, it contains substring \textbf{t}[lf \ldots rg - 1] (0 \leq lf < rg \leq |\textbf{t}|).

Examples

Note

A substring \textbf{s}[l \ldots r] (0 \leq l \leq r < |\textbf{s}|) means the string \textbf{s}_l \textbf{s}_{l+1} \ldots \textbf{s}_r, where \textbf{s} = s_0 s_1 \ldots s_{|\textbf{s}| - 1} and $|\text{s}|$ is the length of $\text{s}$.