C. Путь короля
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Черный король находится на шахматном поле, состоящем из 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