F. ТорКодер

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

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

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

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

Лео нэртэй хүү ТорКодер-ын тэмцээн бүрийг алдалгүй оролцдог. Сүүлийн ТорКодер-ын 100666 дугаартай тэмцээн дээр Лео дараах бодлого дээр бүдэрчээ. Түүнд $n$ ширхэг Англи жижиг үсгүүдээс тогтох $s$ тэмдэгт мөр болон $m$ ширхэг асуултууд өгөгдөнө. Асуулт болгон нь хос бүхэл тоо $l_{i}, r_{i}$ $(1 ≤ l_{i} ≤ r_{i} ≤ n)$ -аар өгөгдөнө.

Бид уг тэмдэгт мөр дэх үсгүүд нь зүүнээсээ баруун уруу 1-ээс $n$ хүртэл дугаарлагдсан байна гэж үзэх ба өөрөөр хэлбэл $s = s_{1}s_{2}... s_{n}$ байх юм. Асуулт болгоны дараа тэрээр $s$ тэмдэгт мөрийн $l_{i}$-ээс $r_{i}$ хүртэлх индексүүдтэй (уг дугаарууд нь мөн орно) үсгүүдийг заавал солих ба ингэснээр $(l_{i}, r_{i})$ дэд тэмдэгт мөр нь палиндром байх ёстой. Хэрэв ийм олон тооны солилт байвал та $(l_{i}, r_{i})$ тэмдэгт мөр нь хэл зүйн хувьд хамгийн бага солилтыг хийх юм. Хэрэв ийм солилт оршин байхгүй бол та уг асуултыг орхино. Өөрөөр хэлбэл $s$ тэмдэгт мөр нь өөрчлөгдөхгүй.

Хүн болгон ТорКодер-ын тэмцээн болгоны оролтын мөр болон цувааны хэмжээ нь $60$-аас хэтэрдэггүй гэдгийг мэдэх ба иймд Лео уг бодлогыг амархан бодов. Таны даалгавар бол уг бодлогыг арай их хязгаартай үед бодох юм. Танд $s$ тэмдэгт мөр болон $m$ ширхэг асуултууд өгөгдөх ба $s$ тэмдэгт мөрд бүх $m$ асуултуудыг гүйцэтгэсний дараах үр дүнгийн тэмдэгт мөрийг хэвлэх юм.

Оролт

Эхний мөрөнд тэмдэгт мөрийн урт болох асуултуудын тоо болох 2 бүхэл тоо $n$ болон $m$ $(1 ≤ n, m ≤ 10^{5})$ өгөгдөнө.

2-дахь мөрөнд $n$ ширхэг Англи жижиг үсгүүдээс тогтох $s$ тэмдэгт мөр өгөгдөнө.

Дараагийн $m$ мөрийн мөр болгонд уг тэмдэгтэд гүйцэтгэх асуултуудыг илэрхийлэх хос бүхэл тоо $l_{i}, r_{i}$ ($1 ≤ l_{i} ≤ r_{i} ≤ n$) өгөгдөнө.

Гаралт

Дан мөрөнд $s$ тэмдэгт мөрд бүх $m$ асуултуудыг гүйцэтгэсний дараах үр дүнгийн тэмдэгт мөрийг хэвлэнэ үү. Асуултуудыг оролтод өгөгдсөн дарааллаар нь хэвлэнэ үү.

Орчуулсан: Баатархүү

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

Оролт
7 2
aabcbaa
1 3
5 7
Гаралт
abacaba
Оролт
3 2
abc
1 2
2 3
Гаралт
abc

Тэмдэглэл

$n$ урт бүхий $s = s_{1}s_{2}... s_{n}$ тэмдэгт мөрийн дэд тэмдэгт мөр $(l_{i}, r_{i})$ $1 ≤ l_{i} ≤ r_{i} ≤ n)$ нь $s_{l_{i}}s_{l_{i + 1}}...s_{r_{i}}$ тэмдэгтүүдийн дараалал байна.

Хэрэв тэмдэгт мөр нь зүүнээс баруун уруу болон баруунаас зүүн уруугаа ижил уншигдаж байвал уг тэмдэгт мөрийг палиндром гэнэ.

Хэрэв $p < q$ бөгөөд $x_{1} = y_{1}, x_{2} = y_{2}, ... , x_{p} = y_{p}$ байх тохиолдолд эсвэл $x_{1} = y_{1}, x_{2} = y_{2}, ... , x_{r} = y_{r}$ болон $x_{r + 1} < y_{r + 1}$ байх $r$ $(r < p, r < q)$ тоо оршин байх тохиолдолд $x_{1}x_{2}... x_{p}$ тэмдэгт мөрийг $y_{1}y_{2}... y_{q}$ тэмдэгт мөрөөс хэл зүйн хувьд бага байна гэж үзнэ.

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