Вы нашли карту лабиринта довольно странной формы. Карта представляет собой сетку, разделенную на \(n\) строк и \(n\) столбцов. Строки карты пронумерованы от \(1\) до \(n\) снизу вверх. Столбцы карты пронумерованы от \(1\) до \(n\) слева направо.
В лабиринте есть \(n\) слоев. Первый слой — это левый нижний угол (ячейка \((1, 1)\)). Второй слой состоит из всех ячеек, которые внутри сетки и смежны с первым слоем по стороне или по углу. Третий слой состоит из всех ячеек, которые внутри сетки и смежны со вторым слоем по стороне или по углу.
Лабиринт из \(5\) слоев, например, выглядит следующим образом:
Слои отделены друг от друга стенами. Однако, в этих стенах есть двери.
В каждом слое (кроме слоя \(n\)) есть ровно две двери в следующий слой. Одна дверь размещена на верхней стене слоя, а другая дверь размещена на правой стене слоя. Для каждого слоя от \(1\) до \(n-1\) вам даны позиции этих двух дверей. Через эти двери можно ходить в обоих направлениях: либо из слоя \(i\) в слой \(i+1\), либо из слоя \(i+1\) в слой \(i\).
Если вы находитесь в какой-либо ячейке лабиринта, то вы можете переместиться в соседнюю по стороне клетку, если путь не преграждает стена (то есть нельзя переместиться в клетку в другом слое, если между клетками нет двери).
Вам нужно обработать \(m\) запросов следующего вида: какое минимальное количество ходов необходимо сделать, чтобы дойти из клетки \((x_1, y_1)\) в клетку \((x_2, y_2)\)?
Выходные данные
На каждый запрос выведите одно целое число — минимальное количество ходов, которое необходимо сделать, чтобы дойти из клетки \((x_1, y_1)\) в клетку \((x_2, y_2)\).
Примечание
Здесь изображена карта лабиринта из второго примера. Двери отмечены красным.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1 1 1 1
10
1 1 1 1
1 1 1 2
1 1 2 1
1 1 2 2
1 2 1 2
1 2 2 1
1 2 2 2
2 1 2 1
2 1 2 2
2 2 2 2
|
0
1
1
2
0
2
1
0
1
0
|
|
2
|
4
1 1 1 1
2 1 2 2
3 2 1 3
5
2 4 4 3
4 4 3 3
1 2 3 3
2 2 4 4
1 4 2 3
|
3
4
3
6
2
|