Minimum Energy Path

The task is to compute the minimum energy required for a rover to travel from a given starting position to a destination within a grid. The grid represents a terrain with different energy costs for moving through cells.

Each cell in the grid can be one of the following:

• . : Normal terrain with an energy cost of \(1\) unit.
• ~ : Water terrain with an energy cost of \(3\) units.
• # : Obstacle which is not passable.

You can move in the four cardinal directions (up, down, left, right). The positions are given in 1-indexed format. If reaching the destination is impossible, the output should be \(-1\).

inputFormat

The input consists of multiple datasets. Each dataset is structured as follows:

1. A line with two integers \(N\) and \(M\), representing the number of rows and columns of the grid.
2. A line with four integers: \(x_1\), \(y_1\), \(x_2\), \(y_2\) denoting the starting and destination positions respectively (1-indexed).
3. \(N\) lines follow, each representing a row of the grid. Each character in the row is one of ., ~, or # as described above.

The input terminates with a line containing a single 0. Read the input from standard input (stdin).

outputFormat

For each dataset, output a single line that contains the minimum energy required to travel from the start to the destination. If the destination is unreachable, output \(-1\). Write your output to standard output (stdout).

## sample

4 4
1 1 4 4
....
.#..
.~~.
...~
0

8

</p>