#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## Problem Description

Gug is bored with his AI, and is trying to program it to play a simple game on a grid. The grid that Gug is using is *H* grid squares tall and *W* grid squares wide, with some grid squares containing an obstacle. The rows of the grid are numbered 0 to *H*-1 from top to bottom, and the columns of the grid are numbered 0 to *W*-1 from left to right. For each grid square that is not an obstacle, it can be turned on or off during the game.

At time = 0, exactly one square on the grid is turned on, with coordinates (*X*, *Y*). At every subsequent time interval *t*, a square will be switched on if and only if any of its neighbours to the top, left, bottom or right are switched on at time *t*-1, and the square is not an obstacle.

Gug wants to know: at each time = t, where t = 1..K, how many grid squares are switched on.

## Input

The first line of input will contain five integers, *H*, *W*, *X*, *Y* and *K*.

The next *H* lines of input will contain *W* integers each, with the *j*th integer on the *i*th line being 1 if the grid square at (*i*, *j*) is an obstacle and 0 otherwise. It is guranteed that (*X*, *Y*) will not be an obstacle.

## Output

The output should contain *K* lines, with the *i*th line representing the number of grid squares which are turned on at time = *i*.

## Limits

For all subtasks: 0 ≤ X < H, 0 ≤ Y < W.

Subtask 1 (27%): 1 ≤ H, W, K ≤ 300.

Subtask 2 (16%): 1 ≤ H, W, K ≤ 1000.

Subtask 3 (13%): H = 1, 1 ≤ W ≤ 1000, 1 ≤ K ≤ 10^{6}, there are no obstacles.

Subtask 4 (21%): 1 ≤ H, W ≤ 1000, 1 ≤ K ≤ 10^{6}, there are no obstacles.

Subtask 5 (23%): 1 ≤ H, W ≤ 1000, 1 ≤ K ≤ 10^{6}.

Subtask 6 (0%): Sample Testcases.

## Sample Input 1

4 4 0 0 7 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0

## Sample Output 1

2 3 4 5 6 7 6

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 27 | 22 | 2s | 256MB | Minimum |

2 | 16 | 42 | 2s | 256MB | Minimum |

3 | 13 | 21 | 2s | 256MB | Minimum |

4 | 21 | 41 | 2s | 256MB | Minimum |

5 | 23 | 102 | 2s | 256MB | Minimum |

6 | 0 | 1 | 2s | 256MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o gridgame -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512