Anh nông dân John có \(N\) chú bò (\(1 \leq N \leq 10^5\)) và chúng rất thích tản bộ quanh hàng rào của trang trại. Tuy nhiên, những chú bò của John hơi hậu đậu nên mỗi khi chúng đi qua một hàng rào thì sẽ làm xước hàng rào đó, khiên John phải đi sơn lại hàng rào mỗi ngày.

Hàng rào của John bao gồm \(P\) cây cọc (\(4 \leq P \leq 2 \times 10^5\), \(P\) là số chẵn), với mỗi cây 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 10^9)\) được nối với các cây 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ộ hàng rào tạo thành một đa giác khép kín bao quanh cánh đồng. Các cạnh 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 tại điểm giao.

Mỗi chú 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 chú bò có thể đi, vì hàng rào tạo thành một vòng tròn khép kín. Tuy nhiên do có phần lười biếng, chúng sẽ luôn chọn đi đường ngắn hơn. Lưu ý rằng với mỗi chú bò không bao giờ xảy ra trường hợp mà cả hai tuyến đường có độ dài bằng nhau.

Một chú bò sẽ làm xước cây cọc nếu nó đi qua cây cọc đó hoặc cây cọc là điểm bắt đầu hoặc kết thúc của chuyến đi. Nhiệm vụ của bạn là giúp nông dân John tính số lần mỗi cây cọc bị làm xước để tính toán xem nên sơn lại cây cọc nào tiếp theo.

Dữ liệu đảm bảo những cây cọc luôn được nối thành một hàng rào.

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 \(x\) và \(y\)
• \(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 điểm bắt đầu và điểm kết thúc ưa thích của mỗi chú bò.

Output:

• In ra \(P\) dòng, mỗi dòng chứa một số nguyên đại diện cho số lần bị quệt phải của mỗi cây cọc.

Scoring:

• Subtask 1: \(N, P \leq 1000\)
• Subtask 2: Tất cả các vị trí thỏa mãn \(0 \leq x, y \leq 1000\).
• Subtask 3: Không có ràng buộc gì thêm

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

1
2
2
1

2 8
1 1
1 2
0 2
0 3
0 0
0 1
2 3
2 0
1 1 2 1
1 0 1 3

1
0
0
0
1
1
1
2

1 12
0 0
2 0
2 1
1 1
1 2
3 2
3 3
1 3
1 4
2 4
2 5
0 5
2 2 0 2

1
1
1
1
1
0
0
0
0
0
0
0