Суфіксне дерево двох рядків

Вхідні дані

У першому рядку задано рядок $\text{s}$ (1 \leq |\textbf{s}| \leq 10^5), де останній символ — "$\text{\$}$", а всі інші — малі латинські літери.

У другому рядку задано рядок $\text{t}$ (1 \leq |\textbf{t}| \leq 10^5), де останній символ — "\textbf{#}", а всі інші — малі латинські літери.

Вихідні дані

Пронумеруйте вершини дерева від $0$ до n - 1 у порядку обходу в глибину, обходячи піддерева у лексикографічному порядку відносно символів на вихідних ребрах з кожної вершини. Для визначення порядку використовуйте ASCII-коди символів.

У першому рядку виведіть одне ціле число $n$ — кількість вершин у дереві. У наступних n - 1 рядках виведіть опис кожної вершини (крім кореня) у зростаючому порядку їх номерів.

Опис вершини складається з чотирьох цілих чисел: $p$, $w$, $lf$, $rg$, де $p$ (0 \leq p < n, p \neq v) — номер батьківської вершини для поточної вершини $v$, $w$ (0 \leq w \leq 1) — індекс рядка для ідентифікації підрядка на ребрі. Якщо w = 0, то на ребрі від $p$ до $v$ розташовано підрядок \textbf{s}[lf \ldots rg - 1] (0 \leq lf < rg \leq |\textbf{s}|), а якщо w = 1, то — підрядок \textbf{t}[lf \ldots rg - 1] (0 \leq lf < rg \leq |\textbf{t}|).

Приклади

Примітка

Підрядком \textbf{s}[l \ldots r] (0 \leq l \leq r < |\textbf{s}|) називається рядок \textbf{s}_l \textbf{s}_{l+1} \ldots \textbf{s}_r, де \textbf{s} = s_0 s_1 \ldots s_{|\textbf{s}| - 1} і $|\text{s}|$ — довжина рядка $\text{s}$.