В королевстве есть бесконечная клетчатая карта. Клетка с координатами (r, c) обозначает участок земли в строке r и столбце c.

Королевский гонец должен как можно быстрее доставить срочные вести из клетки (x0, y0) в клетку (x1, y1). За один ход он может перейти из текущей клетки в любую соседнюю по стороне или по углу, то есть в одну из 8 клеток вокруг.

Однако передвигаться разрешено не везде. Известно n отрезков дорог: для каждого из них задан номер строки ri и диапазон столбцов от ai до bi. Это означает, что во всех клетках (ri, c), где ai <= c <= bi, проложена дорога, и гонец может находиться только на таких клетках.

Требуется определить минимальное число ходов, за которое гонец сможет добраться до места назначения, если он может перемещаться только по клеткам дорог. Если это невозможно, выведите -1.

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

В первой строке записаны четыре целых числа x0, y0, x1, y1 — координаты начальной и конечной клеток.

Во второй строке записано целое число n — количество отрезков дорог.

В следующих n строках записаны по три целых числа ri, ai, bi, описывающих очередной отрезок дороги. Все клетки (ri, c) для ai <= c <= bi разрешены для передвижения.

Гарантируется, что начальная и конечная клетки принадлежат разрешённым клеткам.

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

Выведите одно целое число — минимальное количество ходов, необходимых гонцу, чтобы добраться из начальной клетки в конечную, либо -1, если путь не существует.

Ограничения

• 1 <= n <= 10^5
• 1 <= x0, y0, x1, y1 <= 10^9
• 1 <= ri, ai, bi <= 10^9
• ai <= bi
• Суммарное количество разрешённых клеток не превышает 10^5
• Ввод осуществляется через стандартный ввод
• Вывод осуществляется через стандартный вывод

Примеры

Пример 1

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

999999999 999999999 1000000000 1000000000
2
999999999 999999999 999999999
1000000000 1000000000 1000000000

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

1

Пример 2

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

867552991 41378072 867552992 41378073
2
867552991 41378072 41378073
867552992 41378072 41378073

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

1