Along a straight line, $ n $ thirsty ants are lined up. Initially, the $ i $-th ant is located at coordinate $ x_{i} $ (for simplicity, we use a number line), where $ x_{1} \le x_{2} \le \ldots \le x_{n} $.

Dew drops fall onto the line. We know that the $ i $-th dew drop falls at time $ t_{i} $ at coordinate $ y_{i} $ ($1 \le t_{1} \le t_{2} \le \ldots \le t_{m}$). If there are no dew drops on the line at a given moment, the ants remain stationary. Otherwise, each ant moves at unit speed toward the nearest dew drop; if there are two such nearest drops, it moves to the left. When an ant reaches a drop, it immediately drinks it.

Note that drinking a drop may change the way the ants move subsequently. If several ants reach a drop at the same time, they share the water from that drop equally (and drink it immediately). In particular, more than one ant can be at the same point on the line. If a drop falls directly onto an ant, it is consumed exactly at the moment it falls and does not affect the movement of the ants in any way.

Your task is to determine the final positions of all ants, i.e., at the moment the last dew drop is consumed.

Input

The first line of input contains a single integer $ n $ ($1 \le n \le 250\,000$) representing the number of ants. The second line contains a non-decreasing sequence of $ n $ integers $ x_{i} $ ($1 \le x_{i} \le 10^{9}$) representing the positions of the ants along the line. The third line contains a single integer $ m $ ($1 \le m \le 250\,000$) representing the number of events. Each of the following $ m $ lines contains two integers $ t_{i} $ and $ y_{i} $ ($1 \le t_{i}, y_{i} \le 10^{9}$) indicating that at time $ t_{i} $, a dew drop fell at coordinate $ y_{i} $ on the line. The events are listed in non-decreasing order of time $ t_{i} $.

Output

Your program should output a single line containing a sequence of $ n $ integers representing the positions of the individual ants at the moment the last dew drop is consumed. The resulting sequence should be printed in non-decreasing order.

Examples

Input 1

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

Output 1

1 1 2 6 7