JOI-kun เรียนอยู่ที่ IOI High School ซึ่งกำลังจะจัดสอบปลายภาค ในการสอบ นักเรียนจะถูกทดสอบว่าสามารถคำนวณค่าของ ฟังก์ชัน IOI ได้อย่างถูกต้องหรือไม่ ฟังก์ชัน IOI คือสตริงที่สร้างขึ้นด้วยหนึ่งในกฎหกข้อต่อไปนี้ที่ IOI High School กำหนด และจับคู่จำนวนเต็มตั้งแต่ $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$ และตั้งใจฝึกหาค่าบูลีนที่ฟังก์ชัน IOI นี้จับคู่จำนวนเต็ม $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{gathered} N\ Q\\ S\\ X_1\\ X_2\\ \vdots\\ X_Q \end{gathered} $$

ข้อมูลส่งออก

พิมพ์ $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