Суфіксне дерево двох рядків
Задано рядки s та t. Побудуйте стиснене суфіксне дерево, яке містить усі суфікси рядка s та рядка t.
Знайдіть таке дерево, яке містить мінімальну кількість вершин.
Вхідні дані
У першої рядку записано рядок s (1 ≤ |s| ≤ 10^5), останнім символом рядка є "$", інші символи рядка маленькі латинські літери.
У другому рядку записано рядок t (1 ≤ |t| ≤ 10^5), останнім символом рядка є "#", інші символи рядка маленькі латинські літери.
Вихідні дані
Пронумеруйте вершини дерева від 0 до n-1 у порядку обходу у глибину, обходячи піддерева у порядку лексикографічного сортування виходячих з вершини ребер. Використовуйте ASCII-коди символів для визначення їх порядку.
У першому рядку виведіть ціле число n — кількість вершин дерева. У наступних n-1 рядках виведіть описи вершин дерева, крім кореня, у порядку збільшення їх номерів.
Опис вершини дерева v складається з чотирьох цілих чисел: p, w, lf, rg, де p (0 ≤ p < n, p ≠ v) — номер предка поточної вершини, w (0 ≤ w ≤ 1) — номер рядка для визначення підрядка на ребрі. Якщ w = 0, то на ребрі, що веде з p у v, написано підрядок s[lf...rg-1] (0 ≤ lf < rg ≤ |s|). Якщо w = 1, то на ребрі, що веде з p у v, написано підрядок t[lf...rg-1] (0 ≤ lf < rg ≤ |t|).
Примітка
Підрядком s[l...r] (0 ≤ l ≤ r < |s|) рядка s = s_0s_1...s_{|s|-1} (де |s| — довжина рядка s) називається рядок s_ls_{l+1}...s_r.