Локи и Шахматы
ограничение по времени на тест
7 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

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

В первой строке входных данных содержатся три числа n, m и q (1 ≤ n, m ≤ 1000, 1 ≤ q ≤ 106). Далее в n строках содержится строка из m символов. ci, j — j-й символ в i-й строке. Если ci, j равно единице, то в данной ячейке стоит пешка, в противном случае ячейка является свободной. В последних q строках содержатся три целых числа x, y и dir — строка и столбец запроса и направление (0 ≤ x ≤ n - 1, 0 ≤ y ≤ m - 1, 1 ≤ dir ≤ 4). Строки нумеруются сверху вниз от 0 до n - 1, столбцы нумеруются слева направо от 0 до m - 1.

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

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

Пример

Входные данные
3 3 6
000
010
000
1 1 2
1 1 2
1 2 3
2 2 2
2 2 4
2 1 1
Выходные данные
000
010
000