Bal

Limit pamięci: 32MB

W uznaniu dotychczas wykonanych prac Bajtokles został zaproszony na Bajtolimp, gdzie odbywa się wielki bal wyprawiany na jego cześć. Na Bajtolimpie panuje zwyczaj, iż każdy gość przy wejściu otrzymuje numer(panie nieparzysty, panowie parzysty, przy czym mogą one się powtarzać), mniejszy niż liczba wszystkich gości K – zawsze parzysta, aby każdy miał partnera do rozmowy. Numer nie jest bez znaczenia – znajduje szerokie zastosowanie podczas zabaw. Bajtokles nigdy nie widział jeszcze takiego bogactwa wystroju i potraw. Z tego też powodu bardzo się pilnuje, aby nie popełnić żadnej gafy (a takowa mogłaby się naprawdę źle skończyć!). Gdy zaczęły się tańce (pieczołowicie praktykowane na każdym balu), Bajtokles gorąco zapragnął, aby wszyscy zatańczyli taniec z jego rodzinnych stron. W tańcu tym trzeba uważnie słuchać prowadzącego. Schemat tańca jest następujący: Na początku wszyscy tańczą samotnie. Prowadzący krzyczy dwie liczby: x - mniejszą od liczby gości i liczbę pierwszą p, większą od 2. Wtedy osoby o numerach x oraz K - x - 1 zaczynają tańczyć w damsko-męskich parach. Kobiety albo mężczyźni którym nie udało się znaleźć partnera/ki, zmieniają swój numer mnożąc go razy p. Jeśli nowy numer będzie równy lub większy od K, bierze się jego resztę z dzielenia przez K.

Bajtokles już wcześniej przygotował zestaw liczb, którymi ma się zamiar posłużyć w czasie tańca. Martwi się jednak, czy na końcu zbyt dużo osób nie będzie tańczyć samotnie – mogłoby to popsuć atmosferę balu. Rozwiej jego wątpliwości, podpowiadając mu jak wiele osób zostanie bez pary.

Wejscie

W pierwszej linii wejścia znajdują się dwie liczby całkowite K,  M (1 <= K, M <= 10^6, 2|K) – liczba gości oraz liczba okrzyków Bajtoklesa podczas tańca. W następnej linii znajduje się K liczb całkowitych a_i  (0 <= a_i  < K) , i-ta liczba w tej linii oznacza numer i-tej osoby. W kolejnych M liniach znajdują się po dwie liczby. W i+2 linii znajdują się liczby x oraz p (0 <= x < K, 3 <= p < 1000) charakteryzujące i-ty okrzyk w czasie tańca.

Wyjście

W jedynej linii wyjścia wypisz liczbę osób tańczących samotnie po zakończeniu zabawy.

Przykład

Wejście:
6 3
1 2 0 0 2 3
3 5
4 7
0 3

Wyjście:
2
Wyjaśnienie: po pierwszym zawołaniu będą próbowały dobrać się w pary osoby o numerach 2 i 3. Utworzy się jedna para, a druga osoba zmieni swój numer na 4. Następnie sparują się osoby o numerach 1 i 4. Na końcu zostaną tylko uczestnicy z numerem 0.