Problem description

Jasio bierze udział w specyficznym teleturnieju. Na początku rozgrywki, na wielkim ekranie wyświetlane zostają dwa słowa wzorzec P długości N i tekst T długości M.

Następnie odbywa się Q rund teleturnieju. W każdej z nich prowadzący zmienia jedną literkę wzorca, po czym wykrzykuje pytanie Ile wystąpień wzorca znajduje się teraz w tekście? Zasady teleturnieju są takie, że wzorzec występuje w tekście na pozycji K, wtedy i tylko wtedy, gdy wzorzec P jest równy słowu złożonemu z liter T_K, T_K + 1, …, T_{K + N − 1}.

Jeśli Jasio odpowie poprawnie na wszystkie pytania, czeka go wysoka nagroda pieniężna. Chłopiec postanowił, że w ramach przygotowań do występu w teleturnieju, napisze program, który będzie potrafił bezbłędnie odpowiadać na pytania prowadzącego. Niestety - Jasiu nie jest jeszcze zbyt doświadczonym programistą i nie może sobie poradzić z zadaniem. Pomóż mu!

Wejście

W pierwszym wierszu wejścia znajdują się trzy liczby naturalne N, M, Q, oddzielone pojedynczymi odstępami i oznaczające odpowiednio: długość wzorca, długość tekstu oraz liczbę rund teleturnieju.

W drugim wierszu wejścia znajduje się treść wzorca: N małych liter alfabetu angielskiego, bez żadnych odstępów. W trzecim wierszu wejścia znajduje się treść tekstu: M małych liter alfabetu angielskiego, bez żadnych odstępów.

W następnych Q wierszach znajdują się opisy poszczególnych zmian wzorca. W (i+3)-cim wierszu znajdują się dwie wartości, oddzielone pojedynczym odstępem: liczba naturalna K_i, oraz mała litera alfabetu angielskiego C_i. Oznaczają one, że w i-tej rundzie prowadzący zamienia i-tą literę wzorca na literę C_i.

Litery we wzorcu są numerowane kolejnymi liczbami naturalnymi zaczynając od 1. Prowadzący może także (dla zmylenia Jasia) zamienić literę wzorca na taką samą.

Wyjście

Twój program powinien wypisać dokładnie Q wierszy. W i-tym wierszu powinna się znaleźć liczba wystąpień wzorca po i-tym pytaniu prowadzącego.

Ograniczenia

2 ≤ N ≤ M ≤ 250 000, 1 ≤ K_i ≤ N.

Przykład

2 5 4
aa
aabaa
1 b
2 b
1 a
2 a

1
0
1
2