C. Поликарпийн шилдэг бүтээл

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

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

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

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

Жоане Ровлингийн амжилт болон түүний зөгнөлт Харри Поттер цувралаас урам авсан Поликарп өөрийн шилдэг бүтээлийг бүтээхээр шийдсэн. Тэр өөрийн ирээдүйн хамгийн их борлуулалттай бүтээлдээ $s$ тэмдэгт мөр бүхий нэр сонгосон.

Поликарп номныхоо ерөнхий зохиол дээр ажиллаж байхдаа хэд хэдэн хүндрэлтэй нүүр тулсан ба утга зохиолын Малевич болохоор шийдсэн ба өөрийн "Хар Квадрат"-г бүтээсэн.

Поликарп бүтээлийнхээ бүлгүүдийг $n$ өдрийн дотор бичсэн. Тэр $s$ тэмдэгт мөрийг бичихээс эхлэсэн. Өдөр бүр (дараагийн $n$ өдрийн турш) тэр дараах үйллүүдийг хийсэн: $i$-р өдөр тэр одоо байгаа текстийн $k_{i}$-р дугуй шилжүүлэлтийг текстийн яг баруун талд нь нэмсэн. Энэ нь өдөр бүр түүний бүтээлийн агуулга нь хэмжээгээрээ хоёр дахин ихсэнэ гэсэн үг.

$r$ тэмдэгт мөрийн дугуй шилжүүлэлт гэдэг нь тэмдэгт мөрийн сүүлийн тэмдэгт хамгийн эхний байрлалд ирж байрласан тэмдэгт мөрийг хэлнэ. Жишээлбэл «$masterpiece$» тэмдэгт мөрийн дугуй шилжүүлэлт нь «$emasterpiec$» юм. $r$ тэмдэгт мөрийн $i$-р дугуй шилжүүлэлт нь $r$ тэмдэгт мөрд $i$ удаа дугуй шилжүүлэлт хийгээд гарсан тэмдэгт мөр байна (өөрөөр «$masterpiece$» тэмдэгт мөрийн гуравдугаар дугуй шилжүүлэлт нь «$ecemasterpi$» байна).

$n$ өдрийн залхмаар ажлын дараа Поликарп гүйцэтгэсэн хөдөлмөрийнхөө хүчинд маш урт текст бичсэн. Гэсэн ч түүний бүтээлийн текст маш урт байсан учир бүтээлийн агуулга дээр шинжилгээ хийх нь бараг л боломжгүй байв.

Поликарпд түүний бүтээлийн талаарх $m$ хүсэлтэд хариулахад туслана уу: $j$-р хүсэлтийн хувьд та түүний бүтээлийн $l_{j}$ байрлалаас эхлээд $r_{j}$ (уг байрлалуудыг оролцуулаад) байрлалд дуусах дэд тэмдэгт мөрд $c_{j}$ үсэг хэдэн удаа агуулагдсаныг олох ёстой.

Оролт

Эхний мөрөнд бүтээлийн нэр $s$ тэмдэгт мөр байна. Тэмдэгт мөр $s$ нь зөвхөн латин жижиг үсгүүдээс бүрдэх ба урт нь хамгийн багадаа 1 хамгийн ихдээ 100 байна.

Хоёр дахь мөрөнд хос бүхэл тоо $n$ ба $m$ $(1 ≤ n ≤ 10^{5},  1 ≤ m ≤ 10^{5})$ байх ба харгалзан Поликарпийн ажилласан өдрийн тоо болон хүсэлтүүдийн тоо байна.

Дараагийн мөрөнд $n$ бүхэл тоон утга $k_{i}$ $(0 ≤ k_{i} ≤ 100)$ байх буюу $n$ өдрийн ажлын үед ашиглагдах дугуй шилжүүлгүүд юм.

Дараагийн $m$ мөр бүрт хүсэлтийн тодорхойлолт болох хоёр бүхэл тоо $l_{j}, r_{j}$ болон жижиг латин үсэг $c_{j}$ байна. Үсгийн байрлалууд $1$-с эхлэн дугаарлагдана. Мөн $1 ≤ l_{j} ≤ r_{j} ≤ 10^{18}$ байх ба $l_{j}$ ба $r_{j}$ нь хоёулаа бүтээлийн уртаас хэтрэхгүй.

Гаралт

Гаралтанд $m$ мөр хэвлэх ба энд $j$-р мөрөнд $j$-р хүсэлтийн хариу байна.

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

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

Оролт
masterpiece
1 3
3
1 22 m
9 14 e
8 15 p
Гаралт
2
4
0
Оролт
polycarp
1 2
0
2 15 p
1 16 p
Гаралт
2
4
Сэтгэгдлүүдийг ачааллаж байна...