Biểu thức logic có thể được định nghĩa truy hồi như sau:

• "true" là một biểu thức logic,
• "false" là một biểu thức logic,
• nếu \(A\) là một biểu thức logic thì \((A)\) cũng là một biểu thức logic,
• nếu \(A\) và \(B\) đều là biểu thức logic thì \(A\) OPERATOR \(B\) là một biểu thức logic.

Ta gọi OPERATOR là một phép toán logic bất kì, trong bài toán này ta chỉ xét OPERATOR là "and" hoặc "or". "and" và "or" đều là phép toán hai ngôi (nhận hai tham số đều là biểu thức logic) và được định nghĩa như sau:

• \(x\) and \(y\) bằng "true" nếu cả \(x\) và \(y\) đều bằng "true", ngược lại bằng "false".
• \(x\) or \(y\) bằng "true" nếu \(x\) hoặc \(y\) bằng "true", ngược lại bằng "false".

Anh nông dân John có một biểu thức logic có dạng \(x_1\) OPERATOR \(x_2\) OPERATOR \(\ldots\) OPERATOR \(x_{(N+1)/2}\) (\(1 \leq N < 2 \times 10^5\), \(N\) lẻ), trong đó \(x_i\) nhận giá trị là "true" hoặc "false" và OPERATOR là phép toán "and" hoặc "or".

Lưu ý là hai phép toán "and" và "or" không có cùng thứ tự ưu tiên. Phép "and" có thứ tự ưu tiên lớn hơn "or", nên thứ tự các phép toán được thực hiện phải là "and" trước, "or" sau.

Nông dân John có \(Q\) câu hỏi (\(1 \leq Q \leq 2 \times 10^3\)). Trong mỗi câu hỏi, anh ấy xóa đoạn từ \(l\) đến \(r\) (\(1 \leq r, l \leq N\), cả \(l\) và \(r\) đều là số lẻ) trong biểu thức. Sau đó anh ấy nhờ bạn thay thế phần biểu thức đã xóa thành "true" hoặc "false" để cả biểu thức sau khi được đánh giá sẽ nhận được kết quả mong muốn. Hãy giúp John nếu có thể!

Input:

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\).
• Dòng thứ 2 chứa biểu thức có độ dài \(N\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l\) và \(r\) và "true" hoặc "false" đại diện cho câu hỏi John đưa ra.

Output:

• In ra một chuỗi có độ dài \(Q\), trong đó vị trí thứ \(i\) là Y nếu câu hỏi thứ \(i\) có thể thực hiện được, ngược lại thì in ra N.

Scoring:

• Subtask 1: \(N, Q \leq {10}^2\)
• Subtask 2: \(N, Q \leq {10}^3\)
• Subtask 3: Không có ràng buộc gì thêm.

Example:

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

NYYYNYY

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

YNYY