В королевстве клетки огромной карты задаются целочисленными координатами. Королевский гонец должен как можно быстрее доставить срочную весть из одной клетки в другую.

Гонец находится в клетке ((x_0, y_0)) и должен попасть в клетку ((x_1, y_1)).

За один ход гонец может перейти из клетки ((x, y)) в любую из восьми соседних клеток:

• ((x-1, y-1))
• ((x-1, y))
• ((x-1, y+1))
• ((x, y-1))
• ((x, y+1))
• ((x+1, y-1))
• ((x+1, y))
• ((x+1, y+1))

Однако двигаться можно только по тем клеткам, через которые проложены королевские дороги. Все остальные клетки непроходимы.

Дороги описываются следующим образом: для некоторых строк карты известно, что во всех клетках с координатами ((r_i, c)), где (a_i \le c \le b_i), проходит дорога.

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

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

В первой строке записаны четыре целых числа (x_0, y_0, x_1, y_1) — координаты начальной и конечной клеток.

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

В следующих (n) строках записаны по три целых числа (r_i, a_i, b_i), означающие, что во всех клетках ((r_i, c)), где (a_i \le c \le b_i), проходит дорога.

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

Выведите одно целое число — минимальное количество ходов, необходимое гонцу, чтобы добраться до цели.

Если попасть в конечную клетку невозможно, выведите -1.

Ограничения

• (-10^9 \le x_0, y_0, x_1, y_1 \le 10^9)
• (1 \le n \le 10^5)
• (-10^9 \le r_i, a_i, b_i \le 10^9)
• (a_i \le b_i)
• Суммарное количество клеток, для которых задано наличие дороги, не превосходит (10^5)

Примеры

Пример 1

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

1 1 3 3
3
1 1 2
2 2 3
3 2 3

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

2

Пример 2

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

1 1 4 5
4
1 1 3
2 2 4
3 3 5
4 4 5

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

4

Пример 3

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

1 1 3 3
2
1 1 1
3 3 3

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

-1