F: みこみー文字列 - Miko Mi String -

物語

みっこみっこみ〜！みんなのアイドル，田澤みこみこ！今日は〜，みこと一緒に〜，文字列アルゴリズムの練習，しよ☆

みこのとっておきのキャラ作り合言葉，「みっこみっこみ〜」は，ローマ字にすると “MikoMikoMi” になるみこ！つまり，A=“Mi”, B=“Ko” とすると，ABABAの形で書けるってことなの！こんな風に，適切にAとBを決めるとABABAの形に分解できる文字列のことを「みこみー文字列」って言うわ！文字列の名前にまでなっちゃうなんて，みこはみんなの人気者みこね！

みんなでみこみー文字列をも〜っと使っていくために，与えられた文字列がみこみー文字列かどうか判定するプログラムを作ることにしたんだけど，みこ，FizzBuzzより長いプログラムなんて書けな〜い！だから〜，みこのために〜，みこみー文字列を判定するプログラムを書いて欲しいな☆

……アンタ，いま寒いって言った！？

問題

アルファベット大文字・小文字からなる文字列Sが与えられる． ここで，S = ABABAと書けるような，空でない2つの文字列A, Bが存在するならば，Sは「みこみー文字列」であるという． このとき，アルファベットの大文字と小文字は違う文字として区別するものとする． 与えられた文字列がみこみー文字列であるかどうかを判定するプログラムを作成せよ．

入力形式

入力は文字列Sを含む1行のみからなる． Sは以下の条件を満たすと仮定してよい．

• 1 ≤ |S| ≤ 10^6．ただし，|S|は文字列Sの長さを表す．
• Sは大文字，もしくは小文字のアルファベットのみからなる．

なお，入力が非常に大きくなる場合があるため，入力の受け取りには高速な関数を用いることを推奨する．

出力形式

Sがみこみー文字列であるならば，S = ABABAを満たすようなA, Bについて，“Love AB!”と出力せよ．ただし，複数のA, Bの組が条件を満たす場合，|AB|が最小のものを出力せよ． Sがみこみー文字列でないならば，“mitomerarenaiWA”と出力せよ．

入力例1

NicoNicoNi

出力例1

Love Nico!

入力例2

KashikoiKawaiiElichika

出力例2

mitomerarenaiWA

入力例3

LiveLiveL

出力例3

Love Live!

入力例4

AizunyanPeroPero

出力例4

mitomerarenaiWA

入力例5

AAAAAAAAAAAAAA

出力例5

Love AAAAA!