Sơn Cọc Hàng Rào

Farmer John có $N$ con bò ($1\le N\le {10}^5$) hàng ngày đi dạo quanh hàng rào bao quanh đồng cỏ. Hàng rào gồm $P$ cọc ($4\le P\le 2\times {10}^5$, $P$ chẵn) tại các tọa độ 2D phân biệt. Các cọc nối với nhau bằng đoạn thẳng ngang hoặc dọc, tạo thành đa giác kín vuông góc.

Mỗi con bò đi từ vị trí bắt đầu đến vị trí kết thúc trên hàng rào theo hướng ngắn hơn. Một con bò chạm vào cọc nếu nó đi ngang qua cọc đó, hoặc cọc đó là điểm bắt đầu/kết thúc của nó.

Hãy đếm số lần mỗi cọc bị chạm.

Dữ liệu vào

• Dòng 1: Hai số nguyên $N$ và $P$
• $P$ dòng tiếp: Hai số nguyên $x$, $y$ -- tọa độ mỗi cọc (không nhất thiết theo thứ tự quanh hàng rào)
• $N$ dòng tiếp: Bốn số nguyên $x_1$, $y_1$, $x_2$, $y_2$ -- vị trí bắt đầu và kết thúc

Dữ liệu ra

• $P$ số nguyên, số thứ $i$ là số lần cọc thứ $i$ (theo thứ tự đầu vào) bị chạm.

Ràng buộc

• $1\le N\le {10}^5$
• $4\le P\le 2\times {10}^5$, $P$ chẵn
• $0\le x,y\le {10}^9$
• Giới hạn thời gian: 3s, bộ nhớ: 512MB
• Test 4-6: $N,P\le 1000$
• Test 7-9: $0\le x,y\le 1000$

Ví dụ