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 TK, TK + 1, …, TK + 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 Ki, oraz mała litera alfabetu angielskiego Ci. Oznaczają one, że w i-tej rundzie prowadzący zamienia i-tą literę wzorca na literę Ci.
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 ≤ Ki ≤ N.
Przykład
| Input | Output | |
|
|