Escape from Enemy Territory

Time limit3sMemory limit128 MB

Summary

Given a grid with enemy bases, find the maximum possible minimum Manhattan distance to any base along a path from start to rendezvous, then the shortest such path's step count.

Level: Medium7 of 10
Topics: Binary search, BFS, Graph
Solved: No attempts yet

Problem

A small team of commandos has infiltrated deep into enemy territory. They have just finished their mission and must now return to their rendezvous point without being caught. To stay safe, they want to follow a route that keeps them as far as possible from every enemy base.

The area is modeled as a rectangular grid of integer coordinates $(x, y)$ with $0 \le x < X$ and $0 \le y < Y$ . At each step a commando moves one unit up, down, left, or right, and the route may never leave the grid. Distances use the Manhattan metric:

$\operatorname{dist}((x_1, y_1), (x_2, y_2)) = |x_2 - x_1| + |y_2 - y_1|.$

The separation of a route is the smallest Manhattan distance between any cell it visits (including the start and the rendezvous point) and any enemy base. The commandos first want to maximize this separation. Among all routes that achieve the maximum separation, they then want one with the fewest steps. Enemy bases outside the grid do not exist and can be ignored.

Input

The first line contains the number of test cases $T$ $(1 \le T \le 100)$ . Each test case is given as follows:

One line with three integers $N$ , $X$ , $Y$ $(1 \le N \le 10000,\ 1 \le X, Y \le 1000)$ : the number of enemy bases and the grid size. A coordinate $(x, y)$ lies on the grid if and only if $0 \le x < X$ and $0 \le y < Y$ .
One line with four integers $x_i\ y_i\ x_r\ y_r$ : the commandos' starting position $(x_i, y_i)$ and the rendezvous point $(x_r, y_r)$ .
$N$ lines, each with two integers $x\ y$ giving the position of one enemy base.

All given coordinates lie on the grid and are pairwise distinct.

Output

For each test case, print one line with two integers separated by a single space: the maximum achievable separation from any enemy base, followed by the number of steps in the shortest route that achieves that separation.

Examples6

Example 1

Input

Expected output

1 2
2 14

Example 2
Input
```
1
1 5 5
0 0 4 4
2 2
```
Expected output
```
2 8
```
Example 3
Input
```
1
1 3 1
0 0 2 0
1 0
```
Expected output
```
0 2
```
Example 4
Input
```
1
2 7 5
0 2 6 2
3 1
3 3
```
Expected output
```
1 6
```
Example 5
Input
```
1
1 4 4
0 0 3 3
1 0
```
Expected output
```
1 6
```

Example 6

Input

Expected output

1 2
1 4
1 6