JOI-kun לומד בתיכון IOI, שבו תיערך בקרוב בחינת סיום. בבחינה ייבדק אם התלמידים יכולים לחשב נכון את ערכה של פונקציית IOI. פונקציית IOI היא מחרוזת המתקבלת באמצעות אחד מששת הכללים הבאים, שהוגדרו בתיכון IOI. היא ממפה מספרים שלמים בין $1$ ל־$10^9$ כולל לערכים הבוליאניים True או False.

1. יהי $a$ מספר שלם בין $1$ ל־$10^9$ כולל. אז [a] היא פונקציית IOI (כאן a היא המחרוזת המייצגת את $a$ בכתיב עשרוני). פונקציית IOI זו ממפה מספרים שלמים הגדולים מ־$a$ או שווים לו ל־True, ומספרים שלמים הקטנים מ־$a$ ל־False.
2. תהי $f$ פונקציית IOI. אז גם (f) היא פונקציית IOI. פונקציית IOI זו ממפה מספרים שלמים לאותם ערכי True ו־False שאליהם $f$ ממפה אותם.
3. תהי $f$ פונקציית IOI. אז גם !f היא פונקציית IOI. פונקציית IOI זו ממפה מספרים שלמים ש־$f$ ממפה ל־True לערך False, ולהפך.
4. תהיינה $f$ ו־$g$ פונקציות IOI. אז גם f&g היא פונקציית IOI. פונקציית IOI זו ממפה מספר שלם ל־True אם גם $f$ וגם $g$ ממפות אותו ל־True, ול־False אחרת.
5. תהיינה $f$ ו־$g$ פונקציות IOI. אז גם f^g היא פונקציית IOI. פונקציית IOI זו ממפה מספר שלם ל־True אם בדיוק אחת מהפונקציות $f$ ו־$g$ ממפה אותו ל־True, ול־False אחרת.
6. תהיינה $f$ ו־$g$ פונקציות IOI. אז גם f|g היא פונקציית IOI. פונקציית IOI זו ממפה מספר שלם ל־True אם לפחות אחת מהפונקציות $f$ ו־$g$ ממפה אותו ל־True, ול־False אחרת.

אם אפשר לקבל פונקציית IOI באמצעות כמה כללים, הכלל שמספרו גדול יותר קובע את הערך הבוליאני שאליו פונקציית IOI זו ממפה מספר שלם. לדוגמה, עבור [1]&[2]|[3], מפעילים את כלל $6$ על $f=$[1]&[2] ועל $g=$[3] (ולא את כלל $4$ על $f=$[1] ועל $g=$[2]|[3]). נוסף על כך, בכללים $4$, $5$ ו־$6$ מפעילים את הכלל כך ש־$f$ תהיה ארוכה ככל האפשר. לדוגמה, עבור [4]^[5]^[6], מפעילים את כלל $5$ על $f=$[4]^[5] ועל $g=$[6] (ולא את כלל $5$ על $f=$[4] ועל $g=$[5]^[6]).

כדי להתכונן לבחינה, JOI-kun הכין פונקציית IOI בשם $S$ שאורכה $N$, ובכוונתו לתרגל את קביעת הערכים הבוליאניים שאליהם פונקציה זו ממפה $Q$ מספרים שלמים $X_1,X_2,\ldots,X_Q$. מכיוון שאתם מיומנים בטיפול בפונקציות IOI, הוא מבקש את עזרתכם בהכנת פתרון לדוגמה.

כתבו תוכנית שבהינתן $N$, $Q$, $S$ והמספרים $X_1,X_2,\ldots,X_Q$, קובעת את הערכים הבוליאניים שאליהם פונקציית IOI בשם $S$ ממפה את המספרים השלמים $X_1,X_2,\ldots,X_Q$.

קלט

הקלט ניתן מהקלט הסטנדרטי בפורמט הבא:

$$ \begin{array}{l} N\ Q\\ S\\ X_1\\ X_2\\ \vdots\\ X_Q \end{array} $$

פלט

הדפיסו $Q$ שורות לפלט הסטנדרטי. השורה ה־$i$ ($1 \le i \le Q$) צריכה להכיל ערך בוליאני יחיד שאליו פונקציית IOI בשם $S$ ממפה את המספר השלם $X_i$.

מגבלות

• $1 \le N \le 1\,000\,000$.
• $1 \le Q \le 200\,000$.
• $S$ היא פונקציית IOI שאורכה $N$.
• $1 \le X_i \le 10^9$ ($1 \le i \le Q$).
• $N$, $Q$ ו־$X_i$ ($1 \le i \le Q$) הם מספרים שלמים.

תתי־משימות

1. ($5$ נקודות) $S$ אינה מכילה & או |.
2. ($20$ נקודות) $Q=1$.
3. ($10$ נקודות) $N \le 10\,000$.
4. ($6$ נקודות) $S$ אינה מכילה ! או ^.
5. ($12$ נקודות) כאשר מפעילים את כלל $4$ או את כלל $6$ בתהליך קבלת $S$, לפחות אחת מבין $f$ ו־$g$ היא פונקציית IOI שהתקבלה באמצעות כלל $1$.
6. ($20$ נקודות) $N \le 400\,000$.
7. ($27$ נקודות) אין מגבלות נוספות.

דוגמאות

קלט 1

15 5
(![2]|[3])&![4]
1
2
3
4
5

פלט 1

True
False
True
False
False

הסבר

עבור כמה מפונקציות IOI המופיעות בתהליך קבלת $S$ לפי הכללים שבהגדרת הבעיה, הערכים הבוליאניים שאליהם הן ממפות את המספרים השלמים $X_i$ ($1 \le i \le Q$) מוצגים בטבלה הבאה.

קלט לדוגמה זה מקיים את המגבלות של תתי־משימות $3$, $6$ ו־$7$.

קלט 2

20 4
(!![23])^((([116])))
54
1
200
89

פלט 2

True
False
False
True

הסבר

קלט לדוגמה זה מקיים את המגבלות של תתי־משימות $1$, $3$, $5$, $6$ ו־$7$.

קלט 3

32 4
[2]|[5]&[1]|(([1000000000])|[7])
4
10
6
1

פלט 3

True
True
True
False

הסבר

קלט לדוגמה זה מקיים את המגבלות של תתי־משימות $3$, $4$, $6$ ו־$7$.