Эрозия и дилатация — две базовые операции в цифровой обработке изображений, используемые для уменьшения или расширения белых областей на бинарном изображении соответственно.

Дана матрица $A$ размера $n \times n$, состоящая из $0$ и $1$, и последовательность операций. Последовательность содержит два типа операций:

• $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$-я из которых содержит строку из $0$ и $1$ длиной $n$, представляющую $i$-ю строку матрицы $A$.

Далее следуют $q$ строк, каждая из которых содержит два целых числа $op, k$ ($op \in \{0, 1\}, 1 \le k \le n$), обозначающие операцию.

Гарантируется, что сумма $n$ по всем наборам данных в одном файле не превышает $500$, а сумма $q$ не превышает $10^6$.

Выходные данные

Для каждого набора данных выведите $n$ строк, $i$-я из которых содержит строку из $0$ и $1$ длиной $n$, представляющую $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