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