P13677 [GCPC 2023] Loop Invariant

Luna 是一位历史学家，在探索一座古老修道院的档案时，偶然发现了一卷神秘的羊皮纸。上面只有两种符号：“$\texttt{(}$” 和 “$\texttt{)}$”。很快她注意到，这串符号满足一个有趣的性质：它可以通过不断地在一个初始为空的序列中的某个位置插入“$\texttt{()}$”构造出来。历史学家们称这样的序列为*平衡序列*。图 L.1 给出了一个平衡序列的例子。 :::align{center}  一张圆形的羊皮纸。 :::  :::align{center} 图 L.1：通过不断在初始为空的序列中插入“$\texttt{()}$”得到的样例输入 2。 ::: 修道院的首席图书管理员最近告诉 Luna，本地区一些更为精英的修士有在圆形羊皮纸上书写的习惯。在他们看来，无法立刻分辨出这卷羊皮纸文字起始位置的人，也不配知晓其内容。因此，Luna 很快检查了羊皮纸条的左右两端。果然，羊皮纸条的左右两端完美契合，表明这张羊皮纸原本实际上是圆形的。当她将左右两端合在一起，观察现在变成圆形的羊皮纸时，她在思考，从撕裂处开始的平衡序列是否是唯一可能由撕开圆形羊皮纸得到的平衡序列。毕竟，如果连文本的起始位置都不知道，试图解读内容也毫无意义。

输入包含一行，一个平衡序列 $s$（$2\leq |s|\leq 10^6$），即 Luna 羊皮纸条上的序列。

如果无法通过切割这个圆形序列得到不同的平衡序列，则输出“$\texttt{no}$”；否则，输出任意一个不同的平衡序列。

由 ChatGPT 4.1 翻译