Despite YY's so much homework, she would like to take some time to play with her minions first.

YY lines her minions up to an `N`*`M` matrix. Every minion has two statuses: awake or asleep. We use 0(the digit) to represent that it is asleep, and 1 for awake.
Also, we define the minions who are around a minion **closest** in one of the **eight** directions its neighbors.
And every minute every minion will change its status by the following specific rules:

Also, some minions will get bored and leave this silly game. We use 'X's to describe them.
We suppose that a minion would leave after `T` minutes. It will leave at the end of the T^{th} minute.
Its status is considered during the change at the beginning of the T^{th} minute, and should be ignored after that.
Of course, one minion will not leave twice!

YY is a girl full of curiosity and wants to know every minion's status after `F` minutes. But you know she is weak and lazy! Please help this cute girl to solve this problem :)

There are multiple test cases.

The first line contains the number of test cases `Q`. 1<=`Q`<=100.

For each case, there are several lines:

The first line contains four integers `N`, `M`, `F`, `K`. `K` means the number of leaving messages. 1<=`N`, `M`<=50, 1<=`F`<=1000, 1<=`K`<=N*M.

Next `N` lines are the matrix which shows the initial status of each minion. Each line contains `M` chars. We guarantee that 'X' wouldn't appear in initial status matrix.

And next `K` lines are the leaving messages. Each line contains three integers `T _{i}`,

提交代码