Cho một biểu thức boolean gồm ~N~ từ khóa, với ~N~ là số lẻ và các vị trí được đánh số từ ~1~ đến ~N~.

• Ở các vị trí lẻ chỉ xuất hiện true hoặc false.
• Ở các vị trí chẵn chỉ xuất hiện and hoặc or.

Giá trị của biểu thức được tính theo quy tắc ưu tiên toán tử:

• Mọi phép and được thực hiện trước.
• Sau khi không còn and, thực hiện các phép or.

Kujoh có ~Q~ truy vấn. Mỗi truy vấn gồm ~l, r~ và một giá trị boolean ~b~, trong đó ~l, r~ đều là số lẻ và ~1 \le l \le r \le N~.

Với mỗi truy vấn, hãy xóa đoạn từ khóa từ vị trí ~l~ đến vị trí ~r~, rồi thay toàn bộ đoạn đó bằng đúng một từ khóa, có thể là true hoặc false. Cần xác định xem có thể chọn giá trị thay thế sao cho biểu thức mới có kết quả bằng ~b~ hay không.

Yêu cầu

Với mỗi truy vấn, in ~Y~ nếu tồn tại cách thay đoạn ~[l, r]~ bằng một từ khóa true hoặc false để biểu thức còn lại có giá trị bằng ~b~. Ngược lại, in ~N~.

Dữ liệu

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~Q~.
• Dòng thứ hai chứa ~N~ từ khóa mô tả biểu thức.
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l, r~ và một xâu ~b~, trong đó ~b~ là true hoặc false.

Kết quả

In ra một xâu ký tự độ dài ~Q~.

Ký tự thứ ~i~ là:

• ~Y~ nếu truy vấn thứ ~i~ khả thi,
• ~N~ nếu truy vấn thứ ~i~ không khả thi.

Ví dụ

Ví dụ 1

Input

5 7
false and true or true
1 1 false
1 3 true
1 5 false
3 3 true
3 3 false
5 5 false
5 5 true

Output

NYYYNYY

Ví dụ 2

Input

13 4
false or true and false and false and true or true and false
1 5 false
3 11 true
3 11 false
13 13 true

Output

YNYY

Giải thích

Ví dụ 1

Ở truy vấn thứ nhất, nếu thay đoạn ~[1, 1]~ bằng true, biểu thức trở thành true and true or true và cho kết quả true. Nếu thay bằng false, biểu thức vẫn cho kết quả true. Do đó không thể làm cho kết quả bằng false.

Ở truy vấn thứ hai, thay đoạn ~[1, 3]~ bằng true thì biểu thức còn lại cho kết quả true.

Ví dụ 2

Chuỗi kết quả tương ứng với ~4~ truy vấn lần lượt là ~Y, N, Y, Y~.

Ràng buộc và chấm điểm

Ràng buộc

• ~N~ là số lẻ
• ~1 \le l \le r \le N~
• ~l, r~ là số lẻ

Chấm điểm

• Subtask ~1~ ~(50\%):~ ~N, Q \le 100~
• Subtask ~2~ ~(25\%):~ ~N, Q \le 1000~
• Subtask ~3~ ~(25\%):~ ~N, Q \le 2 \cdot 10^5~