C. Cornelia Street
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

"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 \gt 0, 0 \leq |a| \lt |A|$$$.

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

Input

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

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

Examples
Input
aaaaaaaaaabaabaaaaaa
Output
aaa aba
Input
ABABABABZXCVZXCVABABABA
Output
ABAB ZXCV
Input
abcababcacabcacabcababc
Output
abcab abcac