IOI Function Evaluation

JOI-kun studies at IOI High School and faces a final exam on computing the IOI Function. An IOI function maps each integer in the interval \([1,10^9]\) to a Boolean value (i.e. True or False). It is built using the following six rules:

1. Base: For an integer \(a\) in \([1,10^9]\), the expression [a] is an IOI function. It maps any integer \(x\) to True if \(x \ge a\) and False otherwise.
2. Parentheses: If f is an IOI function, then (f) is also an IOI function. Its mapping is identical to that of f.
3. Negation: If f is an IOI function, then !f is also an IOI function. For an integer \(x\), if f(x)=True then !f(x)=False; otherwise, !f(x)=True.
4. AND: If f and g are IOI functions, then f&g is an IOI function. For an integer \(x\), f&g returns True if and only if both f(x) and g(x) are True.
5. XOR: If f and g are IOI functions, then f^g is an IOI function. For an integer \(x\), f^g returns True if and only if exactly one of f(x) and g(x) is True.
6. OR: If f and g are IOI functions, then f|g is an IOI function. For an integer \(x\), f|g returns True if and only if at least one of f(x) or g(x) is True.

If an IOI function can be built in several ways, the rule with the largest rule number determines the mapping. For example, [1]&[2]|[3] should be interpreted as ([1]&[2])|[3] (using rule 6 for |) rather than [1]&([2]|[3]). Furthermore, for rules 4, 5, and 6, the left part (f) should be maximized. For instance, [4]^ [5]^ [6] is parsed as ([4]^ [5])^ [6] (applying rule 5 with f = [4]^ [5] rather than f = [4]).

JOI-kun has prepared an IOI function S of length \(N\) for his practice. He will use \(Q\) integers \(X_1, X_2, \dots, X_Q\) to test his computation skills. Your task is to help him compute the value of the IOI function S for each integer \(X_i\): output True or False accordingly.

inputFormat

The input is given in the following format:

N Q
S
X_1
X_2
...
X_Q

Here,

• \(N\) is the length of the string representing the IOI function \(S\).
• \(Q\) is the number of queries.
• \(S\) is the IOI function expressed as a string consisting of tokens [a], !, &, ^, |, and parentheses ( and ).
• Each \(X_i\) is an integer query (\(1 \le X_i \le 10^9\)).

outputFormat

Output \(Q\) lines. The \(i\)-th line should be True if the IOI function \(S\) maps \(X_i\) to True and False otherwise.

sample

5 3
[10]
5
10
15

False
True
True