Problem D
Lazy River Ride

A lazy river is a relaxing pool that flows in one or more loops, allowing people to float around in circles. Some lazy rivers have split paths to make the experience more interesting. After a long hard day of programming you decide to take a ride in one such river, but being as exhausted as you are you decide to plan a route through the river that requires the least amount of effort. The effort required to navigate the river is determined by the direction of the current at each point in the river. To make planning easier you first break the river into a grid made up of square cells and record the direction of the current in each cell. In order to move to the neighbouring cell in the direction of the current you don’t need to exert any effort, to move to either of the cells diagonally in the direction of the current (e.g. NW or NE if the current is N, or W or N if the current is NW) you will need to exert one unit of effort. Moving to any other neighbouring cell would require too much effort and thus is not an option. You also cannot stay in the same cell or move into a cell that is a wall.

Figure 1: Diagrams showing the effort required to move in each direction from a north current and a northwest current

Given a grid representing the lazy river and an initial starting point, determine the minimum effort required to navigate the river from the starting point back to the starting point.

Input

The first line of the input contains four integers $r$, $c$, $x$, and $y$ ($1 \leq r, c \leq 100$, $1 \leq x \leq r$, $1 \leq y \leq c$) the number of rows and columns in the map and starting row and column respectively. The next $r$ lines each contain $c$ characters. Each character is either a “#” or a digit from $1$ to $8$ inclusive, where a “#” represents a wall and a digit represents the direction of current as indicated in Figure 2.

Figure 2: 1:NW, 2:N, 3:NE, 4:E, 5:SE, 6:S, 7:SW, 8:W

It is guaranteed that the starting point is not be a wall.

Output

Output a single integer the minimum effort required to navigate the river from the starting point back to the starting point after while moving at least once. Note: It is always possible to navigate the river back to the starting point.

3 3 1 1
688
6#2
442

0

8 7 8 7
6888888
6#####2
4444442
2#####2
2888882
6#####2
6#446#2
442#442

2

7 7 1 1
6888566
6##3566
68#3566
42#3566
#6##1##
4444268
4444442

4