Черный король находится на шахматном поле, состоящем из 109 строк и 109 столбцов. Будем считать, что строки этого шахматного поля пронумерованы целыми числами от 1 до 109 сверху вниз. Аналогично, столбцы пронумерованы целыми числами от 1 до 109 слева направо. Клетку поля, находящуюся в i-ой строке и j-ом столбце, будем обозначать (i, j).
Известно, что некоторые клетки заданного шахматного поля являются разрешенными. Все разрешенные клетки шахматного поля заданы в виде n отрезков. Каждый отрезок описывается тремя целыми числами ri, ai, bi (ai ≤ bi), обозначающими, что в ri-ой строке клетки с номерами столбцов с ai по bi включительно являются разрешенными.
Ваша задача — найти минимальное количество ходов, за которое шахматный король сможет добраться из клетки поля (x0, y0) в клетку поля (x1, y1), двигаясь только по разрешенным клеткам поля. Другими словами, во время своего пути шахматный король может находиться только лишь на разрешенных клетках поля.
Напомним, что шахматный король за один ход может переместиться в любую из (в общем случае восьми) соседних клеток. Две клетки шахматного поля считаются соседними, если они имеют хотя бы одну общую точку.
Выходные данные
Если пути между начальной и конечной позициями, состоящего из разрешенных клеток, не существует, выведите -1.
В противном случае выведите единственное целое число — минимальное количество ходов, за которое король сможет добраться из начальной позиции в конечную.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 7 6 11
3
5 3 8
6 7 11
5 2 5
|
4
|
|
2
|
3 4 3 10
3
3 1 4
4 5 9
3 10 10
|
6
|
|
3
|
1 1 2 10
2
1 1 3
2 6 10
|
-1
|