Erosion and dilation are two fundamental operations in digital image processing, used to shrink or expand the white regions in a binary image, respectively.

Given an $n \times n$ binary matrix $A$ and a sequence of operations, the sequence contains the following two types of operations:

• $0\ k$: Update the values of all positions according to the following rule: if there exists a position with value $0$ within a Chebyshev distance of $k$ from a given position, then the value at that position becomes $0$. Formally, for a position $(x_a, y_a)$, if there exists a position $(x_b, y_b)$ such that $\max(|x_a - x_b|, |y_a - y_b|) \le k$ and $A(x_b, y_b) = 0$, then update $A(x_a, y_a) = 0$.
• $1\ k$: Update the values of all positions according to the following rule: if there exists a position with value $1$ within a Chebyshev distance of $k$ from a given position, then the value at that position becomes $1$. Formally, for a position $(x_a, y_a)$, if there exists a position $(x_b, y_b)$ such that $\max(|x_a - x_b|, |y_a - y_b|) \le k$ and $A(x_b, y_b) = 1$, then update $A(x_a, y_a) = 1$.

Note: All changes for each operation are performed simultaneously.

You need to perform the sequence of operations on matrix $A$ and output the matrix after the final operation is completed.

Input

Each test file contains multiple test cases. The first line contains the number of test cases $T$ ($1 \le T \le 100$). The format for each test case is as follows:

The first line contains two integers $n$ and $q$ ($1 \le n \le 500, 1 \le q \le 10^6$), representing the side length of the square matrix $A$ and the number of operations, respectively.

The next $n$ lines each contain a binary string of length $n$, representing the $i$-th row of matrix $A$.

The next $q$ lines each contain two integers $op, k$ ($op \in \{0, 1\}, 1 \le k \le n$), representing an operation.

Within each test file, it is guaranteed that the sum of $n$ over all test cases does not exceed $500$, and the sum of $q$ over all test cases does not exceed $10^6$.

Output

For each test case, output $n$ lines, where the $i$-th line contains a binary string of length $n$, representing the $i$-th row of the matrix after the final operation is completed.

Examples

Input 1

2
5 3
00001
00000
00000
11000
11000
0 1
1 3
0 1
6 2
000000
000001
000011
000111
001111
011111
1 2
0 2

Output 1

00000
00000
11100
11100
11100
000011
000011
000011
000111
111111
111111