Mrówki [A]

Limit pamięci: 256 MB

Wzdłuż prostej ustawiło się spragnionych mrówek. Początkowo -ta mrówka znajduje się w punkcie o współrzędnej (dla uproszczenia na prostej wprowadzamy oś liczbową), przy czym .

Na prostą spadają krople rosy. Wiemy, że -ta kropla rosy spadnie w chwili na punkt o współrzędnej (). Jeśli w danym momencie na prostej nie ma żadnych kropel, to mrówki stoją w miejscu. W przeciwnym razie każda z mrówek podąża z jednostkową prędkością do najbliższej jej kropli rosy - w przypadku, gdy są dwie takie najbliższe krople, porusza się w lewo. Gdy jakaś mrówka dotrze do kropli, to natychmiast wypija tę kroplę.

Zauważ, że wypicie kropli może zmienić sposób dalszego poruszania się mrówek. Jeśli do kropli jednocześnie dotrze kilka mrówek, mrówki dzielą się wodą z tej kropli po równo (i natychmiast ją wypijają). W szczególności, w jednym punkcie prostej może znajdować się więcej niż jedna mrówka. Jeśli kropla spadnie bezpośrednio na mrówkę, zostaje wypita dokładnie w momencie spadnięcia i nie wpływa w żaden sposób na ruch mrówek.

Twoim zadaniem jest stwierdzenie, jakie będą położenia wszystkich mrówek na końcu, tzn. w chwili, gdy zostanie wypita ostatnia kropla rosy.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą () oznaczającą liczbę mrówek. Drugi wiersz zawiera niemalejący ciąg liczb całkowitych () oznaczających położenia kolejnych mrówek wzdłuż prostej. Trzeci wiersz zawiera jedną liczbę całkowitą () oznaczającą liczbę zdarzeń. Każdy z kolejnych wierszy zawiera dwie liczby całkowite oraz () oznaczające, że w chwili na punkt prostej o współrzędnej spadła kropla rosy. Zdarzenia będą wymienione w niemalejącej kolejności czasów .

Wyjście

Twój program powinien wypisać jeden wiersz zawierający ciąg liczb całkowitych oznaczający położenia poszczególnych mrówek w chwili, gdy skonsumowana zostanie ostatnia kropla rosy. Ciąg wynikowy należy wypisać w kolejności niemalejącej.

Przykład

Dla danych wejściowych:

5
1 3 4 6 7
4
1 2
2 9
4 5
4 1

poprawną odpowiedzią jest:

1 1 2 6 7 

Autor zadania: Adam Karczmarz.