沿着一条直线站着 $n$ 只口渴的蚂蚁。起初，第 $i$ 只蚂蚁位于坐标为 $x_{i}$ 的点（为简化问题，我们在直线上引入数轴），其中 $x_{1} \le x_{2} \le \ldots \le x_{n}$。

露水滴落在直线上。我们知道，第 $i$ 滴露水将在时刻 $t_{i}$ 落在坐标为 $y_{i}$ 的点上（$1 \le t_{1} \le t_{2} \le \ldots \le t_{m}$）。如果某一时刻直线上没有任何露水，则蚂蚁原地不动。否则，每只蚂蚁将以单位速度朝着离它最近的露水滴移动——如果有两滴露水等距，则向左边的那滴移动。当某只蚂蚁到达露水所在的位置时，它会立即喝掉这滴露水。

请注意，喝掉露水可能会改变蚂蚁接下来的移动方式。如果多只蚂蚁同时到达同一滴露水，它们会平均分掉这滴露水（并立即喝掉）。特别地，一条直线上的某个点可能存在不止一只蚂蚁。如果露水正好落在某只蚂蚁所在的位置上，它会在露水落下的瞬间喝掉它，并且这不会以任何方式影响蚂蚁的移动。

你的任务是确定在最后一滴露水被喝掉时，所有蚂蚁的最终位置。

输入格式

第一行输入包含一个整数 $n$（$1 \le n \le 250,000$），表示蚂蚁的数量。 第二行包含一个非递减的整数序列 $x_{i}$（$1 \le x_{i} \le 10^{9}$），表示沿直线依次排列的蚂蚁的位置。 第三行包含一个整数 $m$（$1 \le m \le 250,000$），表示事件的数量。接下来的 $m$ 行中，每行包含两个整数 $t_{i}$ 和 $y_{i}$（$1 \le t_{i}, y_{i} \le 10^{9}$），表示在时刻 $t_{i}$ 有一滴露水落在坐标为 $y_{i}$ 的点上。事件按时间 $t_{i}$ 的非递减顺序给出。

输出格式

你的程序应输出一行，包含 $n$ 个整数，表示在最后一滴露水被喝掉时，各个蚂蚁的位置。输出序列需按非递减顺序输出。

示例

输入

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

输出

1 1 2 6 7