На прямоугольном поле из X на Y квадратных клеток находится куб со стороной, равной длине стороны клетки. За один ход куб может перекатываться через ребро, перемещаясь на соседнюю по вертикали или горизонтали клетку. Между некоторыми клетками могут стоять стенки, которые являются препятствиями. Куб не может перекатываться через препятствия. Куб также не может покидать пределы поля.

Требуется определить минимальное число ходов, необходимых для того, чтобы переместить куб из заданной начальной клетки с координатами A и B в заданную конечную клетку с координатами C и D. При этом в конечном положении верхняя грань должна быть та же, что и в начальном положении.

В первой строке входа указаны размеры поля X (по горизонтали) и Y (по вертикали), отделенные друг от друга одним или несколькими пробелами. Таким же образом во второй строке указаны A и B, а в третьей – C и D. Далее может следовать информация о стенках. Все числа целые; 2 ≤ X,Y ≤ 10.

После символа ‘v’, расположенного в отдельной строке, перечисляются пары чисел, говорящие о вертикальных стенках. Здесь пара чисел N и M определяет стенку между клетками N,M и N+1,M. Каждая пара чисел расположена в отдельной строке. Пустых строк между парами нет.

После символа ‘h’, стоящего в отдельной строке, перечисляются (таким же образом) пары чисел, говорящие о горизонтальных стенках. Пара чисел N и M определяет стенку между клетками N,M и N,M+1.

Ваша программа должна записать единственную строку, содержащую минимальное число ходов. При невозможности перемещения в эту строку следует записать текст “No solution”.