Кубик поставили на некоторую клетку обычной шахматной доски. Длина ребра кубика в точности равна длине стороны клетки доски. На каждой грани кубика записано целое число в пределах от 0 до 1000. На разных гранях могут быть записаны разные числа. Перекатывая кубик через рёбра основания, можно переместить его в соседнюю ячейку. В ходе перекатываний считается сумма чисел на нижней грани кубика (каждое число входит в сумму столько раз, сколько раз данная грань является нижней для кубика). Найдите маршрут кубика между двумя заданными клетками доски с минимальной суммой чисел на нижней грани. Числа на нижней грани перед началом перекатываний и после их окончания также входят в сумму. Начальная и конечная позиции различны.

Все данные расположены в единственной строке и разделены пробелами. Сначала даны начальная и конечная позиции на доске в стандартной шахматной нотации (символ от ‘a’ до ‘h’ и цифра от ‘1’ до ‘8’). Затем даны 6 чисел, записанных в начальный момент времени на ближней, дальней, верхней, правой, нижней и левой гранях кубика соответственно.

Выведите в единственной строке через пробел минимальную сумму чисел и оптимальный маршрут. Маршрут должен представлять собой последовательность клеток доски, записанных в шахматной нотации, во время движения кубика. Маршрут должен начинаться с начальной позиции и оканчиваться конечной.