Nông dân John có \(N\) con bò (\(1 \leq N \leq 10^5\)) và chúng rất thích đi lại quanh nông trường của anh ấy.

Hàng rào của John bao gồm \(P\) cọc (\(4 \leq P \leq 2 \times 10^5\), \(P\) là số chẵn), với mỗi cọc là một điểm phân biệt trên trục tọa độ hai chiều (\(0 \leq x,y \leq 1000\)) được nối với các cọc kề nó bằng đường thẳng song song với trục tung hoặc trục hoành. Vậy nên toàn bộ nông trường tạo thành một đa giác khép kín bao quanh cánh đồng. Đường biên của hàng rào phải đáp ứng những điều kiện như sau: các đoạn của hàng rào chỉ có thể giao nhau ở các đầu mút (chính là các cây cọc), mỗi cây cọc chỉ có thể là đầu mút của hai đoạn hàng rào và các đoạn phải vuông góc với nhau.

Mỗi con bò có một điểm bắt đầu và điểm kết thúc chuyến đi khác nhau dọc theo hàng rào (có thể ở các cây cọc, có thể không). Chúng đi dạo dọc theo hàng rào mỗi ngày từ điểm bắt đầu đến điểm kết thúc. Có hai tuyến đường những con bò có thể đi nếu hàng rào khép kín. Tuy nhiên do có phần lười biếng, chúng sẽ luôn chọn đi con đường ngắn hơn (nếu hai con đường có độ dài bằng nhau, chúng có thể chọn 1 trong hai tuyến đường).

Hãy giúp nông dân John tìm ra khoảng cách mỗi con bò đi mỗi ngày.

Input:

• Dòng đầu tiên chứa \(N\) và \(P\).
• \(P\) dòng tiếp theo, mỗi dòng chứa hai số nguyên đại diện cho vị trí của các cọc hàng rào theo thứ tự theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ.
• \(N\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(x_1\), \(y_1\), \(x_2\), \(y_2\) đại diện cho vị trí bắt đầu \((x_1, y_1)\) và vị trí kết thúc \((x_2, y_2)\) của một con bò.

Output:

• In ra \(N\) số nguyên trên mỗi dòng, mỗi số là khoảng cách mà mỗi con bò đi.

Scoring:

• Subtask 1: \(0 \leq x, y \leq 100\) và \(N \leq 100\)
• Subtask 2: Không có ràng buộc gì thêm.

5 4
0 0
2 0
2 2
0 2
0 0 0 2
0 2 1 0
2 1 0 2
1 0 1 2
1 2 1 0

2
3
3
4
4