题目描述

In the capital of Byteotia, Bytau, the layout of streets is highly regular. Every street leads either from north to south, or from east to west. Therefore every north-south street intersects every east-west street in exactly one spot. Furthermore, along every street its successive intersections are exactly 1 km apart.

Bytau is not only the capital, but also one of the oldest cities in Byteotia. No wonder that there are as many as historic buildings, each at one of the intersections. The City Council cares for their protection very much, and is now concerned with the risk of fire. Hence they have decided to establish two main fire stations in the city. Each monument is going to be protected by the nearest station; by both, should both fire stations be equally close.

Housing is very dense in Bytau, so Euclidean distance is not the measure of choice. The distance between a monument and fire station should rather be defined as the length of the shortest path along the streets between them.

The City Council has prepared several projects of the stations' location. And you have been asked to determine, for each of them, the number of monuments protected by: the first station only, the second station only, and both stations, respectively.

输入格式

In the first line of the standard input there are four integers $n$, $m$, $z$ and $p$ ($1\le n,m\le 1{,}000{,}000{,}000$, $1\le z,p\le 100{,}000$) separated by single spaces and denoting respectively: the number of streets leading from north to south, the number of streets leading from east to west, the number of historic buildings in Bytau, and the number of projects proposed by the City Council.

The north-south streets are numbered from $1$ to $n$, west to east. The east-west streets are numbered from $1$ to $m$, north to south. The intersection of $x$-th north-south and $y$-th east-west street will be denoted by the coordinates $(x,y)$.

In each of the following lines there are two integers $x_i$ and $y_i$ ($1 ≤ xi ≤ n$, $1 ≤ yi ≤ m$) separated by a single space and denoting the coordinates of the i-th monument. No pair of different monuments is located at the same intersection.

Each of the following $p$ lines contains one proposal of the City Council - four integers $x_{j,1}, y_{j,1}, x_{j,2}, y_{j,2}$ separated by single spaces, $1 ≤ x_{j,1},x_{j,2} ≤ n$, $1 ≤ y_{j,1},y_{j,2} ≤ m$, $(x_{j,1},y_{j,1})≠(x_{j,2},y_{j,2})$. The coordinates $(x_{j,1},y_{j,1})$ and $(x_{j,2},y_{j,2})$ describe the intersections at which the fire stations are to be located according to the $j$-th proposal $(1 ≤ j ≤ p)$.

输出格式

Your programme should print out exactly $p$ lines on the standard output.

There should be three integers in the $j$-th line, denoting:

the number of monuments protected by the first station of $j$-th proposal of the City Council only, the number of monuments protected by the second station only and the number of monuments protected by both stations, respectively.

These numbers should be separated by single spaces.

题目大意

平面上有 $z$ 个点，给你 $p$ 个形如 $p_1(x_1,y_1),p_2(x_2,y_2)$ 的询问，要你求出 $z$ 个点中离 $p_1$ 更近的点，离 $p_2$ 更近的点，与 $p_1$ 和 $p_2$ 的距离相等的点各有多少个。这里的距离指的是曼哈顿距离，即x坐标之差的绝对值加上y坐标之差的绝对值。

6 5 6 1
1 2
6 5
5 1
3 3
3 4
4 1
2 3 4 3

1 3 2