Wzdłuż prostej ustawiło się $ n $ spragnionych mrówek. Początkowo $ i $-ta mrówka znajduje się w punkcie o współrzędnej $ x_{i} $ (dla uproszczenia na prostej wprowadzamy oś liczbową), przy czym $ x_{1} \le x_{2} \le \ldots \le x_{n} $.

Na prostą spadają krople rosy. Wiemy, że $ i $-ta kropla rosy spadnie w chwili $ t_{i} $ na punkt o współrzędnej $ y_{i} $ (1 ≤ $ t_{1} \le t_{2} \le \ldots \le t_{m} $). 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.

Input Format

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

Output Format

Twój program powinien wypisać jeden wiersz zawierający ciąg $ n $ 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.

Example

Input

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

Output

1 1 2 6 7