Найкоротший шлях коня

На шаховій дошці розміром 8×8 задано дві клітинки. З'єднайте ці клітинки найкоротшим шляхом коня.

Вхідні дані

Задано координати двох клітинок, кодна у окремому рядку. Координати клітинок задаються у вигляді букви (від "a" до "h") та цифри (від 1 до 8) без пропусків.

Вихідні дані

Вивести шлях коня, який починається і завершується у заданих клітинках і містить найменше число клітинок.

Приклади