The Shortest Path of the Knight

On an 8×8 chessboard, you are given two specific squares. Your task is to find the shortest path a knight can take to travel between these two squares.

Input

You will receive the coordinates of the two squares, each on a separate line. The coordinates are provided in the format of a letter (ranging from "a" to "h") followed by a number (from 1 to 8), with no spaces in between.

Output

Print the sequence of moves that the knight will take, starting at the first square and ending at the second, using the minimum number of moves possible.

Examples