問題文

文字列 $T$ が「ヘビ文字列」であるということを次のように定義します。

$N$ を $T$ の長さとして、ある整数 $i\ (1 \le i \le N - 1)$ が存在して、$T$ を $i$ 文字目と $i + 1$ 文字目の間で分割し、前半後半を入れ替えたときに元の文字列 $T$ に戻る。
つまり $T = T_{i + 1} T_{i + 2} ... T_N T_1 T_2 ... T_i$ を満たす。 ($T_i$ は $T$ の $i$ 文字目の文字を指す)

英大文字からなる文字列 $S$ が与えられます。$N$ を $S$ の長さとして、あなたは次の操作を何度でも繰り返すことができます。

整数 $i\ (1 \le i \le N)$ を選び、$S_i$ を好きな英大文字で置き換える。

出来るだけ少ない回数の操作で $S$ をヘビ文字列 $S^\prime$ にしてください。

入力

$S$

$S$ は英大文字からなる文字列。
$S$ の長さ $|S|$ は $2 \le |S| \le 2 \times 10^6$.

出力

$S^\prime$

答えとなるような $S^\prime$ が複数存在する場合はどれを出力しても構いません。
最後に改行してください。

注意

• 提出したプログラムが TLE (Time Limit Exceeded; 時間切れ) となる場合は、アルゴリズムをもっと効率的にできるかも検討してください。
• 使用する言語によっては、正しいアルゴリズムが書けていても TLE になることがあります。 Python をお使いの方は、一般的な Python 処理系 (CPython) ではなく、より早い処理系の PyPy を使うことをおすすめします。 C++, PyPy では制限時間に間に合うことは確認済みです。

サンプル

ABCBBBACC

ABCABCABC

ABCDEFG

AAAAAAA