B. BPE Preparation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Great! Now that you have a working neural net activation function, Sebastian got another task for you to make. Byte-Pair Encoding ($$$BPE$$$) is an algorithm commonly used in LLM tokenizers (such as GPT-4, Gemini, and other stuff that probably wrote your homework at 11pm last Friday). $$$BPE$$$ encodes large strings into smaller strings by using a translation table, which is based on a huuuge dataset.

However, Sebastian found something interesting in this dataset. Turns out that this entire string $$$s$$$ could be represented as the repeated concatenation of another string $$$t$$$! More formally, this means that there's an integer $$$k$$$ so that $$$s = t\mathbin\Vert t\mathbin\Vert ...\mathbin\Vert t$$$ ($$$t$$$ concatenated $$$k$$$ times). Can you help Sebastian find the smallest string $$$t$$$ where this is true?

Input

The first and only line of input contains $$$s$$$ $$$(1 \leq |s| \leq 10^5)$$$ — a contiguous (without any spaces) string that represents Sebastian's dataset.

Output

Print a single string — the string with shortest length $$$t$$$ where there exists an integer $$$k$$$ so that $$$t$$$ concatenated with itself $$$k$$$ times is $$$s$$$.

Example
Input
td
Output
td