Wstęp do programowania w C++

Richard Feynman był naprawdę niezwykle fascynującym człowiekiem - otrzymał nagrodę Nobla w dziedzinie fizyki, rozszyfrowywał hieroglify Majów, grał sambę na bębnach podczas karnawału w Rio, rozkręcał też imprezę w studenckim klubie Hybrydy (oczywiście grając na perkusji i ucząc polskich studentów samby). Zajmował się również biologią, w ramach swoich biologicznych eksperymentów przeprowadził szereg bardziej i mniej poważnych badań na mrówkach :-)

My co prawda z fizyki jesteśmy raczej przeciętni, grać na perkusji nie umiemy zupełnie, a hieroglifów nie widzieliśmy na oczy lecz nic nie stoi na przeszkodzie żebyśmy poeksperymentowali z mrówkami! Nasz eksperyment zakłada, że weźmiemy garść mrówek i umieścimy je w jednowymiarowej przestrzeni. W przestrzeni tej będą się znajdowały co najmniej dwa otwory - na początku i końcu odcinka na jakim umieściliśmy owady. Oczywiście mrówki jako stworzenia pracowite nie znoszą stagnacji - od razu po umieszczeniu na placu eksperymentu zaczynają się poruszać ze stałą prędkością równą 1 polu na kolejkę. Chodzą chaotycznie w prawo lub lewo odbijając się od siebie w nieskończenie krótkim czasie. Pierwszą rzeczą jaką zaobserwowaliśmy jest to, że gdy mrówki wpadają na siebie, błyskawicznie zawracają i zaczynają iść w drugą stronę dopóki nie trafią na kolejną mrówkę idącą w przeciwnym kierunku lub nie wpadną do dołka. Oczywiście chcielibyśmy poprosić Cię o niewielką pomoc - napisz program, który na podstawie współrzędnych początkowych mrówek oraz dołków a także kierunku w jakim porusza się każda z mrówek w momencie 0 obliczy ile owadów wpadnie do danego dołka oraz po ilu kolejkach wpadnie ostatnia z nich (dla każdego z dołków). W momencie początkowym żadna z mrówek nie znajduje się w dołku, dwie mrówki nie mogą również znajdować się w tym samym punkcie. Oprócz tego żadne dwa dołki nie mogą być w bezpośrednim sąsiedztwie.

Wejście

W pierwszej linii wejścia znajduje się dokładnie jedna liczba całkowita Z (1 ≤ Z ≤ 10) określająca liczbę zestawów danych.

W pierwszej linii każdego zestawu danych znajduje się liczba p (2 ≤ p ≤ 1000) określająca liczbę dołków, po której wypisane są współrzędne każdego z dołków. Dołki o najniższej i najwyższej współrzędnej określają rozmiar pola (1 ≤ współrzędna dołka ≤ 2 × 10⁹). W drugiej linii każdego zestawu znajduje się liczba n (0 ≤ n ≤ 300000) określająca ile mrówek w chwili 0 przemieszcza się w prawo. Po liczbie n wypisanych jest n liczb – są to współrzędne każdej z mrówek idących w prawo w chwili startu. W kolejnej linii analogicznie opisane są mrówki idące w lewo. Współrzędne dołków oraz mrówek podane są w kolejności rosnącej.

Wyjście

Dla każdego zestawu danych należy w osobnej linii wypisać ile mrówek wpadnie do danego dołka i po jakim czasie do tego dołka wpadnie ostatnia z nich. Wyniki dla poszczególnych dołków wypisujemy zgodnie z kolejnością na wejściu.

Przykład

Wejście:

1
3
1 8 17
6
2 3 5 11 12 13
5
4 6 7 9 10

Wyjście:

3 6
5 6
3 6