6. Čarovný lexikón kúziel

David si z knižnice požičal lexikón kúziel. V lexikóne kúziel sa ukrýva jeho obľúbené zaklínadlo. Chcel nájsť, koľkokrát sa tam nachádza. Lenže! Čarodejnica pred ním zo srandy lexikón zakliala, takže sa po každom prečítaní text trochu zmení. David bol tvrdohlavý a po každej zmene lexikónu znova zisťoval, koľkokrát je tam zaklínadlo. Toto robil, až kým mu neuplynula výpožičná lehota a keďže nechcel platiť pokutu, musel lexikón vrátiť.

Úloha

Máme reťazec a podreťazec, v reťazci hľadáme počet výskytov podreťazca. Reťazec sa mení. Po každej zmene chceme znova zistiť počet výskytov podreťazca.

Formát vstupu

V prvom riadku je reťazec dlhý \(n\) (\(1 \leq n \leq 10^6\)). V druhom riadku je podreťazec dlhý \(m\) (\(1 \leq m \leq 10^4\)). Možeš predpokladať, že \(m \leq n\). V treťom riadku je číslo \(q\) (\(0 \leq q \leq 10^3\)). Nasleduje \(q\) riadkov vo formáte [\(p\)] [\(S\)], \(p\) označuje miesto v texte, kam zapísať podreťazec \(S\) (\(0 \leq p \leq n-m\)). Dĺžka podreťazca \(S\) je rovná \(m\), to znamená, že dĺžka reťazca sa celý čas nemení.

Formát výstupu

Na výstupe je \(1+q\) riadkov, jeden pre pôvodný text a jeden pre každú zmenu v reťazci. Na každom riadku je jedno číslo, počet výskytov podreťazca v reťazci.

V niektorých pomalších jazykoch (python) nemusí správne riešenia prechádzať na plný počet bodov. Body za popis táto skutočnosť neovplyvní. ## Príklady

Input:

BANANANOS
NANA
2
5 ANAS
3 XXXX

Output:

1
2
0

V pôvodnom reťazci sa podreťazec “NANA” vyskytuje raz. Potom sa reťazec zmení na “BANANANAS”, preto sa tam podreťazec vyskytuje dvakrát. Potom sa zmení na “BANXXXXAS”, kde už sa podreťazec nevyskytuje.

Input:

AAAAAAAAAAAAAAA
AAA
2
1 XXX
6 XXX

Output:

13
9
4

Input:

BALALAJKA
ALA
2
5 ALA
1 BLA

Output:

2
3
2

Input:

BLBALABLA
BL
2
1 LB
2 AL

Output:

2
2
2

Input:

BABANANASSSSSS
NANA
1
1 XXXX

Output:

1
0