시험 2

JOI-kun은 IOI 고등학교에 다니고, 곧 기말고사가 치러진다. 시험에서는 IOI 함수의 값을 정확하게 계산할 수 있는지를 평가한다. IOI 함수는 아래 여섯 규칙 중 하나로 만들어지는 문자열이다. 모든 IOI 함수는 $1$ 이상 $10^9$ 이하의 정수 각각을 True 또는 False에 대응시킨다. (1) $a$를 $1$ 이상 $10^9$ 이하의 정수라고 하자. 그러면 [a]는 IOI 함수이다. 여기서 a는 $a$의 십진수 표기이다. 이 함수는 $a$ 이상인 정수를 True에, $a$보다 작은 정수를 False에 대응시킨다. (2) f를 IOI 함수라고 하자. 그러면 (f)도 IOI 함수이며, f와 같은 정수를 True와 False에 대응시킨다. (3) f를 IOI 함수라고 하자. 그러면 !f도 IOI 함수이다. f가 True로 대응시키는 정수는 False로, 그 반대의 정수는 True로 대응시킨다. (4) f와 g를 IOI 함수라고 하자. 그러면 f&g도 IOI 함수이다. 두 함수가 모두 True로 대응시키는 정수는 True로, 나머지는 False로 대응시킨다. (5) f와 g를 IOI 함수라고 하자. 그러면 fˆg도 IOI 함수이다. 둘 중 정확히 하나만 True로 대응시키는 정수는 True로, 나머지는 False로 대응시킨다. (6) f와 g를 IOI 함수라고 하자. 그러면 f|g도 IOI 함수이다. 둘 중 적어도 하나가 True로 대응시키는 정수는 True로, 나머지는 False로 대응시킨다.

하나의 IOI 함수가 여러 규칙으로 만들어지면, 번호가 큰 규칙이 값을 결정한다. 예를 들어 [1]&[2]|[3]에서는 규칙 4를 f = [1], g = [2]|[3]에 적용하지 않고, 규칙 6을 f = [1]&[2], g = [3]에 적용한다. 규칙 4, 5, 6에서는 왼쪽 피연산자 f가 가능한 한 길도록 적용한다. 예를 들어 [4]ˆ[5]ˆ[6]에서는 규칙 5를 f = [4]ˆ[5], g = [6]에 적용한다.

JOI-kun은 길이가 $N$인 IOI 함수 $S$를 가지고 있으며, $S$가 정수 $X_1, X_2, \dots, X_Q$ 각각에 대응시키는 값을 연습하려고 한다. 이 값들을 구하는 프로그램을 작성하라.

입력은 표준 입력으로 다음 형식에 따라 주어진다. 첫째 줄에 $N$과 $Q$가 주어진다. 둘째 줄에 $S$가 주어진다. 이후 $Q$개의 줄에 각각 정수 $X_i$가 하나씩 주어진다.

표준 출력에 $Q$줄을 출력한다. $i$번째 줄에는 $S$가 $X_i$에 대응시키는 참 값인 True 또는 False를 출력한다.

$1 \le N \le 1\,000\,000$. $1 \le Q \le 200\,000$. $S$는 길이가 $N$인 IOI 함수이다. 모든 $1 \le i \le Q$에 대해 $1 \le X_i \le 10^9$이다. $N$, $Q$, 그리고 각 $X_i$는 정수이다.