407499: GYM102803 C Cornelia Street

"We bless the rain on Cornelia Street, memorize the creaks in the floor."

Creak, creak, creak... The drum beats regularly. To keep the number of syllables in harmony, one sentence in chorus is as long as one in verse. However, drumbeats in the chorus is much stronger.

Jessica wants to memorize the music, piano and drumbeat. She records the music and encodes it into a string. So, the recorded string is so strange.

Let $$$A$$$ be the pattern of verse and $$$B$$$ be the pattern of chorus. So $$$A \neq B$$$ and $$$|A| = |B|$$$. The recorded string $$$S$$$ is in the pattern of $$$AAA \cdots A ~ BB\cdots B ~ AAAAA \cdots Aa$$$. Formally, it is formed as $$$n$$$ times repeat of $$$A$$$, $$$m$$$ times repeat of $$$B$$$, $$$k$$$ times repeat of $$$A$$$, and the broken piece $$$a$$$ at the end is one prefix of $$$A$$$. And note that $$$n, m, k > 0, 0 \leq |a| < |A|$$$.

Now Jessica wants to know the pattern of $$$A$$$ and $$$B$$$. Can you help her?

One line containing a string $$$S ~ (7 \leq |S| \leq 8\times 10^5)$$$. Note that $$$S$$$ consists of only lowercase letters and uppercase letters.

Output one line containing string $$$A$$$ and $$$B$$$ respectively, separated by one space. If there are multiple answers, choose the shortest one.

aaaaaaaaaabaabaaaaaa

aaa aba

ABABABABZXCVZXCVABABABA

ABAB ZXCV

abcababcacabcacabcababc

abcab abcac