# Distance to the nearest point P28079

Statement html

Given two sets S and Q of points on the plane, determine, for each point in Q, the minimum of the Manhattan distances to the points in S.

Input

Input consists of a natural n, the coordinates of the n points in S, a natural m, and the coordinates of the m points in Q. Assume 1 ≤ n ≤ 105 and 0 ≤ m ≤ 105. The coordinates are real numbers. Points can be repeated.

Output

For every point in Q, print the Manhattan distance to its closest point in S.

Observation

This problem tolerates an error of 10−7 for each output.

Public test cases
• Input

```5
0 0
0 1
1 0
1 1
1 0
3
0.1 0.1
0.5 0.5
1.0 1.0
```

Output

```0.20000000
1.00000000
0.00000000
```
• Input

```3
2057.54368732 7224.84142068
6754.64655994 7907.85575136
9678.10748947 4968.45548394
4
6628.69040481 8947.34821279
747.4327363 8300.22431512
8784.52986333 4373.37802232
7170.45535426 6464.09159581
```

Output

```1165.44861656
2385.49384546
1488.65508776
1859.57294987
```
• Input

```5
0 0
0 1
1 0
1 1
1 0
3
0.1 0.1
0.5 0.5
1.0 1.0
```

Output

```0.20000000
1.00000000
0.00000000
```
• Information
Author
Jordi Petit
Language
English
Official solutions
C++
User solutions
C++