There are n grid points in a 2-Dimension plane, and m blocks in the plane, now alibaba require you to calculate each pairofpoints’ distance. (the shortest one), notice the route you choose should only be the grid points(which means the route from point A to point B is just comprised by grid points), and points can go just up, down, left, right. The route between two points can not cross blocks but can along withblocks’ border.

       (we ensure points will not be inside any blocks, and blocks may overlap)

       There are several test cases end with EOF

Each case started with two integers n, m. then followed by n lines indicates point’s coordinates formatted as x y. then m lines x1 y1 x2 y2 followed indicates there are m blocks whose upper left corner is (x1,y1), lower right corner is (x2,y2)

(x1 < x2, y2 < y1)

(1<=n<=50)

(1<=m<=50)

(|x|, |y| <= 2*10^9)

(|x1|, |x2|, |y1|, |y2|<=2*10^9)

All inputs are integer.

       An n*n matrix, the unit of ith row and jth column filled with the distance between ith point and jth point (by the points’ order in input), if point i can’t reach point j, then just fill -1.

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

0 8 6
8 0 6
6 6 0