Thirsty Ants

There are $n$ thirsty ants placed on a number line. Initially the $i$-th ant is at the point with coordinate $x_i$, and $x_1 \le x_2 \le \dots \le x_n$.

Drops of dew fall onto the line. The $i$-th drop falls at time $t_i$ onto the point with coordinate $y_i$, where $1 \le t_1 \le t_2 \le \dots \le t_m$. If at some moment there is no drop on the line, every ant stays still. Otherwise each ant moves at unit speed toward the drop nearest to it; if the two nearest drops are equally far (one to the left and one to the right), the ant moves toward the left one. As soon as an ant reaches a drop, it drinks that drop.

Drinking a drop may change how the ants move afterward. If several ants reach one drop at the same instant, they share its water equally and drink it immediately. In particular, more than one ant may occupy the same point. If a drop falls exactly onto an ant, it is drunk at the very instant it lands and does not influence the ants' movement in any way.

Determine the position of every ant at the moment the last drop of dew is drunk, that is, when no drop remains on the line.

The first line contains the number of ants $n$ ($1 \le n \le 250\,000$). The second line contains a non-decreasing sequence of $n$ integers $x_i$ ($1 \le x_i \le 10^9$), the positions of the ants. The third line contains the number of events $m$ ($1 \le m \le 250\,000$). Each of the next $m$ lines contains two integers $t_i$ and $y_i$ ($1 \le t_i, y_i \le 10^9$), meaning that at time $t_i$ a drop of dew fell onto the point with coordinate $y_i$. The events are given in non-decreasing order of $t_i$.

Print $n$ integers on a single line, separated by single spaces, giving the position of each ant at the moment the last drop is consumed. Print them in non-decreasing order.