Последняя разработка компании R2 в сфере 2D игр — это новый революционный алгоритм поиска кратчайшего пути в лабиринте 2 × n.
Представьте лабиринт, который выглядит как прямоугольник 2 × n, разделенный на единичные квадраты. Каждый единичный квадрат — это либо свободная клетка, либо препятствие. За единицу времени некто может переместиться из свободной клетки лабиринта в любую соседнюю по стороне свободную клетку. Задача о кратчайшем пути формулируется следующим образом. Заданы две свободные клетки лабиринта, нужно определить, какое наименьшее время потребуется, чтобы дойти от одной до другой.
К сожалению, разработанный алгоритм хорошо работает только для одного запроса на поиск кратчайшего пути, на практике же таких запросов возникает достаточно много. Вам, как главному программисту R2, поручено оптимизировать алгоритм поиска кратчайшего пути. Напишите программу, которая эффективно будет отвечать на запросы поиска кратчайшего пути в лабиринте 2 × n.
Выходные данные
Выведите m строк. В i-й строке выведите ответ на i-й запрос — величину кратчайшего пути, или -1, если из первой клетки запроса нельзя дойти до второй.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 7
.X..
...X
5 1
1 3
7 7
1 4
6 1
4 7
5 7
|
1
4
0
5
2
2
2
|
|
2
|
10 3
X...X..X..
..X...X..X
11 7
7 18
18 10
|
9
-1
3
|