Fire Brigade

In Bytau, the capital of Byteotia, the street layout is a perfectly regular grid. Every street runs either north-south or east-west, so each north-south street crosses each east-west street at exactly one intersection. Along any street, consecutive intersections are exactly $1$ km apart.

Bytau has $z$ historic monuments, each standing at a distinct intersection. To protect them from fire, the City Council will build two fire stations. Every monument is guarded by the station nearest to it; if both stations are equally near, the monument is guarded by both.

Because the city is densely built, distance is measured along the streets rather than as the crow flies. The distance between a monument and a fire station is the length of the shortest path along the streets connecting them, that is, the Manhattan distance.

The Council has prepared several candidate placements for the two stations. For each placement, determine how many monuments are guarded by the first station only, by the second station only, and by both stations.

The first line contains four integers $n$, $m$, $z$, and $p$ ($1 \le n, m \le 10^9$, $1 \le z, p \le 100{,}000$): the number of north-south streets, the number of east-west streets, the number of monuments, and the number of candidate placements.

The north-south streets are numbered $1$ to $n$ from west to east; the east-west streets are numbered $1$ to $m$ from north to south. The intersection of the $x$-th north-south street and the $y$-th east-west street is written as $(x, y)$.

Each of the next $z$ lines contains two integers $x_i$ and $y_i$ ($1 \le x_i \le n$, $1 \le y_i \le m$): the coordinates of the $i$-th monument. No two monuments share an intersection.

Each of the next $p$ lines contains four integers $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})$): the intersections where the first and second fire stations are placed in the $j$-th proposal.

Print exactly $p$ lines. The $j$-th line contains three integers separated by single spaces: the number of monuments guarded by the first station only, by the second station only, and by both stations, for the $j$-th placement.