Bronze Lilypad Pond

Farmer John built a rectangular pond for his cows to admire and exercise in. The pond is divided into a grid of $M$ rows and $N$ columns ($1 \le M \le 30$, $1 \le N \le 30$). Every cell holds one of three things: a remarkably sturdy lilypad, a rock, or open water.

Bessie the cow is practising her ballet by leaping from lilypad to lilypad. She currently stands on one lilypad and wants to reach another. She may land only on lilypads — never on open water and never on a rock.

Each of Bessie's leaps has the shape of a generalized knight's move: she travels $M_1$ cells in one cardinal direction and then $M_2$ cells in a perpendicular direction, or $M_2$ cells in one direction and then $M_1$ cells in a perpendicular direction ($1 \le M_1 \le 30$, $1 \le M_2 \le 30$, $M_1 \ne M_2$). This gives up to eight possible landing cells per leap. Only the landing cell must be a lilypad; Bessie may fly over water and rocks freely.

Given the pond layout and the two jump lengths, determine the minimum number of leaps Bessie needs to travel from her starting lilypad to her destination lilypad. A route is guaranteed to exist for every input.

The first line contains four space-separated integers $M$, $N$, $M_1$, and $M_2$.

Each of the next $M$ lines contains $N$ space-separated integers describing one row of the pond, using these codes:

• $0$ — open water
• $1$ — a lilypad
• $2$ — a rock
• $3$ — the lilypad Bessie starts on
• $4$ — the lilypad that is Bessie's destination

Exactly one cell equals $3$ and exactly one cell equals $4$.

Print a single integer: the minimum number of leaps Bessie must make to reach her destination lilypad from her starting lilypad.

Think of each lilypad as a node in a graph, with an edge between two lilypads whenever a single generalized knight's move connects them. A breadth-first search from the starting lilypad then yields the minimum number of leaps. Remember that Bessie may pass over water and rocks — only the landing cell must be a lilypad.