Fire Brigade

Memory limit: 64 MB

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.

Input

In the first line of the standard input there are four integers , , and (, ) 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 to , west to east. The east-west streets are numbered from to , north to south. The intersection of -th north-south and -th east-west street will be denoted by the coordinates .

In each of the following lines there are two integers and (, ) separated by a single space and denoting the coordinates of the -th monument. No pair of different monuments is located at the same intersection.

Each of the following lines contains one proposal of the City Council - four integers , , , separated by single spaces, , , . The coordinates and describe the intersections at which the fire stations are to be located according to the -th proposal ().

Output

Your programme should print out exactly lines on the standard output. There should be three integers in the -th line, denoting: the number of monuments protected by the first station of -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.

Example

For the input data:

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

the correct result is:

1 3 2

The dashed lines in the figure represent streets, circles - locations of monuments, while crosses - proposed locations of fire stations. White circles depict monuments protected by the first station only, black circles - by second station only, while grey ones - by both stations.

Task authors: Marian M. Kedzierski and Jakub Radoszewski.