time limit per test: 0.25 sec.
memory limit per test: 65536 KB

input: standard
output: standard

Qc has discovered n new amusing cultures of bacteria. The bacteria are grown in a special container divided into qxc cells. Initially one bacterium of each culture is put into some cell of the box. After that they start to grow.
Each second the following actions take place.
First the bacteria of the first culture divide simultaneously. Each bacterium divides into five ones, and if the dividing bacterium occupied the cell (x, y), the five bacteria try to occupy cells (x, y), (x-1, y), (x+1, y), (x, y-1) and (x, y+1). If the required cell does not exist, or is occupied by the bacterium of the other culture, the corresponding bacterium dies. If the cell that the bacterium goes to is already occupied by the bacterium of the same culture, the younger bacterium kills the older one and occupies the cell. If two bacteria of the same generation try to occupy the same cell, the random one wins and kills the other one.
After bacteria of the first culture divide, bacteria of the second culture do, after that the bacteria of the third culture, and so on. It takes one second for all n cultures to divide.
All cultures divide in the described way each second.
Given the initial positions of bacteria of all cultures, Qc wants to know how many cells are occupied by each culture after t seconds.

The first line of the input contains four integer numbers: 1 <= q, c, <= 1000, 1 <= n <= 22204 --- the number of cultures and 0 <= t <= 10^9. Next n lines contains n pairs of integer numbers (xi, yi) --- initial positions of bacteria of each culture. No two bacteria initially occupy the same cell. Size q is for x coordinates, c is for y.

Print n lines of output, each line must contain a single integer --- the answer for the i-th culture.

Input

10 10 3 3
3 3
6 2
7 9