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|$ 이다.