Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
62 - ZOJ Monthly, January 2008 - 1009
Ten drops

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Have you ever played the flash game "10 drops" before?

I have tried this game several times, but I am not good at playing this game because of my bad imagination. So I come to you, one of the best programmers in the world, for help. The target is to find the status of the grid after several given actions. Do you think that is too easy? But, to me, it is an impossible mission. So, if you help me to solve it, I'll appreciate it.

INSTRUCTIONS:
    You start with m drops in your tank;
    Use them to grow blobs until they burst;
    We use a number 0 <= x < k to describe the size of the blob: 0 indicate there is no blobs, and a blob with a given size k will burst. Once a drop attach to a blob, the size of it will increase by 1. The burst blob will release four drops moving in four directions, and they move in the same speed.
    If a drop moves to a grid which contains a blob, the blob will grow. What's more, if more than one drops move to the same grid simultaneously, you can assume that the one comes from north (up) attaches the blob first, then south second, west third and east last.
    An action is a left click in some grid in the game (the left top one is (0,0), and (0,1) is to the east of (0,0)). A left click indicates that you use 1 drop in your tank (if it's not empty) to grow the blob in that grid. Of cause, a left click in grid without blob should be ignored because it's meaningless.

Input

There are multiple test cases. Each case begins with a line containing four integer n, m, k, p where n < 20 indicates the size of the grid is n * n; m <= 1000 is the number of rest drops in your tank; k <= 10 is the burst size of blob; and p is the number of actions. The next n lines each with n integers less than k. And then p lines each with 2 integers x, y stand for an action. Both x and y are less than n.

Process to the end of file.

Output

Print the number of left drops after p actions in tank in a line. Then print the description of the grid after p actions as the input shows.

Print a blank line between cases.

Sample Input

6 10 5 3
002243
423200
030132
132214
143213
403202
1 2
2 1
3 1
6 10 5 4
002243
423200
030132
132214
143213
403202
1 2
2 1
3 1
2 1

Sample Output

7
002243
424200
040132
142214
143213
403202

6
003243
000400
000232
304214
204213
403202

Author: WU, Zejun


Submit    Status