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^thminute. 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 :)

Input

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, X_i, Y_i, They mean the minion who is located in (X_i, Y_i) will leave the game at the end of the T_i^th minutes. 1<=T_i<= F, 1<=X_i<=N, 1<=Y_i<=M.

Output

For each case, output N lines as a matrix which shows the status of each minion after F minutes.

Sample Input

2
3 3 2 1
101
110
001
1 2 2
5 5 6 3
10111
01000
00000
01100
10000
2 3 3
2 4 1
5 1 5

Sample Output

010
1X0
010
0000X
11000
00X00
X0000
00000

Hint

For case 1:

T=0, the game starts
101
110
001
---------------
at the beginning of T=1, a change took place
100
101
010
---------------
at the end of T=1 (the minion in (2,2) left)
100
1X1
010
---------------
at the beginning of T=2, a change took place
010
1X0
010
---------------
at the end of T=2 (nothing changed for no minion left at T=2)
010
1X0
010
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1010;
char A[N][N], B[N][N];
struct node {
    int t, x, y;
    bool operator < (const node &p) const{
        return t < p.t;
    }
} leave[N];
int n, m, k, f;
int dir[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};

void solve() {
    for(int x = 0; x < n; x++) {
        for(int y = 0; y < m; y++) {
            int awake = 0;
            for(int i = 0; i < 8; i++) {
                int nx = x + dir[i][0];
                int ny = y + dir[i][1];
                if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                if(A[nx][ny] == '1') awake++;
            }
            B[x][y] = A[x][y];
            if(A[x][y] == '1') {
                if(awake < 2) B[x][y] = '0';
                else if(awake > 3) B[x][y] = '0';
                else B[x][y] = '1';
            }
            else if(A[x][y] == '0') {
                if(awake == 3) B[x][y] = '1';
            }
        }
    }
    for(int x = 0; x < n; x++) {
        for(int y = 0; y < m; y++)
            A[x][y] = B[x][y];
    }
}

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d%d%d", &n, &m, &f, &k);
        for(int i = 0; i < n; i++)
            scanf("%s", A[i]);
        for(int i = 0; i < k; i++) {
            scanf("%d%d%d", &leave[i].t, &leave[i].x, &leave[i].y);
            --leave[i].x; --leave[i].y;
        }
        sort(leave, leave + k);
        for(int i = 1, j = 0; i <= f; i++) {
            solve();
            while(j < k && leave[j].t == i) {
                A[leave[j].x][leave[j].y] =  'X';
                ++j;
            }
        }
        for(int i = 0; i < n; i++)
            printf("%s\n", A[i]);
    }
    return 0;
}