Một vị vua đang trên đường trở về vương quốc của mình thì chợt nhận ra mình đã lạc vào một bàn cờ có chiều dài ~10^9~ và chiều rộng ~10^9~. Bàn cờ được đánh số từ ~1~ đến ~10^9~ theo từng hàng từ trên xuống và theo từng cột từ trái sang. Vị trí tại dòng ~i~ và cột ~j~ được định nghĩa là tọa độ ~(i, j)~.

Nhà vua được biết chỉ một số ô trên bàn cờ là đi được (gọi là ô cho phép). Những ô này được xác định bằng ~n~ đoạn con. Mỗi đoạn con gồm ba số nguyên ~r_i, a_i, b_i~ ~(a_i \le b_i)~ cho biết các ô thuộc các cột liên tiếp từ ~a_i~ đến ~b_i~ tại dòng ~r_i~ là ô cho phép. Nhà vua đang đứng ở ô ~(x_0, y_0)~ và rất gấp rút để trở về. Bạn hãy giúp nhà vua tìm cách đi với số bước ít nhất để tới ô ~(x_1, y_1)~. Biết nhà vua chỉ có thể di chuyển trong các ô cho phép.

Mỗi bước, nhà vua có thể di chuyển tới một ô cho phép bất kì có ít nhất một điểm chung với ô đang đứng (tức là một trong 8 ô xung quanh). Dữ liệu đảm bảo rằng điểm đầu và điểm cuối của nhà vua nằm trong bàn cờ, là các ô cho phép và không trùng nhau. Ngoài ra, tổng số ô cho phép trong bộ dữ liệu không vượt quá ~10^5~.

Dữ liệu

• Dòng thứ nhất chứa bốn số tự nhiên ~x_0, y_0, x_1, y_1~ ~(1 \le x_0, y_0, x_1, y_1 \le 10^9)~ — vị trí ban đầu và vị trí kết thúc của nhà vua.

• Dòng thứ hai chứa duy nhất một số ~n~ ~(1 \le n \le 10^5)~ — số đoạn con.

• ~n~ dòng tiếp theo, mỗi dòng chứa ba số ~r_i, a_i, b_i~ ~(1 \le r_i, a_i, b_i \le 10^9,\ a_i \le b_i)~ — các cột từ ~a_i~ đến ~b_i~ trên dòng ~r_i~ có thể đi được.

Kết quả

Nếu như không có đường đi, in ra ~-1~. Ngược lại, in ra số bước đi ít nhất để nhà vua ở vị trí bắt đầu có thể tới được vị trí kết thúc.

Ví dụ

Sample Input 1

5 7 6 11
3
5 3 8
6 7 11
5 2 5

Sample Output 1

4

Sample Input 2

3 4 3 10
3
3 1 4
4 5 9
3 10 10

Sample Output 2

6

Sample Input 3

1 1 2 10
2
1 1 3
2 6 10

Sample Output 3

-1