There is a cube on the rectangular X × Y board. The cube side is equal to the side of a cell of the board. During one turn the cube may roll over its edge moving to the vertically or horizontally neighboring cell. There may be walls between some cells that are obstacles. The cube may not roll over the obstacles. The cube may not leave the board.
You are to find the minimal number of turns necessary to move the cube from the initial point with coordinates A and B to the given final point with coordinates C and D. Moreover, in the final position the upper side must be the same as it was in the initial position.
The first input line contains two numbers X and Y separated with one or more spaces. The second line consists of the numbers A and B, and the third line consists of the numbers C and D presented in the same way. Then an information about the walls may follow. All the numbers are integers; 2 ≤ X,Y ≤ 10.
After a symbol ‘v’, located in a separate line, there are pairs of integers describing the walls. Here the pair of numbers M and N define a wall between the cells N, M and N+1, M. Each pair of numbers is located in a separate line.
After a symbol ‘h’, located in a separate line, there are pairs of integers describing the horizontal walls in the same way. The pair M, N define a wall between the cells N, M and N, M+1.
The only line containing the minimal number of moves. If such a displacement is impossible, you should output “No solution”.
Problem Source: II Collegiate Students Urals Programming Contest. Yekaterinburg, April 3-4, 1998