No tags yet

No tag edit access

The problem statement has recently been changed. View the changes.

×
time limit per test: 0.25 sec.

memory limit per test: 65536 KB

memory limit per test: 65536 KB

input: standard

output: standard

output: standard

Qc has discovered n new amusing cultures of bacteria. The bacteria are grown in a special container divided into q*x*c 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.

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

3 3

6 2

7 9

Output

21

15

21

15

21

Author: | Anton Golubev, Petrazavodsk SU |

Resource: | Anton Golubev (Hedgehog)'s Contest #2 from Annual Summer Russian Teams Meeting in Petrozavodsk State University |

Date: | August 26, 2005 |

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/24/2021 19:26:59 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|