Андрею на день рождения подарили две очень интересные вещи: лабиринт и лазер. Лабиринт представляет собой матрицу из \(n\) строк и \(m\) столбцов. В матрице могут встречаться пустые клетки ., стены #, а также два типа зеркал: / и \.
После этого Андрей начинает запускать лазер из различных точек лабиринта. Когда луч оказывается в некоторой клетке, происходит следующее:
- если луч находится в пустой клетке, то он продолжает двигаться в том же направлении;
- если луч находится в клетке с зеркалом
/, то направление меняется: вверх → вправо; вправо → вверх; вниз → влево; влево → вниз;
- если луч находится в клетке с зеркалом
\, то направление меняется: вверх → влево; влево → вверх; вниз → вправо; вправо → вниз.
После этого луч пытается перейти в соседнюю клетку в новом направлении. Если луч пытается выйти за границы лабиринта или перейти в клетку со стеной, его движение немедленно заканчивается.
Вам необходимо ответить на \(q\) запросов. В каждом запросе заданы клетка \((x,y)\) и начальное направление луча. Для каждого запроса требуется определить количество переходов между соседними клетками, которое совершит луч до остановки, либо вывести \(-1\), если луч будет двигаться бесконечно (попадёт в цикл).
Формат входных данных
В первой строке даны два целых числа \(n\) и \(m\) — количество строк и столбцов (\(1 \le n, m \le 500\)). В следующих \(n\) строках дано по \(m\) символов — описание матрицы (каждый символ — один из ., #, /, \). В следующей строке дано целое число \(q\) — количество запросов (\(1 \le q \le 10^5\)). В следующих \(q\) строках дано описание запросов вида \(x\ y\ dir\) (\(1 \le x \le n,\ 1 \le y \le m,\ dir \in \{left, right, up, down\}\)). Гарантируется, что клетка \((x,y)\) не является стеной.
Формат выходных данных
Для каждого запроса выведите одно целое число в отдельной строке: количество переходов между соседними клетками, либо \(-1\), если луч движется бесконечно. Обратите внимание, что если луч несколько раз посещает одну и ту же клетку, но с разными направлениями, то это считаются разными состояниями.
| № | Входные данные | Выходные данные |
|
1
|
3 3
/.\
...
\./
4
1 2 left
1 2 right
1 2 up
1 2 down
|
-1
-1
1
3
|
|
2
|
3 3
...
./.
#\/
5
1 1 down
2 3 left
2 3 right
2 3 down
2 1 right
|
2
6
1
5
3
|