Problem 14095

14095 - NTHU - Dormitory

Status | Limits Submit

	Time	Memory
Case 1	1 sec	512 MB
Case 2	1 sec	512 MB
Case 3	1 sec	512 MB
Case 4	1 sec	512 MB
Case 5	1 sec	512 MB
Case 6	1 sec	512 MB

Description

The NTHU campus map is represented by an R × C table A, where A_{i, j} represents the number of residents (居住人數) in the dormitory located at (i, j). If A_{i, j} = -1, it means that the dormitory cannot accommodate residents.

We define K as the average dormitory satisfaction, which can be obtained through statistical analysis. Each day, every dormitory will transfer (Integer division, round down) individuals to each of its four adjacent dormitories. Please output the numbers of residents in the dormitories after M days.

Note: Adjacency is defined in the four cardinal directions (up, down, left, and right). If there is no dormitory in that direction or if the adjacent dormitory cannot accommodate residents, no one will be transferred in that direction.

** No Recursion Is Required. :) **

Input

The first line consists of four positive integers, R, C, K, M.
Following that, there are R lines, each containing C integers A_{i, j}.

Constraints

Test Case 1: R = 1, M = 1
Test Cases 2 ~ 3: R = 1
Test Cases 4 ~ 6: satisfy no additional constraints.
For all test cases: 1 ≤ R, C ≤ 100, 4 ≤ K ≤ 100, 1 ≤ M ≤ 100, -1 ≤ A_{i, j} ≤ 100

Output

Output a total of R lines, each containing C integers A_{i, j}, representing the table A after M days.

Remember to print a ‘\n’ at the end of the output.

Do not include any spaces at the end of line.

Sample Input Download

# Sample Input 1:

2 3 4 1
10 2 -1 
5 -1 2

# Sample Input 2:

3 5 4 3
4 8 7 6 3
3 2 1 9 10
-1 7 6 5 4

Sample Output Download

# Sample Output 1:

7 4 -1
6 -1 2

# Sample Output 2:

4 4 7 6 6
4 5 5 5 7
-1 6 5 6 5