Bò Logic

Farmer John có một biểu thức logic gồm $N$ từ khóa ($1\le N<2\times {10}^5$, $N$ lẻ). Các vị trí lẻ (1, 3, 5, ...) chứa "true" hoặc "false", các vị trí chẵn (2, 4, 6, ...) chứa "and" hoặc "or".

Phép toán "and" có độ ưu tiên cao hơn "or". Biểu thức được tính bằng cách lặp lại: chọn một phép "and" bất kỳ, thay thế ba từ khóa xung quanh (giá trị - and - giá trị) bằng kết quả, cho đến khi chỉ còn một giá trị. Sau đó tính tương tự với "or".

Có $Q$ truy vấn ($1\le Q\le 2\times {10}^5$). Mỗi truy vấn cho hai số lẻ $l$ và $r$ ($1\le l\le r\le N$) và một giá trị mục tiêu "true" hoặc "false". Truy vấn hỏi: liệu có thể xóa đoạn từ khóa $l$ đến $r$ và thay thế bằng đúng một giá trị "true" hoặc "false" sao cho toàn bộ biểu thức có kết quả bằng giá trị mục tiêu?

Dữ liệu vào

• Dòng 1: Hai số nguyên $N$ và $Q$
• Dòng 2: $N$ từ khóa cách nhau bởi dấu cách, tạo thành biểu thức logic hợp lệ
• $Q$ dòng tiếp theo: Hai số nguyên $l$, $r$ (đều lẻ) và một chuỗi "true" hoặc "false"

Dữ liệu ra

Một chuỗi độ dài $Q$, ký tự thứ $i$ là 'Y' nếu truy vấn thứ $i$ khả thi, ngược lại là 'N'.

Ràng buộc

• $3\le N<2\times {10}^5$, $N$ lẻ
• $1\le Q\le 2\times {10}^5$
• Test 3-5: $N,Q\le 100$
• Test 6-8: $N,Q\le 1000$

Ví dụ