[POI2009] STR-Fire Brigade

题目描述

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.

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

输入格式

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 ![](http://main.edu.pl/images/OI16/str-en-tex.11…

输出格式

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.

样例 #1

样例输入 #1

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

样例输出 #1

1 3 2