Again About Horses

On an 8×8 chessboard, you are given two distinct squares.

Your task is to determine the shortest path a knight can take to move from the first square to the second.

Input

The input consists of the coordinates of two squares. Each coordinate is represented by two characters: the first is a lowercase letter from a to h, and the second is a digit from 1 to 8, such as h8. Each square's coordinates are provided on a separate line.

Output

The output should be a sequence of squares, beginning with the first square and ending with the second. Each pair of consecutive squares in the sequence must be connected by a knight's move, and the total number of squares in the sequence should be minimized.

Examples