Bytelandian 生物研究所 (BIBR) 正在研究两种细菌的特性,简称为 0 和 1。即使在显微镜下,这两种细菌也很难区分。事实上,科学家们唯一能够区分它们的就是一种叫做福尔摩罗莎的植物。
如果科学家们将细菌菌落样本放置在福穆罗莎叶子上,它将激活一个复杂的营养过程。在此过程中,Formurosa 的颜色会发生变化,以反映细菌种类的逻辑公式(可能非常复杂)的结果,其中涉及常数和运算符 | (或)、& (与) 和 ^ (异或)。如果它是0,植物就会变成红色,否则——它就会变成蓝色。
例如,福尔摩沙的营养过程用公式描述:(((?^?)|?)&(1^?));那么福尔摩沙有四片叶子(“?”符号表示叶子)。如果我们将 0, 1, 0, 0 放在各个叶子上,营养过程的结果将是 (((0^1)|0)&(1^0)) = 1,因此植物会变成蓝色。
科学家们有n个细菌菌落。他们不知道自己的类型;他们唯一确定的是,并非所有的殖民地都是同一类型。他们希望通过与福尔莫罗萨公司的反复评估来尝试确定细菌的种类。在每次评估期间,他们必须在植物的每一片叶子上放置一个样品。然而,他们可能在一次评估中使用一个菌落的多个样本;它们甚至可以用一个菌落的细菌覆盖整个植物!
他们是否有可能始终确定每个群体的物种,无论它们是什么(假设它们并不完全相同)?
输入
输入的第一行包含一个整数 n (2 ≤ n ≤ 106) — 细菌菌落数。
第二行包含描述福尔摩罗莎营养过程的配方。该行仅包含字符 «0», «1», «?», «|», «&», «^», «(», «)» 并符合以下语法:
s → 0|1|?|(s|s)|(s&s)|(s^s)
公式长度不超过 106 个字符。
输出
如果始终可以确定每个菌落的物种,则输出“YES”(不带引号)。否则,输出“NO”(不带引号)。
示例
输入 #1
2 (?^?)
输出 #1
NO
输入 #2
10 ?
输出 #2
YES
输入 #3
2 ((?^?)&?)
输出 #3
YES