E. Лабиринт 2D
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Последняя разработка компании R2 в сфере 2D игр — это новый революционный алгоритм поиска кратчайшего пути в лабиринте 2 × n.

Представьте лабиринт, который выглядит как прямоугольник 2 × n, разделенный на единичные квадраты. Каждый единичный квадрат — это либо свободная клетка, либо препятствие. За единицу времени некто может переместиться из свободной клетки лабиринта в любую соседнюю по стороне свободную клетку. Задача о кратчайшем пути формулируется следующим образом. Заданы две свободные клетки лабиринта, нужно определить, какое наименьшее время потребуется, чтобы дойти от одной до другой.

К сожалению, разработанный алгоритм хорошо работает только для одного запроса на поиск кратчайшего пути, на практике же таких запросов возникает достаточно много. Вам, как главному программисту R2, поручено оптимизировать алгоритм поиска кратчайшего пути. Напишите программу, которая эффективно будет отвечать на запросы поиска кратчайшего пути в лабиринте 2 × n.

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

В первой строке записаны два целых числа n и m (1 ≤ n ≤ 2·105; 1 ≤ m ≤ 2·105) — ширина лабиринта и количество запросов соответственно. В следующих двух строках задан лабиринт. В каждой строке записано по n символов, каждый из которых равен: либо «.» (свободная клетка), либо «X» (препятствие).

В каждой из следующих m строк записано по два целых числа vi и ui (1 ≤ vi, ui ≤ 2n) — описание i-го запроса. Числа vi, ui обозначают, что нужно вывести величину кратчайшего пути из клетки лабиринта с номером vi в клетку с номером ui. Считается, что клетки первой строки лабиринта нумеруются от 1 до n слева направо, а клетки второй строки от n + 1 до 2n слева направо. Гарантируется, что обе заданные клетки свободные.

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

Выведите m строк. В i-й строке выведите ответ на i-й запрос — величину кратчайшего пути, или -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
Входные данные
10 3
X...X..X..
..X...X..X
11 7
7 18
18 10
Выходные данные
9
-1
3