목마른 개미

수직선 위에 목마른 개미 $n$마리가 놓여 있다. 처음에 $i$번째 개미는 좌표가 $x_i$인 점에 있으며, $x_1 \le x_2 \le \dots \le x_n$을 만족한다.

수직선 위로 이슬방울이 떨어진다. $i$번째 이슬방울은 시각 $t_i$에 좌표가 $y_i$인 점에 떨어지며, $1 \le t_1 \le t_2 \le \dots \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$개의 정수를 한 줄에 공백으로 구분하여 비내림차순으로 출력한다.