JOI-kun luyện tập trên một sân golf đặc biệt, được biểu diễn bằng mặt phẳng tọa độ. Có \(N\) chướng ngại vật. Chướng ngại vật thứ \(i\) là hình chữ nhật kín

Hai chướng ngại vật, kể cả biên, không giao nhau. Điểm bắt đầu là \((S,T)\) và điểm kết thúc là \((U,V)\); hai điểm khác nhau và không nằm trên chướng ngại vật hay biên của chúng.

Mỗi cú đánh có thể đưa bóng đi một khoảng tùy ý theo một trong bốn hướng song song với trục tọa độ. Quỹ đạo bóng không được chạm phần trong của chướng ngại vật, nhưng có thể đi trên biên hoặc dừng trên biên. Từ đó, bóng có thể đổi hướng bằng một cú đánh về phía không bị chướng ngại vật chắn.

Hãy tính số cú đánh ít nhất để đưa bóng từ điểm đầu đến điểm cuối.

Dữ liệu vào

• Dòng đầu chứa \(S,T,U,V\).
• Dòng thứ hai chứa \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(A_i,B_i,C_i,D_i\).

Dữ liệu ra

In số cú đánh ít nhất.

Ràng buộc

• \(1\le S,T,U,V\le1\,000\,000\,000\).
• \(1\le N\le100\,000\).
• \(1\le A_i<B_i\le1\,000\,000\,000\).
• \(1\le C_i<D_i\le1\,000\,000\,000\).
• \((S,T)\ne(U,V)\).
• Hai chướng ngại vật, kể cả biên, không giao nhau.
• Điểm đầu và điểm cuối không nằm trên chướng ngại vật hay biên của chúng.

Phân nhóm

1. \(10\) điểm: \(S,T,U,V\le1\,000\), \(N\le1\,000\), \(B_i,D_i\le1\,000\) với mọi \(i\)
2. \(20\) điểm: \(N\le1\,000\)
3. \(70\) điểm: Không có ràng buộc bổ sung

Ví dụ

3 5 8 6
1
5 6 2 8

3

1 1 1 10
3
5 6 2 8
1 2 2 3
8 10 3 5

1

20 68 85 74
5
30 70 14 100
5 24 15 67
75 86 75 79
75 90 19 62
93 98 26 58

4

Nguồn

JOI 2016/2017 Open Contest.