Words in the Babaza language consist of any sequence of letters A–Z in which no two adjacent letters are the same. For example, BABAZA, ABCD, FOFOBAR, VALID, and WORD are valid Babaza words, while FOOBAR and ABBA are not.

In the Babaza game, you are given two different Babaza words of the same length. For example:

BABAZA
BACBCB

You then need to find a way to change the first word into the second in the smallest possible number of steps. In each step, you may change one or more letters, but you may never change two letters that are next to each other. After each step, you must have a valid Babaza word. For example, in the above case, you can solve the problem in two steps as follows:

BABAZA
BACACA
BACBCB

Note that the following solution would be wrong because it tries to change two adjacent letters (...BA... to ...CB...):

BABAZA
BACBZA
BACBCB

This solution is also wrong because BABBZB has two adjacent Bs, meaning it is not a Babaza word.

BABAZA
BABBZB
BACBCB

Your task is to write a program that always wins the Babaza game by finding the shortest possible sequence of changes from the first word to the second. The input consists of two lines, each with one Babaza word. Your program must output the full sequence of words, including the first and the last.

Input

You are given the two words of the game on two lines, in order, one word per line.

Output

Output the shortest sequence of Babaza words that solves the game, in order, taking you from the first word to the second.

Constraints

Each word in the input is at least 1 and at most 10 characters long.

Example 1

Input:

A
B

Output:

A
B

Example 2

Input:

BABAZA
BACBCB

Output:

BABAZA
BACACA
BACBCB

Example 3

Input:

AB
BA

Output:

AB
AZ
BZ
BA