Eksterminacja świstaków

Limit pamięci: 128 MB

Gnębon Bajtopysk postanowił uprzykrzyć życie bajtockim świstakom. Te sympatyczne zwierzątka zamieszkują w norkach, w górnych partiach pasma Bajtogór Wysokich.

Gnębon odnalazł pewien grzbiet górski, wzdłuż którego w jednej linii jest rozmieszczonych świstaczych norek (dla ułatwienia kolejne norki wzdłuż grzbietu, patrząc z zachodu na wschód, numerujemy od 1 do ). Diabelski pomysł Gnębona polega na gnębieniu świstaków muzyką z gatunku rock and roll. Aby go zrealizować, nasz bohater zakupił magnetofonów, w każdym umieścił inny album Bajtelsów i rozmieścił je wszystkie w linii, wzdłuż której są wykopane norki. Wiadomo, że po rozkręceniu głośności w danym magnetofonie na cały regulator, wydobywająca się z niego muzyka nie daje spać świstakom znajdującym się w norkach odległych co najwyżej o metrów od tego magnetofonu.

Zaniepokojone tą sytuacją świstaki poprosiły Cię o sprawdzenie, w których norkach na pewno nie uda im się tej zimy wyspać. Nie wiedziały, że to jeszcze nie koniec złośliwości Gnębona...

Otóż Gnębon postanowił wywołać jeszcze większe zamieszanie i co jakiś czas przestawiać niektóre magnetofony. Świstakom udało się wykraść tajny plan Gnębona i wiedzą dokładnie, że -tego dnia rankiem weźmie on magnetofon położony metrów od norki numer 1 i przestawi go w punkt odległy o metrów od tejże norki. Pomóż świstakom sprawdzić, w ilu norkach nie uda im się zasnąć po każdej takiej zamianie.

Wejście

W pierwszym wierszu wejścia znajdują się cztery liczby całkowite , , oraz (, , ) oznaczające odpowiednio liczbę norek świstaków, liczbę magnetofonów Gnębona, liczbę dni "eksperymentu" Gnębona i zasięg rażenia magnetofonu.

Drugi wiersz wejścia zawiera liczb całkowitych () oznaczających odległości norek o numerach od norki numer 1.

Trzeci wiersz zawiera liczb całkowitych () oznaczających odległości kolejnych magnetofonów od norki numer 1. Wszystkie magnetofony położone są na wschód od tej norki.

Dalej na wejściu następuje wierszy; -ty z nich zawiera dwie liczby całkowite oraz (, ) oznaczające, że na początku -tego dnia "zabawy" Gnębon zamierza przestawić magnetofon znajdujący się metrów od norki numer 1 w punkt odległy o metrów na wschód od tej norki. Możesz założyć, że przed wykonaniem takiej operacji na pozycji znajduje się jakiś magnetofon oraz że na pozycji nie ma jeszcze żadnego magnetofonu.

Wyjście

Twój program powinien wypisać wierszy. Wiersz numer (dla ) powinien zawierać jedną liczbę całkowitą, oznaczającą liczbę norek, w których żaden świstak na pewno się nie wyśpi w nocy przed wykonaniem -tej zamiany. W ostatnim wierszu należy wypisać, w ilu norkach świstaki nie będą mogły spać po ostatniej zamianie.

Przykład

Dla danych wejściowych:

5 3 4 1
2 5 6 11
2 4 8
2 1
4 10
8 6
1 8

poprawną odpowiedzią jest:

2
3
3
5
3

Autor zadania: Jakub Radoszewski.