İki sıra üçün sufiks ağacı

Giriş

Birinci sətirdə $s$ sətiri verilir ( $1 \leq ∣ s ∣ \leq 1 0^{5}$ 1 \leq |\textbf{s}| \leq 10^5), burada sonuncu simvol " $$$ "-dir, qalan bütün simvollar isə kiçik latın hərfləridir.

İkinci sətirdə $t$ sətiri verilir ( $1 \leq ∣ t ∣ \leq 1 0^{5}$ 1 \leq |\textbf{t}| \leq 10^5), burada sonuncu simvol " $\textbf{#}$ "-dır, qalan bütün simvollar isə kiçik latın hərfləridir.

Çıxış

Ağacın zirvələrini $0$ -dan $n - 1$ n-1-ə qədər dərinlik üzrə öncəli (DFS) qaydada, hər bir zirvədən çıxan qolları ASCII kodlarına əsasən leksikqrafik ardıcıllıqla gəzərək nömrələyin.

Birinci sətirdə $n$ — ağacın zirvələrinin sayını çap edin. Növbəti $n - 1$ n-1 sətirin hər birində, nömrələr üzrə artan qaydada (kökdən başqa), hər bir zirvənin təsvirini verin.

Hər bir zirvə təsvirində dörd tam ədəd olur: $p$ , $w$ , $l f$ , $r g$ , burada $p$ ( $0 \leq p < n$ 0 \leq p < n, $p \neq = v$ p \neq v) — cari zirvə $v$ -nin valideynidir, $w$ ( $0 \leq w \leq 1$ 0 \leq w \leq 1) — qollardakı altsətirlərin hansı sətirdən götürüldüyünü göstərən ədəddir. Əgər $w = 0$ w = 0-dırsa, $p$ -dən $v$ -yə gedən qolda $s [l f \dots r g - 1]$ \textbf{s}[lf \ldots rg-1] alt sətri yerləşir ( $0 \leq l f < r g \leq ∣ s ∣$ 0 \leq lf < rg \leq |\textbf{s}|), əgər $w = 1$ w = 1-dirsə, $t [l f \dots r g - 1]$ \textbf{t}[lf \ldots rg-1] alt sətri yerləşir ( $0 \leq l f < r g \leq ∣ t ∣$ 0 \leq lf < rg \leq |\textbf{t}|).

Nümunələr

Nümunə 1

Loading

Nümunə 2

Loading

Qeyd

Alt sətri $s [l \dots r]$ \textbf{s}[l \ldots r] ( $0 \leq l \leq r < ∣ s ∣$ 0 \leq l \leq r < |\textbf{s}|) deyərkən, $s_{l} s_{l + 1} \dots s_{r}$ \textbf{s}_l\textbf{s}_{l+1}\ldots\textbf{s}_r nəzərdə tutulur, burada $s = s_{0} s_{1} \dots s_{∣ s ∣ - 1}$ \textbf{s} = s_0s_1 \ldots s_{|\textbf{s}|-1} və $∣ s ∣$ $s$ -in uzunluğudur.