You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

一条直线上有 $m$ 个位置，分别为位置1，位置2，...,位置m。每个位置上最多放置一辆碰碰车。

一开始有 $n$ 辆碰碰车，分别在位置 $a_1, a_2, ..., a_n$。

现在有 $k$ 次移动。每次告诉你2个数字，$i$ 和 $x$，表示将碰碰车 $i$ 移动到位置$x$。 假如过程中碰到其他车，会将那些车往那个方向推动到下一个位置，使得每个位置最多放置一辆车。

例如原来有4辆车，位置分别为7，10，15，16。

如将车2移动到19，4辆车的位置分别为 7，19，20，21.

再将车3移动到5，4辆车位置分别为3，4，5，21.

再将车4移动9，4辆车位置分别为3，4，5，9.

保证每次移动都是合法的,保证碰碰车位置始终在1~~m。

问最后每辆车的位置。

Format

Input

第一行两个整数 $n$ 和 $m$。

接下来一行， $n$ 个整数，表示$n$辆碰碰车的位置。

接下来一行，一个整数q。

接下来q行，每行两个整数i和x，表示将碰碰车i移动到位置x。

Output

一行，$n$ 个整数，整数间用空格分开，表示碰碰车的位置。

Samples

4 100
7 10 15 16
3
2 19
3 5
4 9

3 4 5 9

Limitation

30% $1 \le n, q \le 100, m\le 1000$

60% $1 \le n,q \le 1000, n \le m \le 10^6$

100% $1 \le n \le 1000, 1\le q \le 20000, n\le m \le 10^9$