Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
Language:
Cube in Labyrinth
 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 623 Accepted: 165

Description

There is a cube on the rectangle X * Y board. The cube side with the side equal to the side of a cell on the board. During one turn the cube may roll over its edge movnig 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 deturmine 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.

All the numbers are positive integers; 2<= X,Y <= 10.

Input

The first input line contains two numbers X and Y separated with one or several spaces. Analogously, the second line consists of the numbers A and B, the third line – of the numbers C and D. Then there amy be an informtaion about the walls.

After a symbol 'v', situated 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 separat line, there are pairs of integers (analogously to the previous paragraph) describing the horizontal walls. The pair M, N define a wall between the cells N, M and N, M+1.

Output

The only line containing the minimal number of moves. If such a displacement is impossible, you should output "no".

Sample Input

```10 2
1 1
10 1
v
2 1
6 2
h
4 1```

Sample Output

`11`

Source

[Submit]   [Go Back]   [Status]   [Discuss]