Problem description

Jasiu, jak każdy mały chłopiec, bardzo lubi obserwować kolorowe neony. Niedawno na pobliskim budynku zamontowano niezwykły rodzaj neonu – taki, który potrafi zmieniać wyświetlane literki.

Mama Jasia postanowiła nauczyć go czytać. Zaczęła od tego, że nauczyła go rozpoznawać słowo W. Słowo W jest szczególne – wszystkie literki są w nim różne (dzięki temu Jasiu od razu nauczył się wielu literek).

Jasiu zaczął wieczorami przesiadywać przy oknie i patrzeć na zmieniające się znaki na neonie. Ponieważ niekoniecznie rozumie wyświetlane napisy, zadaje sobie nieco inne pytanie – ile razy słowo W występuje w aktualnie wyświetlanym napisie?

Jasiu mieszka w odległym kraju i mówi w egzotycznym języku. W tym języku może być o wiele więcej liter niż w alfabecie łacińskim, dlatego dla uproszczenia, w tym zadaniu, ponumerowaliśmy te litery i traktujemy je jako liczby.

Wejście

W pierwszym wierszu wejścia znajdują się liczba naturalna N oznaczająca długość słowa W. W kolejnym wierszu znajduje się N liczb naturalnych W_i poodzielanych pojedynczymi odstępami – oznaczają one numery kolejnych znaków w słowie W. W trzecim wierszu wejścia znajduje się liczba naturalna M oznaczająca długość neonu. W kolejnym wierszu znajduje się M liczb naturalnych V_i oznaczających numery kolejnych znaków neonu w chwili 0. W piątym wierszu wejścia znajduje się liczba naturalna Q oznaczająca długość okresu obserwowania neonu przez Jasia. W kolejnych Q wierszach znajdują się po dwie liczby naturalne oddzielone pojedynczym odstępem A_i oraz B_i. Liczby A_i, B_i oznaczają, że znak na pozycji A_i na neonie został zamieniony na znak o numerze B_i.

Wyjście

Na wyjściu powinno się znaleźć Q wierszy zawierającyh po jednej liczbie całkowitej, i-ta z nich powinna być równa liczbie wystąpień słowa W w napisie na neonie po dokonaniu i-tej zmiany.

Ograniczenia

1 ≤ N, M, Q ≤ 100 000, 1 ≤ W_i, V_i, A_i, B_i ≤ 10⁹.

Przykład

3
1 2 3
6
1 2 3 3 2 3
2
4 1
1 2

2
1