Suffix tree of two strings

Input

The first line contains the string $s$ ( $1 \leq ∣ s ∣ \leq 1 0^{4}$ 1 \le |s| \le 10^4), ending with the character "$". All other characters are lowercase Latin letters. The second line contains the string $t$ ( $1 \leq ∣ t ∣ \leq 1 0^{4}$ 1 \le |t| \le 10^4), ending with the character "#". All other characters are lowercase Latin letters.

Output

Number the vertices of the tree from $0$ to $n - 1$ n-1 using a depth-first search, ordering subtrees based on the lexicographical order of the outgoing edges from each vertex. Use the ASCII values of characters to determine this order.

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

The description for a vertex $v$ includes four integers: $p$ , $w$ , $l f$ , $r g$ . Here, $p$ ( $0 \leq p < n$ 0 \le p < n, $p \neq = v$ p \ne v) is the parent vertex number, $w$ ( $0 \leq w \leq 1$ 0 \le w \le 1) indicates which string determines the substring on the edge. If $w = 0$ w = 0, the edge from $p$ to $v$ contains the substring $s [l f \dots r g - 1]$ s[lf \ldots rg-1] ( $0 \leq l f < r g \leq ∣ s ∣$ 0 \le lf < rg \le |s|). If $w = 1$ w = 1, the edge contains the substring $t [l f \dots r g - 1]$ t[lf \ldots rg-1] ( $0 \leq l f < r g \leq ∣ t ∣$ 0 \le lf < rg \le |t|).

Examples

Example 1

Loading