E. Шүүхийн шалгалт

хугацааны хязгаарлалт 6 секунд

санах ойн хязгаарлалт 768 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Реберланд улс бол Берландын заналт дайсан. Саяхан Берландын эрх мэдэлтнүүд Реберландын тагнуулыг барьсан. Тагнуул Берландад хууль бус байдаг ухуулга сурталчилгааны хуудаснууд барьсан байжээ. Ихэнх хуудас дээр Маргаангүй Зөвшөөршгүй Хараалын үгний дэд тэмдэгт мөрүүд байсан ба заримд нь үг бүхлээрээ байсан ч байж магадгүй.

Берландын хууль зүйн систем тагнуулын гэм буруутайг тогтоох төвөгтэй алгоритм хэрэглэдэг.

Тагнуулын авч явж байсан бүх $m$ хуудас $1$-с $n$ хүртэл дугаарлагдсан. Үүний дараа дараах төрлийн $q$ асуулгад хариулт олох хэрэгтэй болсон: "$[l, r]$ тооны сегментэд байгаа аль хуудсанд нь Маргаангүй Зөвшөөршгүй Хараалын үгийн дэд тэмдэгт мөр $[p_{l}, p_{r}]$ илүү олон тохиолдож байна вэ?".

Мэргэжилтэн таныг энэ үйл ажиллагааг автоматжуулахыг хүсч байна учир нь энэ удаагийн хуудаснууд дээрх текстүүд маш урт байна. Түүнд туслана уу!

Оролт

Эхний мөрөнд тэмдэгт мөр $s$ ($1 ≤ |s| ≤ 5*10^{5}$) байх буюу Маргаангүй Зөвшөөршгүй Хараалын үг байна. $s$ тэмдэгт мөр нь зөвхөн Англи цагаан толгойн жижиг үсгүүдээс бүрдэнэ.

Хоёр дахь мөрөнд бүхэл тоон утга $m$ ($1 ≤ m ≤ 5*10^{4}$) байх ба шинжих текстүүд байна.

Дараагийн $m$ мөр бүрт тэмдэгт мөр $t_{i}$ байх ба $i$-р хуудасны текст юм. Бүх хуудасны текстүүдийн нийт урт $5*10^{4}$-с ихгүй байна. Хуудаснууд дээрх текстүүд зөвхөн Англи цагаан толгойн жижиг үсгүүдээс бүрдэнэ.

Дараагийн мөрөнд бүхэл тоон утга $q$ ($1 ≤ q ≤ 5*10^{5}$) байх ба шинжилгээний асуулгуудын тоо юм.

Эцэст нь сүүлийн $q$ мөр бүрт дөрвөн бүхэл тоон утга $l$, $r$, $p_{l}$, $p_{r}$ ($1 ≤ l ≤ r ≤ m, 1 ≤ p_{l} ≤ p_{r} ≤ |s|$) байх ба энд $|s|$ нь Маргаангүй Зөвшөөршгүй Хараалын үгний урт юм.

Гаралт

$q$ мөр хэвлэнэ. $i$-р мөрөнд хоёр бүхэл тоон утга байх ёстой ба эдгээр нь $s$ тэмдэгт мөрийн $[p_{l}, p_{r}]$ дэд тэмдэгт мөрийг хамгийн олон агуулсан үгний тоо ба хамгийн олон агуулсан тохиолдлын тоо байна. Хэрвээ хэд хэдэн текстийн тоо байвал хамгийн багыг нь хэвлэнэ.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
suffixtree
3
suffixtreesareawesome
cartesiantreeisworsethansegmenttree
nyeeheeheee
2
1 2 1 10
1 3 9 10
Гаралт
1 1
3 4
Сэтгэгдлүүдийг ачааллаж байна...