Exploration rover navigation

Assignment

A team of NASA researches aims to navigate an exploration rover deployed on a surface of a distant planet. The environment on the surface is highly inhomogeneous in terms of pressure and temperature, which have an impact on the movement and enforce so called reconfigurations of the rover used to adapt it to varying conditions. To simplify the planning, the surface is discretized and represented by a grid map, composed of sectors. Based on the average pressure and temperature, each sector is assigned by an identifier which specifies its type. In addition, each maximal connected subset of neighboring sectors of the same type is called a region (a subset is maximal when it cannot be extended by one more neighboring sector of the same type; two sectors are neighbors if they share a side). The rover can move from each sector to a neighboring one, located northwards, westwards, southwards or eastwards. Each such movement is called a single move. It is possible to perform several single moves to relocate the rover. The rover has to be reconfigured each time it crosses a border between a region of type T₁ consisting of S₁ sectors and a region of type T₂≠T₁ consisting of S₂ sectors where |S₁-S₂| > min(S₁, S₂).
The researches look for an optimal route from a starting sector to a target sector which will require to perform the minimal possible number of reconfigurations. Among all routes with the minimal number of reconfigurations, the researches search for the shortest route. The length of a route is defined as the number of single moves to be performed to follow it.

Image 1. (a) A map of sectors which contains 7 regions distinguished by color. The numbers identify sector types. The starting sector is in the 4th row and 1st column, the target sector is in the 2nd row and 5th column. An optimal route consisting of 6 single moves is depicted by the red arrows. One reconfiguration is required when moving from the blue region of size 6 to the target sector (brown region of size 1). The other moves do not require reconfigurations. (b) The target sector (6th row, 8th column) can be reached from the starting sector (3rd row, 1st column) without any reconfiguration. An optimal route of length 16 is again depicted by the red arrows. Observe that the target sector is in the blue region of size 6. This region can be reached without a reconfiguration only from the green region of size 4, and the green region can be reached without a reconfiguration from the orange region of size 2. Finally, the orange region is reached from the starting sector through a sequence of one-sector regions (not highlighted by color).

Task

You are given a map of sectors, starting position and target position. Your task is to compute the number of reconfigurations and length of an optimal route.

Input

The first input line contains two integers M and N which determine the grid size: M is the number of rows, N is the number of columns. The second input line contains integers Sr and Sc specifying the starting sector (it is located in row Sr and column Sc). Analogously, the third line contains integers Tr and Tc specifying the target sector (located in row Tr and column Tc). We consider the rows and columns to be numbered from 1 to M and N, respectively. Next, there are M input lines, each of them containing N integers, separated by a space, that describe types of sectors in the row. Each of the integers is in the range from 1 to 20.
It holds M*N ≤ 1.5*10⁶.

Output

The output consists of one line containing two integers R and D, separated by a space. R is the number of reconfigurations and D is the number of single moves required to follow an optimal route.

Examples

Example 1

Input

Output

1 6

Data and a solution of Example 1 are visualized in Image 1a).

Example 2

Input

6 8
3 1
6 8
3 3 2 2 1 1 2 2
3 1 2 2 4 3 4 2
1 3 1 3 1 2 3 2
2 1 3 2 2 1 1 1
1 2 1 3 3 2 1 3
1 2 3 1 1 2 1 1

Output

0 16

Data and a solution of Example 2 are visualized in Image 1b).

Example 3

Input

8 16
5 1
4 16
1 1 1 1 1 1 5 5 5 5 5 5 5 5 1 1
1 1 1 1 1 5 5 5 5 1 1 5 5 1 1 5
1 1 1 1 5 1 1 1 5 1 5 1 5 1 1 5
1 1 1 1 5 5 1 1 1 1 1 5 5 5 1 5
1 1 1 5 1 1 1 1 1 1 1 1 1 5 1 1
1 1 5 5 5 1 1 1 1 1 1 1 1 1 1 1
1 1 1 5 1 5 5 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 5 1 1 1 1 1 1 1 1

Output

2 22

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.

Veřejná data