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.