腐蝕和膨脹是數位影像處理中的兩個基本操作，分別用於縮小或擴展二值影像中的白色區域。

現在給定一個 $n \times n$ 的 01 矩陣 $A$ 和一個操作序列。操作序列中包含以下兩種操作：

• $0\ k$，將所有位置的值根據以下規則進行更新：如果某個位置的切比雪夫距離小於等於 $k$ 的範圍內存在一個值為 0 的位置，則該位置的值變為 0。形式化地，對於位置 $(x_a, y_a)$，如果存在位置 $(x_b, y_b)$ 使得 $\max(|x_a - x_b|, |y_a - y_b|) \le k$ 且 $A(x_b, y_b) = 0$，則更新 $A(x_a, y_a) = 0$。
• $1\ k$，將所有位置的值根據以下規則進行更新：如果某個位置的切比雪夫距離小於等於 $k$ 的範圍內存在一個值為 1 的位置，則該位置的值變為 1。形式化地，對於位置 $(x_a, y_a)$，如果存在位置 $(x_b, y_b)$ 使得 $\max(|x_a - x_b|, |y_a - y_b|) \le k$ 且 $A(x_b, y_b) = 1$，則更新 $A(x_a, y_a) = 1$。

注意：每次操作的所有更改是同時進行的。

你需要根據操作序列對矩陣 $A$ 進行一系列操作，並輸出最後一個操作完成後的矩陣。

輸入格式

每個測試檔案包含多組測試資料。第一行包含測試資料的組數 $T$ ($1 \le T \le 100$)。每組測試資料的格式如下：

第一行包含兩個整數 $n$ 和 $q$ ($1 \le n \le 500, 1 \le q \le 10^6$)，分別表示方陣 $A$ 的邊長和操作數量。 接下來 $n$ 行，第 $i$ 行包含一個長度為 $n$ 的 01 字串，表示矩陣 $A$ 的第 $i$ 行。 接下來 $q$ 行，每行包含兩個整數 $op, k$ ($op \in \{0, 1\}, 1 \le k \le n$)，表示一個操作。

在每個測試檔案內，保證所有測試資料的 $n$ 之和不超過 500，保證所有測試資料的 $q$ 之和不超過 $10^6$。

輸出格式

對於每組資料，輸出 $n$ 行，第 $i$ 行包含一個長度為 $n$ 的 01 字串，表示最後一個操作完成後的矩陣的第 $i$ 行。

範例

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