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.