Problem J
Pumpkin Patch

Illustration of Sample Input 2

Pumpkin Pete is trying out a new type of “rapid-growth” pumpkin seed that he bought from the farmer’s market. Without looking at the directions, Pumpkin Pete tears through the packaging and plants the seeds he has into his pumpkin patch. Unbeknownst to Pumpkin Pete, his rival, Gourd Gary, is watching him plant the new seeds from a secret vantage point. After Pumpkin Pete leaves the pumpkin patch, Gourd Gary approaches the patch and picks up the packaging that Pumpkin Pete left on the ground. The packaging says the following:

• A pumpkin starts with four roots of length zero.

• Each of the pumpkin’s four roots grow a single unit in a different cardinal direction each day.

• When a pumpkin dies, its remains will not disappear.

• If any of the roots grow into another pumpkin or its roots – dead or alive – the pumpkin will die at the end of that day.

• Roots cannot grow outside of the bounds of a plot. In other words, a pumpkin will die if one of its roots tries to go outside the bounds of the pumpkin patch.

• If the roots of multiple pumpkins reach the same spot on the same day, each one of the affected roots stops growing (i.e. fight for nutrients) and in turn, the pumpkins will die at the end of the day.

• When a pumpkin dies, its roots do not grow on subsequent days.

With this information and the knowledge of where each of the pumpkin seeds were planted, Gourd Gary starts to think about which pumpkins would still be alive if they were left to grow for $D$ days$\ldots $

Input

The first line of input contains three integers: the number of pumpkins $P$, the number of days $D$ that will pass ($1 \leq D \leq 10$), and $N$ ($1 \leq N \leq 30, 1 \leq P \leq N^2$) the dimension of the $N\times N$ grid. The next $P$ lines of input contain two integers, $R$ and $C$ ($0 \leq R,C < N$), representing the row and column position of each pumpkin. No two pumpkins will be at the same position. Position $(0,0)$ is the top left corner of the grid.

Output

The output will consist of a single line per pumpkin in the same relative order as the input. If the pumpkin is alive after $D$ days have passed, print “ALIVE”. Otherwise, print the day the pumpkin died as a single integer.

4 2 8
3 2
5 5
4 3
1 1

1
2
1
2

5 3 10
0 0
6 3
6 4
3 6
2 1

1
1
1
ALIVE
2