H. Палиндромууд дээрх хүсэлт

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

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

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

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

Чамд $|s|$ урттай Англи цагаан толгойн жижиг үсгүүдээс тогтох $s = s_{1}s_{2}... s_{|s|}$ тэмдэгт мөр өгөгдөнө. Мөн $q$ хүсэлт өгөгдөх ба хүсэлт бүр $l_{i}, r_{i}$ $(1 ≤ l_{i} ≤ r_{i} ≤ |s|)$ гэсэн хоёр бүхэл тоогоор тодорхойлогдоно. Хүсэлтийн хариуд $s[l_{i}... r_{i}]$ дэд тэмдэгт мөрийн палиндром дэд тэмдэгт мөрүүдийн тоог олох юм.

$s[l... r] = s_{l}s_{l + 1}... s_{r}$ $(1 ≤ l ≤ r ≤ |s|)$ тэмдэгт мөрийг $s = s_{1}s_{2}... s_{|s|}$ тэмдэгт мөрийн дэд тэмдэгт мөр гэнэ.

$t$ тэмдэгт мөрийг баруунаас зүүн рүү уншихад зүүнээс баруун руу уншсантай адилхан уншигдаж байвал палиндром гэнэ. Өөрөөр хэлбэл $t = t_{1}t_{2}... t_{|t|} = t_{|t|}t_{|t| - 1}... t_{1}$ байвал палиндром гэнэ.

Оролт

Эхний мөрөнд $s$ $(1 ≤ |s| ≤ 5000)$ тэмдэгт мөр өгөгдөнө. Хоёр дахь мөрөнд хүсэлтийн тоо болох $q$ $(1 ≤ q ≤ 10^{6})$ байна. Дараагийн $q$ мөрөнд хүсэлтүүд байна. $i$ дэхь мөрөнд $i$ дэхь хүсэлтийг илэрхийлэх $l_{i}, r_{i}$ $(1 ≤ l_{i} ≤ r_{i} ≤ |s|)$ гэсэн бүхэл тоонууд байна.

Өгөгдсөн тэмдэгт мөр Англи цагаан толгойн жижиг үсгүүдээс тогтоно.

Гаралт

Хүсэлт бүрийн хариу болгож $q$ бүхэл тоо хэвлэ. Хариуг хэвлэхдээ хүсэлтүүдийн өгөгдсөн дарааллаар хэвлэ.

Орчуулсан: Бат-Од

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

Оролт
caaaba
5
1 1
1 4
2 3
4 6
4 5
Гаралт
1
7
3
4
2

Тэмдэглэл

Эхний жишээний дөрөвдэх хүсэлтийг авч үзье. $s[4... 6]$ = «$aba$» байна. Үүний палиндром дэд тэмдэгт мөрүүд нь : «$a$», «$b$», «$a$», «$aba$».

Сэтгэгдлүүдийг ачааллаж байна...