Problem B
A Greedy Hike

One of our students, Alice, loves to go on long mountain hikes. When she first started hiking, Alice would just pick random trails in a map, but soon realized this was not a good strategy: Alice loves mountains, but is not crazy about steep climbs (or descents), and some of the trails involve large elevation changes in a very short distance. So, as a Computer Science student, Alice decided she would come up with a concrete algorithm to try to minimize the number of steep climbs and descents during her hike. However, Alice knows that finding an optimal path is challenging, so she instead decides to apply a greedy algorithm: at each point in the hike, she will always follow the path that involves the smallest absolute elevation change. For example, given the choice between ascending 500ft and descending 1000ft, Alice will actually choose to ascend 500ft because it involves a smaller absolute elevation change (yes, climbing is more fatiguing than descending, but a steep descent can be dangerous and prone to falls).

To figure out the best path, Alice will use a simplified elevation map that shows elevations on an $X$ by $Y$ grid. For example:

Notice that $X$ specifies the number of rows, numbered from zero, and $Y$ specifies the number of columns, numbered from zero.

Alice begins her hike at a starting position denoted by coordinates $(x_ s, y_ s)$. For example, if the starting position in the above hike is $(2,1)$, Alice would begin her hike at elevation 10.

At each step in her hike, Alice will always move to the right by one position (i.e., she will increase her $y$ position by one) and can change her $x$ position by 1, 0, or -1 (as long as she doesn’t exceed the bounds of the map). So, if Alice is in position $(2,1)$, she can move to three possible positions:

In this case, Alice would choose to move to position $(2,2)$, with elevation 15. Remember that Alice always chooses the option with the smallest absolute elevation change.

But what if more than one option has the same elevation change? Well, let’s denote the three possible options as $x_{-1}$, $x_0$, and $x_{+1}$:

The tie-breaking rules are simple:

• If the absolute elevation change for $x_{-1}$ or $x_{+1}$ is equal to the absolute elevation change for $x_0$, then we choose $x_0$. Note that this includes the case when all three options have the same absolute elevation change.

• If the absolute elevation change for $x_{-1}$ is the same as the one for $x_{+1}$ (but they are still both smaller than the one for $x_0$), then we choose $x_{+1}$.

Alice will continue to take steps, according to the algorithm described above, until she reaches the rightmost edge of the map (i.e., until her $y$ coordinate is equal to $Y-1$). In this case, starting at $(2,1)$ would result in the following path:

Once we compute a path, there are two things that Alice cares about:

• The ending position, which we will denote as $(x_ e,y_ e)$. In this case, the ending position is $(2,6)$. Notice how $y_ e$ will always be equal to $Y-1$.

• The sum of all the absolute elevation changes, which we will denote as $E$. In this case, this would be 13: $|15-10|+|12-15|+|12-12|+|9-12|+|11-9|=5+3+0+3+2=13$

Finally, take into account that Alice’s algorithm is not guaranteed to find the best path, although it will usually find a pretty good one. For example, take this map, assuming $(x_ s,y_ s) = (1,0)$:

Our greedy algorithm produces a path with $E=15$, even though a better path (with $E=3$) exists in the map. You should not worry about this, and should always apply the greedy algorithm described above, even if it doesn’t produce the best possible path.

Input

The input contains the specification of an elevation map. The specification starts with a line with $X$ and $Y$, separated by a single space ($1\leqslant X, Y \leqslant 100$). The next line contains $x_ s$ and $y_ s$, separated by a single space ($0 \leqslant x_ s < X$ and $0 \leqslant y_ s < Y$).

The input is followed by $X$ lines, each corresponding to a row of the elevation map, starting with row 0. Each such line contains $Y$ integers, representing the elevations in that row. Each integer is separated by a single space, and will be greater than or equal to 0, and strictly smaller than $10\, 000$.

Note that the two sample inputs correspond to the two maps discussed earlier.

Output

The output will be the result of running the greedy hiking algorithm. It will be a single line with three values, each separated by a single space: $x_ e\; \; y_ e\; \; E$

5 7
2 1
0 3 15 10 15 5 0
5 8 20 12 12 17 5
7 10 15 5 12 9 11
5 7 3 2 5 5 7
0 9 11 8 9 2 3

2 6 13

4 4
1 0
0 2 10 15
0 10 15 20
0 3 3 3
0 10 10 10

0 3 15