C2. 消息传输错误（困难版）

时间限制：每个测试点 $2$ 秒
内存限制：$256$ 兆字节

本题为困难版，与简易版的区别仅在于数据范围。

在贝兰德国立大学，服务器之间的本地网络并不总是无差错运行。当连续传输两条相同的消息时，可能会发生一种错误，导致两条消息合并为一条。在合并过程中，第一条消息的结尾与第二条消息的开头重合。当然，合并只能发生在相同的字符上，且合并长度必须为正数且小于消息文本的长度。

例如，连续传输两条消息 "abrakadabra" 时，可能因所述类型的错误而传输得到类似 "abrakadabrabrakadabra" 或 "abrakadabrakadabra" 的结果（第一种情况合并了 $1$ 个字符，第二种情况合并了 $4$ 个字符）。

给定接收到的消息 $t$，请判断它是否可能是上述类型错误的结果；如果是，请给出一个可能的 $s$ 值。

两条消息完全重叠的情况不应视为错误。例如，如果接收到的消息是 "abcd"，应认为其中没有错误。同样，仅仅将一条消息附加在另一条消息之后也不构成错误。例如，若收到的消息是 "abcabc"，也应认为其中没有错误。

输入

输入只有一行非空字符串 $t$，由小写拉丁字母组成。字符串 $t$ 的长度不超过 $4 \times 10^5$ 个字符。

输出

如果消息 $t$ 不可能包含所述错误，则输出一行 "NO"。
否则，第一行输出 "YES"，第二行输出一个字符串 $s$ —— 可能造成该错误的消息。如果有多个可能的答案，输出任意一个即可。

示例

输入

abrakadabrabrakadabra

输出

YES
abrakadabra

输入

acacacaca

输出

YES
acacaca

输入

abcabc

输出

NO

输入

abababab

输出

YES
ababab

输入

tatbt

输出

NO

提示
在第二个示例中，"acacaca" 也是一个合适的答案。