Bessie tìm thấy một xâu \(s\) có độ dài tối đa là \(2*10^5\) chỉ chứa ba ký tự C, O và W. Cô ấy muốn biết liệu có thể biến xâu này thành C (chữ cái yêu thích của cô ấy) hay không bằng cách sử dụng các thao tác sau:

• \(1\): Chọn hai chữ cái liền kề giống nhau và xóa.
• \(2\): Chọn một chữ cái và thay thế nó bằng hai chữ cái còn lại theo thứ tự.

Việc tìm câu trả lời trên xâu \(s\) thôi là chưa đủ đối với Bessie, vì vậy cô ấy muốn biết câu trả lời cho \(Q(1 \leq Q\leq 2*10^5)\) xâu con của \(s\).

Input

• Dòng đầu tiên chứa xâu \(s\).
• Dòng tiếp theo chứa số \(Q\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l,r\) \((1\leq l\leq r\leq |s|\), \(|s|\) là độ dài xâu \(s)\).

Output

Một xâu độ dài \(Q\), với ký tự thứ \(i\) là Y nếu xâu con thứ \(i\) có thể biến thành C và N nếu ngược lại.

Scoring

• Subtask \(1\): \(|s|,Q \leq 5000\).
• Subtask \(2\): Không có điều kiện gì thêm.

Example

COW
6
1 1
1 2
1 3
2 2
2 3
3 3

YNNNYN