Локи и Шахматы

Однажды Тор заставил Локи играть в шахматы. Но шахматы в Асгарде не совсем обычные. Дело в том, что шахматная доска представляет собой таблицу из $n$ строк и $m$ столбцов. Каждая ячейка таблицы может либо иметь пешку, либо не иметь. Ячейка, которая не имеет пешки, называется свободной, а ячейка, которая имеет пешку, называется занятой.

Локи необходимо сделать $q$ действий. Каждое действие заключается в том, что Тор дает Локи координаты ячейки и направление: 1 --- вверх, 2 --- вправо, 3 --- вниз и 4 --- влево. Если выбранная Тором ячейка свободна, то Локи ничего не должен делать, в противном случае он должен подвинуть пешку в указанном направлении.

Обратите внимание, что двигаются также все пешки, которые выбранная пешка толкает при движении в указанном направлении. Если пешка достигает границы доски, то дальше она не двигается.

В первой строке входных данных содержатся три числа $n$, $m$ и $q$ $(1 \leq n, m \leq 1000, 1 \leq q \leq 10^6)$. Далее в $n$ строках содержится строка из $m$ символов. $c\_{i, j}$ --- $j$-й символ в $i$-й строке. Если $c\_{i, j}$ равно единице, то в данной ячейке стоит пешка, в противном случае ячейка является свободной. В последних $q$ строках содержатся три целых числа $x$, $y$ и $dir$ --- строка и столбец запроса и направление $(0 \leq x \leq n - 1, 0 \leq y \leq m - 1, 1 \leq dir \leq 4)$. Строки нумеруются сверху вниз от $0$ до $n - 1$, столбцы нумеруются слева направо от $0$ до $m - 1$.

В $n$ строках выходных данных выведите $m$ символов. В $i$-й строке $j$-й символ должен быть равен единице, если после выполнения всех команд от Тора в текущей ячейке находится пешка; в противном случае, если пешки в текущей ячейке нет, выведите 0.