Problem3510--Formurosa

3510: Formurosa

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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)?

Input

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.

Output

If it is always possible to determine the species of each colony, output "YES" (without quotes). Otherwise, output "NO" (without quotes).

Examples
Input
2
(?^?)
Output
NO
Input
10
?
Output
YES
Input
2
((?^?)&?)
Output
YES

Source/Category