Erozja i dylatacja to dwie podstawowe operacje w cyfrowym przetwarzaniu obrazów, służące odpowiednio do zmniejszania lub powiększania białych obszarów na obrazach binarnych.

Dana jest macierz binarna $A$ o wymiarach $n \times n$ oraz sekwencja operacji. Sekwencja ta zawiera dwa rodzaje operacji:

• $0\ k$: zaktualizuj wartości we wszystkich pozycjach zgodnie z następującą regułą: jeśli w odległości Czebyszewa mniejszej lub równej $k$ od danej pozycji istnieje pozycja o wartości $0$, to wartość w tej pozycji zmienia się na $0$. Formalnie, dla pozycji $(x_a, y_a)$, jeśli istnieje pozycja $(x_b, y_b)$ taka, że $\max(|x_a - x_b|, |y_a - y_b|) \le k$ oraz $A(x_b, y_b) = 0$, to zaktualizuj $A(x_a, y_a) = 0$.
• $1\ k$: zaktualizuj wartości we wszystkich pozycjach zgodnie z następującą regułą: jeśli w odległości Czebyszewa mniejszej lub równej $k$ od danej pozycji istnieje pozycja o wartości $1$, to wartość w tej pozycji zmienia się na $1$. Formalnie, dla pozycji $(x_a, y_a)$, jeśli istnieje pozycja $(x_b, y_b)$ taka, że $\max(|x_a - x_b|, |y_a - y_b|) \le k$ oraz $A(x_b, y_b) = 1$, to zaktualizuj $A(x_a, y_a) = 1$.

Uwaga: wszystkie zmiany w ramach pojedynczej operacji zachodzą jednocześnie.

Należy wykonać sekwencję operacji na macierzy $A$ i wypisać macierz po zakończeniu wszystkich operacji.

Wejście

Każdy plik testowy zawiera wiele zestawów danych. Pierwsza linia zawiera liczbę zestawów danych $T$ ($1 \le T \le 100$). Format każdego zestawu danych jest następujący:

Pierwsza linia zawiera dwie liczby całkowite $n$ oraz $q$ ($1 \le n \le 500, 1 \le q \le 10^6$), oznaczające odpowiednio długość boku macierzy kwadratowej $A$ oraz liczbę operacji.

Następnie $n$ linii, z których $i$-ta zawiera ciąg binarny o długości $n$, reprezentujący $i$-ty wiersz macierzy $A$.

Następnie $q$ linii, z których każda zawiera dwie liczby całkowite $op, k$ ($op \in \{0, 1\}, 1 \le k \le n$), reprezentujące operację.

W każdym pliku testowym suma $n$ dla wszystkich zestawów danych nie przekracza $500$, a suma $q$ dla wszystkich zestawów danych nie przekracza $10^6$.

Wyjście

Dla każdego zestawu danych wypisz $n$ linii, z których $i$-ta zawiera ciąg binarny o długości $n$, reprezentujący $i$-ty wiersz macierzy po wykonaniu wszystkich operacji.

Przykład

Wejście 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

Wyjście 1

00000
00000
11100
11100
11100
000011
000011
000011
000111
111111
111111