27530번 - UFO in the Sinchon

신촌 하늘에 UFO가 나타났다!

신촌은 $N \times M$ 크기의 격자 모양 지역이고, 현재 신촌에는 $1$번부터 $K$번까지의 번호가 붙은 $K$명의 사람이 있다. $i$번 사람은 처음에 ($y_i, x_i$) 위치에 있다. $(y_i, x_i)$는 신촌을 $NM$개의 $1 \times 1$ 크기 땅으로 나누었을 때, $y_i$번째 행의 $x_i$번째 열에 위치한 칸을 의미한다.

UFO가 나타나면 사람들은 사진을 찍기 위해 UFO가 나타난 위치를 향해 이동한다. 사람들은 매초 상하좌우 대각선으로 인접한 칸으로 한 칸 이동할 수 있는데, 항상 인접한 여덟 칸 중 UFO와의 택시 거리가 가장 가까워지는 칸으로 이동한다. 단, 이미 UFO와 같은 위치에 있는 사람은 더 움직이지 않는다. 이동 과정 중에서 같은 위치에 여러 명의 사람이 있을 수도 있다.

UFO는 총 $Q$번 등장한다. UFO는 한 번 등장하면 ($y_j, x_j$) 위치에 $t_j$초 동안 가만히 떠 있다가 사라진다. UFO는 동시에 나타나지 않고, 항상 직전에 나타난 UFO가 사라진 지 $1$초 뒤에 나타난다. 사람들은 UFO가 나타나는 즉시 움직이기 시작하고, UFO가 없을 때는 움직이지 않고 가만히 있는다. 단, UFO가 사라지는 시점에는 사람들이 움직이지 않는다.

UFO가 더 이상 나타나지 않게 되었을 때, 신촌에 있는 모든 사람의 위치를 출력하라.

첫째 줄에 $N$, $M$, $K$, $Q$가 공백을 두고 주어진다. ($1 \le N, M \le 10^9; 1 \le K \le 200\ 000; 1 \le Q \le 200\ 000$)

다음 $K$개의 줄에는 $i$번 사람의 초기 위치를 의미하는 $y_i$, $x_i$가 공백을 두고 주어진다. ($1 \le y_i \le N; 1 \le x_i \le M$)

다음 $Q$개의 줄에는 UFO가 나타나는 정보가 등장한 순서대로 주어진다. 각 줄에는 UFO가 등장한 위치 $y_j$, $x_j$와 떠 있는 시간 $t_j$가 공백을 두고 주어진다. ($1 \le y_j \le N; 1 \le x_j \le M; 1 \le t_j \le 10^9$)

입력에서 주어지는 모든 수는 정수이다.

UFO가 더 이상 나타나지 않게 되었을 때 사람들의 위치를 한 줄에 하나씩 출력한다. $i$번째 줄에는 $i$번 사람이 있는 위치의 $y$좌표와 $x$좌표를 공백을 두고 출력한다.

두 위치 $(y_1, x_1)$, $(y_2, x_2)$ 사이의 택시 거리는 $|y_1 - y_2| + |x_1 - x_2|$ 이다.