gridgame

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 jth integer on the ith 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 ith 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⁶, there are no obstacles.

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

Subtask 5 (23%): 1 ≤ H, W ≤ 1000, 1 ≤ K ≤ 10⁶.

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