Shortest Alternating-Color Path on a Parallelogram

Given a parallelogram (assumed here as a rectangle) with a base length L and a height H, its four edges are assigned a color – either black or white – in clockwise order. The edges are positioned as follows:

• Edge 0 (bottom): length L
• Edge 1 (right): length H
• Edge 2 (top): length L
• Edge 3 (left): length H

You are given an entrance and an exit, specified as vertices of the rectangle. The vertices are numbered 0 to 3 as follows:

• Vertex 0: bottom-left
• Vertex 1: bottom-right
• Vertex 2: top-right
• Vertex 3: top-left

Your task is to determine the shortest path along the perimeter from the entrance to the exit such that the colors of consecutive edges alternate (i.e. black, white, black, white, ...). A single edge on its own is considered valid. If no alternating-color path exists, output -1.

The distance of each edge is given by:

\[ \begin{array}{lcl} d_0 &=& L\\ d_1 &=& H\\ d_2 &=& L\\ d_3 &=& H \end{array} \]

The total distance of a path is the sum of the distances of the edges traversed along the perimeter.

inputFormat

The input consists of three lines:

1. The first line contains two integers L and H, representing the base length and the height respectively.
2. The second line contains two integers representing the indices of the entrance and exit vertices (each in the range 0 to 3).
3. The third line contains 4 space-separated strings; each is either black or white, representing the colors of the edges in clockwise order: bottom (edge 0), right (edge 1), top (edge 2), and left (edge 3).

outputFormat

Output a single integer, which is the total length of the shortest valid path (with alternating colors) along the perimeter from the entrance to the exit. If no such path exists, output -1.

sample

5 3
0 2
black white black white

8