Words in the Babaza language consist of any sequence of letters A–Z such that no two adjacent letters are the same. So for example, BABAZA, ABCD, FOFOBAR, VALID, and WORD are valid words in Babaza, 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 need to then find a way of changing the first word to the second in the smallest possible number of steps. In each step you can change one or more letters, but you can never change two letters that are next to each other. And after each step you must have a valid Babaza word. So for example, in the above case you can solve the problem in two steps like this:

BABAZA
BACACA
BACBCB

Note that the following solution would be wrong, as it is trying to change two adjacent letters (...BA... to ...CB...):

BABAZA
BACBZA
BACBCB

This solution is also wrong, as BABBZB has two adjacent Bs, meaning that 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 one. The input consists of two lines, each with one Babaza word. Your program needs to output the full sequence of words, including the first one and the last one.

Input

You are given the two words of the game in two lines, in order, one word in each 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