AVIRUT - Alien Virut

We have a matrix, size n*m. The point in line i and column j is point (i,j).

Now, we pour water in point (x,y) at seconds 0.

If at seconds k, point (i,j) have water, we say point (i,j) is degree k. And water'll pour to point (x-1,y),(x+1,y),(x,y-1),(x,y+1) at seconds k+1 if they are having no water. But if c[i,j]=w, point (i,j) never have water, and haven't degree of course.

In point (i,j) (degree k) have some virut dying. But if have water, they live again. And they'll attack some point that degree ≥ k-b[i,j] and degree ≤ k; and total virut in them augment a[i,j].

Finally, if total virut in point (i,j)>c[i,j], house in this point will be infection.

Input

The first line is 5 integer: n,m,x,y,w.

In n group line next, group line i is m line, line j in m line is 3 integer: a[i,j],b[i,j],c[i,j].

Output

n Line. Line i is a integer: The number of house in line i that is infection.

Example

Input:

 3 3 1 2 5

1 1 20

1 3 40

1 1 5

2 0 29

1 1 1

2 2 2

2 3 5

1 4 4

1 5 50

Output: 0
2 
1
Note:
	0<n,m<501. 0<a[i,j]<1001. 0≤b[i,j]≤m*n. 0<c[i,j]≤1000000000.

 50% test: 0<n,m<101.


Added by:Phạm Bá Thái
Date:2013-10-02
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Mine

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.