What word comes at the question mark to complete this word sequence?

Space, Cinema, Ester, Abaci, Cabaret, Seamen, ?

The complete sequence is a palindrome: you get the same sequence of letters if you read the letters of the words from left to right or from right to left. So the missing word is Icecaps:

Space, Cinema, Ester, Abaci, Cabaret, Seamen, Icecaps

Assignment

In this kind of puzzle you have to append one word at the end of a given sequence such that the complete sequence is a palindrome. You can find the missing word by first writing all letters of the given words one after the other. In doing so, convert all letters into lowercase, to make no distinction between uppercase and lowercase letters. We will call this the forward sequence:

spacecinemaesterabacicabaretseamen

Then reverse the order of the letters from the forward sequence. We will call this the backward sequence:

nemaesterabacicabaretseamenicecaps

Next, find the longest suffix of the forward sequence that is also a prefix of the backward sequence. Here's that longest common suffix/prefix marked in green:

spacecinemaesterabacicabaretseamen*******
*******nemaesterabacicabaretseamenicecaps

If you remove the longest common suffix/prefix as a prefix from the backward sequence, what remains is the missing word. We marked that missing word in blue in the above example.

Prefix and suffix

A prefix of a word $$w$$ is a sequence of one or more letters at the start of $$w$$. For example: fore is a prefix of foresight.

A suffix of a word $$w$$ is a sequence of one or more letters at the end of $$w$$. For example: sight is a suffix of foresight.

Input

The first line contains a number $$t \in \mathbb{N}_0$$. This is followed by $$t$$ lines, each containing a word that only contains letters.

Output

The output consists of the following four lines:

  1. the forward sequence for the given sequence of $$t$$ words, followed by as many asterisks (*) as the number of letters in the missing word

  2. as many asterisks (*) as the number of letters in the missing word, followed by the backward sequence for the given sequence of $$t$$ words

  3. as many equal signs (=) as the number of characters on the first (and also the second) line of the output

  4. the missing word that completes the given sequence of $$t$$ words, written as an uppercase letter followed by lowercase letters

Example

Input:

6
Space
Cinema
Ester
Abaci
Cabaret
Seamen

Output:

spacecinemaesterabacicabaretseamen*******
*******nemaesterabacicabaretseamenicecaps
=========================================
Icecaps