# F006B. Manhattan distance P64555

Statement html

The Manhattan distance between two points with integer coordinates in a plane is described as the number of unit steps towards up, down, left or right that you must do to go from a point to the other one. (It has this name because is the number of blocks that is necessary to walk in a squared neighborhood to go from a junction to another one.)

For instance, consider the point (1, -2) of the figure on the right (the biggest). The nearest point is (2, -3), that it is in a distance 2. The farthest point is (-2, 1), that it is in a distance 6. Except that (2,2), the rest of points are in a distance 4.

Your task is to write a program that, given a point (x, y) and n points (x1, y1), …, (xn, yn), prints these points sorted depending on their Manhattan distance to (x, y).

(205, 230)(-85, -140) (-80, 0)(1, 0)200 (115, 5)x (0, -140)(0, 1)200 (5, 55)y

(-80, -2)(0, 1)4 (-60, -2)(0, 1)4 (-40, -2)(0, 1)4 (-20, -2)(0, 1)4 (20, -2)(0, 1)4 (40, -2)(0, 1)4 (60, -2)(0, 1)4 (80, -2)(0, 1)4 (100, -2)(0, 1)4

(-2, -140)(1, 0)4 (-2, -120)(1, 0)4 (-2, -100)(1, 0)4 (-2, -80)(1, 0)4 (-2, -60)(1, 0)4 (-2, -40)(1, 0)4 (-2, -20)(1, 0)4 (-2, 20)(1, 0)4 (-2, 40)(1, 0)4

(20, -40)6 (25, -43)(1, -2) (40, -60)4 (45, -63)(2, -3) (20, -120)4 (25, -123)(1, -6) (100, -40)4 (105, -43)(5, -2) (-60, -40)4 (-55, -43)(-3, -2) (-40, -20)4 (-35, -23)(-2, -1) (-40, 20)4 (-53, 25)(-2, 1) (40, 40)4 (45, 37)(2, 2) (60, 0)4 (47, 5)(3, 0)

(20, -45)(0, -1)4 (20, -51)(0, -1)4 (20, -57)(0, -1)3 (20, -60)(1, 0)3 (25, -60)(1, 0)4 (31, -60)(1, 0)4

(20, 20)(0, -1)4 (20, 14)(0, -1)4 (20, 8)(0, -1)4 (20, 2)(0, -1)4 (20, -4)(0, -1)4 (20, -10)(0, -1)4 (20, -16)(0, -1)4 (20, -22)(0, -1)4 (20, -28)(0, -1)4 (20, -34)(0, -1)2

(20, 20)(-1, 0)4 (14, 20)(-1, 0)4 (8, 20)(-1, 0)4 (2, 20)(-1, 0)4 (-4, 20)(-1, 0)4 (-10, 20)(-1, 0)4 (-16, 20)(-1, 0)4 (-22, 20)(-1, 0)4 (-28, 20)(-1, 0)4 (-34, 20)(-1, 0)2

Input

The input consists of integer numbers, and it is formed by one line with x and y, one line with n, and one or more lines with the coordinates of the n points: x1, y1, x2, y2, …, xn, yn. You can suppose 0 ≤ n ≤ 105. The n points are different, and they can be in any order.

Output

Your program must print according to their distance to (x, y). If two points are at the same distance, print first the one that has the first coordinate smaller and, in the event of draw, the one that has the second coordinate smaller. Follow the format of the instance.

Observation

Your algorithm must be efficient in all the cases, because n can be huge, and because the private test data will include borderline cases, like a lot of points at the same distance.

Public test cases
• Input

```1 -2
8
-3 -2
-2 -1
-2  1
1 -6
2 -3
2  2
3  0
5 -2
```

Output

```points at distance 2
2 -3
points at distance 4
-3 -2
-2 -1
1 -6
3 0
5 -2
points at distance 5
2 2
points at distance 6
-2 1
```
• Input

```2 2
13
2 4
1 3   2 3   3 3
0 2   1 2   2 2   3 2   4 2
1 1   2 1   3 1
2 0
```

Output

```points at distance 0
2 2
points at distance 1
1 2
2 1
2 3
3 2
points at distance 2
0 2
1 1
1 3
2 0
2 4
3 1
3 3
4 2
```
• Input

```-100000000 -100000000
4
-1 -1
0 0
50000000 50000000
-87654321 87654321
```

Output

```points at distance 199999998
-1 -1
points at distance 200000000
-87654321 87654321
0 0
points at distance 300000000
50000000 50000000
```
• Input

```2 3
0
```

Output

• Information
Author
Professorat de P1
Language
English
Translator
Carlos Molina
Original language
Catalan
Other languages
Catalan
Official solutions
C++
User solutions
C++