| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 7 초 | 1024 MB | 6 | 5 | 3 | 75.000% |
Однажды Тор заставил Локи играть в шахматы. Но шахматы в Асгарде не совсем обычные. Дело в том, что шахматная доска представляет собой таблицу из $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.
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