34975번 - 그래플링 후크 스페셜 저지

문제

세종이는 안타깝게도 바다에 표류 중이다. 가만히 있을 수 없던 세종이는 가지고 있는 그래플링 후크들을 사용해서 근처에 부유 중인 물자들을 끌어오고자 한다.

바다에는 총 $N$개의 물자가 떠다니고 있다. 물자들은 각각 $xy$ 평면의 한 격자점에 위치하며, 다행히 수면이 잔잔해 움직이지 않는다. 세종이의 위치는 $(0, ,0円)$이다.

세종이는 후크를 총 $M$번 사용할 것이고, $j$번째에 사용할 후크의 길이는 $l_j$이다.

세종이가 길이가 $l$인 후크를 사용하면, 세종이로부터의 맨해튼 거리가 $l$ 이하인 물자들 중 가장 멀리 있는 물자를 맨해튼 거리가 감소하도록 축과 평행한 아무 방향으로 길이 1ドル$만큼 당겨올 수 있다. 만약 가장 멀리 있는 물건이 여러 개라면, 그런 물건들을 모두 한 번에 당길 수 있다. 한 번에 당기는 물건들을 같은 방향으로 당기지 않아도 된다. 만약 가장 멀리 있는 물자가 $(0,0)$에 있다면 후크를 사용해도 물자가 당겨지지 않는다.

세종이가 갖고 있는 후크들을 순서대로 모두 사용했을 때, 물자들의 위치를 예상해보자. 단, 한 격자점에 여러 물자가 동시에 위치할 수 있다.

입력

첫 번째 줄에 물자의 개수 $N$이 주어진다. (1ドル\leq N \leq 100 ,000円$)

두 번째 줄부터 $N$개의 줄에 걸쳐 $i$번째 줄에 $i$번 물자의 위치 $(x_i, ,円 y_i)$를 나타내는 정수 $x_i$와 $y_i$가 공백으로 구분되어 주어진다. ($|x_i|, ,円 |y_i|\le 10^9$)

$N+2$번째 줄에 그래플링 후크의 개수 $M$이 주어진다. (1ドル \leq M \leq 100,000円 $)

$N+3$번째 줄부터 $M$개의 줄에 걸쳐 $j$번째 줄에 $j$번 그래플링 후크의 길이 $l_j$가 주어진다. (1ドル\le l_j\leq 2 \times 10^9$)

출력

$N$개의 줄에 걸쳐 $i$번째 줄에 $i$번 물자가 그래플링 후크를 모두 사용한 후에 도달할 수 있는 위치 $(x_i^f,~y_i^f)$를 공백으로 구분하여 출력하라. 도달할 수 있는 위치가 여러 곳이라면 그 중 아무거나 출력해도 된다.

제한

노트

$xy$ 평면에서 격자점은 $(x, ,円 y)$에서 $x$와 $y$ 모두 정수인 점을 의미한다. 일례로, $(0,,1円)$은 격자점이지만, $\left(0, ,円 0.5\right)$는 격자점이 아니다.

또한, $xy$ 평면 위 임의의 두 점 $P(p_1, ,円 p_2)$와 $Q(q_1, ,円 q_2)$에 대하여 맨해튼 거리는 $|p_1-q_1|+|p_2-q_2|$로 정의된다. 즉, $(a, ,円 b)$에 위치한 물자와 세종이 사이의 맨해튼 거리는 $|a|+|b|$이다.