The jack jumper ant¹ (Myrmecia pilosula) is a species of venomous ants native to Australia, most commonly found in Tasmania and southeast mainland Australia. It was formally described and named by British entomologist Frederick Smith in 1858. The species is known for the ability to jump long distances. Their sting generally only causes a mild local reaction in humans. However, it is one of the few ant species that can be dangerous to humans. Between 1980 and 2000, there have been four recorded deaths, all in Tasmania and all due to anaphylactic shock². The venom causes about 90% of Australian ant allergies.

Assignment

Foraging ants usually form one long row, with each ant following its predecessor. But what happens if two rows of ants meet each other when they forage in opposite directions across an edge that does not allow them to pass each other? With the species Myrmecia pilosula, the ants simply jump over one other. In this assignment we will simulate this jumping behavior.

Input

There are two lines of input that only contain uppercase letters. Each line represents a row of ants, with the two rows foraging in opposite directions. Each ant is represented by a unique uppercase letter. As such, there are no more than 26 ants in total. The first line describes the row of ants that forages from the left. The second line describes the row of ants that forages from the right. In both cases, the ants are arranged in the order they are foraging: the first ant forages at the front of the row!

Output

The output exists of a couple of lines that each describe the order of the ants while they are passing each other. The first line describes the order of the ants at the point in time when the two rows first meet on the edge. If two ants directly face each other in a previous step (without any other ants in between them), they change positions in a next step. The last step that must be described in the output, is the step after which no more ants change positions.

Example

Input:

CBA
DEFG

Output:

ABCDEFG
ABDCEFG
ADBECFG
DAEBFCG
DEAFBGC
DEFAGBC
DEFGABC

Graphical simulation of these two rows of jumping ants crossing each other: