7. Ye ti zima?

Yeti Ignác nedávno dostal skvelý nápad: oholí si nohy, aby bol krajší. No len čo tak spravil, pochopil, že ten nápad nebol až taký skvelý. Keď sa teraz brodí snehom, je mu zima. Rozhodol sa preto, že si pustí na počítači vaše programy a tým sa zahreje.

Vytrestajte Ignáca za jeho hlúpe nápady, nech si dobre zapamätá, že yeti si nemá holiť nohy. Vyriešte teda čo najefektívnejšie nasledujúcu úlohu, nech sa yeti príliš nezahreje.

Úloha

KSP-krása reťazca je počet spôsobov, ktorými v ňom vieme vyznačiť podpostupnosť ksp – teda niekde vyznačiť písmeno k, niekde napravo od neho písmeno s a napravo od toho zase písmeno p. Napríklad KSP-krása reťazca kokosplesk je 2: buď zoberieme znaky na indexoch 0, 4, 5 alebo znaky na indexoch 2, 4, 5.

Na vstupe dostanete jeden reťazec \(S\) a potom postupne \(q\) otázok o ňom. Každá otázka bude nasledujúceho tvaru: “Aká je KSP-krása podreťazca tvoreného znakmi na indexoch \(a_i\) až \(b_i\)?”

Formát vstupu

V prvom riadku je číslo \(n\): dĺžka reťazca. V druhom riadku je reťazec \(S\) tvorený \(n\) malými písmenami anglickej abecedy. V treťom riadku je číslo \(q\): počet otázok.

Zvyšok vstupu tvorí \(q\) riadkov. Tieto riadky a aj im zodpovedajúce otázky si očíslujeme od 0 po \(q-1\). Správnu odpoveď na otázku \(i\) označíme \(c_i\) a navyše dodefinujeme, že \(c_{(-1)} = 0\).

Riadok popisujúci otázku číslo \(i\) obsahuje dve celé čísla \(x_i\) a \(y_i\), pre ktoré platí \(0\leq x_i, y_i < n\). Hodnoty \(a_i\) a \(b_i\) pre túto otázku sú určené nasledovne: Nech \(p_i = (x_i + c_{i-1}) \bmod n\) a \(q_i = (y_i + c_{i-1}) \bmod n\). Potom \(a_i = \min(p_i,q_i)\) a \(b_i = \max(p_i,q_i)\).

V jednotlivých sadách testov platia pre \(n\) a \(q\) nasledovné obmedzenia zhora:

Formát výstupu

Vypíšte \(q\) riadkov a v nich postupne čísla \(c_0\) až \(c_{q-1}\).

Upozornenie

Pri hodnotení popisov budeme o čosi viac ako inde prihliadať na asymptotickú časovú zložitosť vašich riešení. Špeciálne upozorňujeme na to, že algoritmy asymptoticky horšie od vzorového riešenia nedostanú plný počet bodov za popis (hoci môžu úspešne vyriešiť všetky testy).

Príklad

Input:

16
kkssppkokosplesk
4
6 15
4 14
3 3
15 0

Output:

2
8
0
16

• Otázka 0 sa pýta na podreťazec kokosplesk, ktorého KSP-krása je \(c_0 = 2\).
• Keď vieme, že \(c_0=2\), vypočítame si, že otázka 1 má \(a_1=0\) a \(b_1=6\), pýta sa teda na reťazec kkssppk. Toto KSP-krása je \(c_1 = 8\).
• Otázka 2 sa pýta na nejaký jednoznakový reťazec, toho KSP-krása je určite \(c_2 = 0\).
• No a na záver, otázka 3 sa teda pýta na celý reťazec \(S\).