腐食と膨張はデジタル画像処理における2つの基本的な操作であり、それぞれ二値画像内の白い領域を縮小または拡大するために使用されます。

$n \times n$ の 01 行列 $A$ と操作のシーケンスが与えられます。操作のシーケンスには以下の2種類の操作が含まれます。

• $0\ k$: すべての位置の値を以下のルールに従って更新します。ある位置のチェビシェフ距離が $k$ 以下の範囲内に値が $0$ である位置が存在する場合、その位置の値を $0$ に変更します。形式的には、位置 $(x_a, y_a)$ について、$\max(|x_a - x_b|, |y_a - y_b|) \le k$ かつ $A(x_b, y_b) = 0$ を満たす位置 $(x_b, y_b)$ が存在する場合、$A(x_a, y_a) = 0$ に更新します。
• $1\ k$: すべての位置の値を以下のルールに従って更新します。ある位置のチェビシェフ距離が $k$ 以下の範囲内に値が $1$ である位置が存在する場合、その位置の値を $1$ に変更します。形式的には、位置 $(x_a, y_a)$ について、$\max(|x_a - x_b|, |y_a - y_b|) \le k$ かつ $A(x_b, y_b) = 1$ を満たす位置 $(x_b, y_b)$ が存在する場合、$A(x_a, y_a) = 1$ に更新します。

注意：各操作におけるすべての変更は同時に行われます。

操作のシーケンスに従って行列 $A$ に対して一連の操作を行い、最後の操作が完了した後の行列を出力してください。

入力

各テストファイルには複数のテストケースが含まれます。最初の行にはテストケースの数 $T$ ($1 \le T \le 100$) が含まれます。各テストケースの形式は以下の通りです。

最初の行には2つの整数 $n$ と $q$ ($1 \le n \le 500, 1 \le q \le 10^6$) が含まれ、それぞれ正方行列 $A$ の一辺の長さと操作の回数を表します。

続く $n$ 行のうち、$i$ 行目には長さ $n$ の 01 文字列が含まれ、行列 $A$ の $i$ 行目を表します。

続く $q$ 行の各行には、2つの整数 $op, k$ ($op \in \{0, 1\}, 1 \le k \le n$) が含まれ、1つの操作を表します。

各テストファイルにおいて、すべてのテストケースの $n$ の総和は $500$ を超えず、$q$ の総和は $10^6$ を超えないことが保証されます。

出力

各データセットについて、$n$ 行を出力してください。$i$ 行目には、最後の操作が完了した後の行列の $i$ 行目を表す長さ $n$ の 01 文字列を出力してください。

入出力例

入力 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

出力 1

00000
00000
11100
11100
11100
000011
000011
000011
000111
111111
111111