소방서

바이트오티아의 수도 바이타우는 도로가 완벽한 격자 형태로 놓여 있다. 모든 도로는 남북 방향 아니면 동서 방향으로만 뻗어 있어서, 남북 방향 도로는 모두 동서 방향 도로와 정확히 한 곳에서 교차한다. 한 도로 위에서 이웃한 두 교차점 사이의 거리는 항상 $1$ km이다.

바이타우에는 유서 깊은 기념물이 $z$개 있으며, 각 기념물은 서로 다른 교차점에 하나씩 놓여 있다. 시 의회는 화재로부터 이 기념물들을 지키기 위해 소방서 두 곳을 세우려고 한다. 각 기념물은 가장 가까운 소방서가 지키며, 두 소방서까지의 거리가 같다면 두 소방서가 함께 지킨다.

도시가 매우 조밀하기 때문에 거리는 직선 거리가 아니라 도로를 따라 잰다. 기념물과 소방서 사이의 거리는 둘을 잇는 도로를 따라가는 최단 경로의 길이, 즉 맨해튼 거리로 정의한다.

시 의회는 두 소방서를 놓을 후보 위치를 여러 개 준비했다. 각 후보안마다 첫 번째 소방서만 지키는 기념물 수, 두 번째 소방서만 지키는 기념물 수, 그리고 두 소방서가 함께 지키는 기념물 수를 구하여라.

첫째 줄에 네 정수 $n$, $m$, $z$, $p$가 주어진다 ($1 \le n, m \le 10^9$, $1 \le z, p \le 100{,}000$). 각각 남북 방향 도로의 수, 동서 방향 도로의 수, 기념물의 수, 후보안의 수를 뜻한다.

남북 방향 도로는 서쪽부터 동쪽으로 $1$번부터 $n$번까지, 동서 방향 도로는 북쪽부터 남쪽으로 $1$번부터 $m$번까지 번호가 매겨져 있다. $x$번 남북 도로와 $y$번 동서 도로가 만나는 교차점을 좌표 $(x, y)$로 나타낸다.

다음 $z$개의 줄에는 각각 두 정수 $x_i$와 $y_i$가 주어진다 ($1 \le x_i \le n$, $1 \le y_i \le m$). $i$번째 기념물의 좌표를 뜻하며, 서로 다른 두 기념물이 같은 교차점에 놓이는 경우는 없다.

이어지는 $p$개의 줄에는 각각 네 정수 $x_{j,1}$, $y_{j,1}$, $x_{j,2}$, $y_{j,2}$가 주어진다 ($1 \le x_{j,1}, x_{j,2} \le n$, $1 \le y_{j,1}, y_{j,2} \le m$, $(x_{j,1}, y_{j,1}) \ne (x_{j,2}, y_{j,2})$). $j$번째 후보안에서 첫 번째와 두 번째 소방서가 놓이는 교차점을 뜻한다.

정확히 $p$개의 줄을 출력한다. $j$번째 줄에는 $j$번째 후보안에 대해 세 정수를 공백 하나로 구분하여 출력한다: 첫 번째 소방서만 지키는 기념물 수, 두 번째 소방서만 지키는 기념물 수, 두 소방서가 함께 지키는 기념물 수.