CF217C Formurosa

Bytelandia 生物研究院（BIBR）正在研究两种细菌：编号为 0 和 1。即使在显微镜下，这两种细菌也很难区分。事实上，科学家们唯一能区分它们的方法，是借助一种叫 Formurosa 的植物。 如果科学家们在 Formurosa 的每片叶子上分别放置一组细菌样本，植物就会启动一种复杂的营养反应。在这个过程中，Formurosa 的颜色会发生改变，其结果是根据细菌类型，利用一些常数和运算符 $|$（或）、$&$（与）、$^$（异或）计算出的一个逻辑表达式。如果结果为 0，植物变成红色，否则变成蓝色。 例如，如果 Formurosa 的营养过程由以下公式描述：$ (((?^?)|?)\&(1^?)) $；则 Formurosa 有四片叶子（每个“?”表示一片叶子）。如果我们分别放置 $0, 1, 0, 0$，营养过程的结果就是 $ (((0^1)|0)\&(1^0))=1 $，因此植物会变成蓝色。 科学家们有 $n$ 个细菌样本，但他们不知道每个样本的类型，唯一确定的是并非所有样本类型都相同。他们希望通过多次使用 Formurosa 来确定每个样本的类型。每次实验必须给每片叶子都放一个样本，可以重复使用某些细菌样本，甚至可以所有叶子都放同一种。 不论样本类型如何分布（只要不是全部相同），他们能否一定推断出每个细菌样本的类型？

第一行输入一个整数 $n$，表示细菌样本的数量，$2 \leq n \leq 10^6$。 第二行输入一个描述 Formurosa 营养过程的公式。该公式仅包含字符「0」、「1」、「?」、「|」、「&」、「^」、「(」、「)」，且符合以下语法： $s \rightarrow 0|1|?| (s|s) | (s \& s) | (s^s)$ 公式长度不超过 $10^6$ 个字符。

如果一定能确定每个样本的类型，输出 “YES”；否则输出 “NO”。

由 ChatGPT 5 翻译