C. Formurosa
divide and conquer; dp; expression parsing
The Bytelandian Institute for Biological Research (BIBR) is investigating the properties of two species of bacteria, named simply 0 and 1. Even under a microscope, bacteria of those two species are very difficult to distinguish. In fact, the only thing the scientists possess that is able to differentiate between them is a plant called Formurosa.If the scientists place a sample of colonies of bacteria on each on Formurosa's leaves, it will activate a complicated nutrition process. During that process color of Formurosa changes to reflect the result of a — possibly very complicated — logical formula on the species of bacteria, involving constants and the operators | (OR), & (AND) and ^ (XOR). If it is 0, the plant will turn red, otherwise — it will turn blue.For example, if the nutrition process of Formurosa is described by the formula: (((?^?)|?)&(1^?)); then Formurosa has four leaves (the ""?"" signs denote the leaves). If we place 0, 1, 0, 0 on the respective leaves, the result of the nutrition process will be (((0^1)|0)&(1^0)) = 1, therefore the plant will turn blue.The scientists have n colonies of bacteria. They do not know their types; the only thing they know for sure is that not all colonies are of the same type. They want to attempt to determine the bacteria's species by repeated evaluations with Formurosa. During each evaluation they must place exactly one sample on every leaf of the plant. However, they may use multiple samples of one colony during a single evaluation; they can even cover the whole plant with bacteria from one colony!Is it possible for them to always determine the species of each colony, no matter what they are (assuming they are not all the same)?
The first line of input contains a single integer n (2 ≤ n ≤ 106) — the number of colonies of bacteria.The second line contains the formula describing the nutrition process of Formurosa. This line contains only characters «0», «1», «?», «|», «&», «^», «(», «)» and complies with the following grammar:s → 0|1|?|(s|s)|(s&s)|(s^s)The formula consists of no more than 106 characters.
If it is always possible to determine the species of each colony, output ""YES"" (without quotes). Otherwise, output ""NO"" (without quotes).