Một khu cắm trại được biểu diễn dưới dạng một lưới, trong đó mỗi ô có thể chứa một vị trí cắm trại đã được đặt trước hoặc còn trống. Khoảng cách giữa hai ô \((x_1, y_1)\) và \((x_2, y_2)\) là khoảng cách Manhattan \(|x_1 - x_2| + |y_1 - y_2|\).

Nhiệm vụ của bạn là tìm khoảng cách từ mỗi vị trí cắm trại còn trống đến vị trí cắm trại đã được đặt trước gần nhất.

Input

Dòng đầu tiên gồm hai số nguyên \(n\) và \(m\): số lượng vị trí cắm trại đã được đặt trước và còn trống.

\(n\) dòng tiếp theo mô tả vị trí của các vị trí cắm trại đã được đặt trước. Mỗi dòng gồm hai số nguyên \(x\) và \(y\).

\(m\) dòng tiếp theo mô tả vị trí của các vị trí cắm trại còn trống. Mỗi dòng gồm hai số nguyên \(x\) và \(y\).

Bạn có thể giả sử rằng mỗi ô chứa nhiều nhất một vị trí cắm trại.

Output

In ra \(m\) số nguyên: khoảng cách từ mỗi vị trí cắm trại còn trống đến vị trí cắm trại đã được đặt trước gần nhất, theo thứ tự trong input.

Constraints

• \(1 \le n, m \le 10^5\)

• \(1 \le x, y \le 10^6\)

Example

4 2
1 1
5 2
2 6
4 7
1 3
7 5

2 5

Explanation

Hình sau minh họa bản đồ của khu cắm trại:

Khoảng cách từ vị trí cắm trại còn trống thứ nhất (ở bên trái) đến vị trí cắm trại đã được đặt trước gần nhất là \(2\), và khoảng cách từ vị trí cắm trại còn trống thứ hai (ở bên phải) đến vị trí cắm trại đã được đặt trước gần nhất là \(5\).