Đi Dọc Hàng Rào

Hàng rào của Farmer John 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 $(x,y)$ với $0\le x,y\le 1000$. Các cọc được nối bởi các đoạn thẳng ngang hoặc dọc tạo thành một đa giác kín vuông góc (rectilinear polygon). Các đoạn hàng rào chỉ giao nhau tại điểm đầu mút.

• $N$ con bò ($1\le N\le {10}^5$) mỗi con đi dạo dọc hàng rào từ một vị trí bắt đầu đến một vị trí kết thúc. Vì hàng rào là vòng kín, có hai hướng đi. Mỗi con bò sẽ đi theo hướng ngắn hơn (nếu bằng nhau, bò có thể chọn hướng bất kỳ).

Hãy tính quãng đường mỗi con bò đi.

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 (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 của mỗi con bò

Dữ liệu ra

• $N$ dòng, mỗi dòng một số nguyên -- quãng đường mỗi con bò đi.

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 1000$
• Test 2-6: $0\le x,y\le 100$ và $N\le 100$

Ví dụ