Бессі знаходить рядок ~s~ довжиною не більше ~2\cdot 10^5~, який містить лише три символи 'C', 'O' та 'W'. Вона хоче дізнатися, чи можна перетворити цей рядок в одне єдине 'C' (її улюблений символ), використовуючи такі операції:

1. Оберіть два прилеглих однакових символи та видаліть їх.

2. Оберіть один символ та замініть його на два інших символи у будь-якому порядку.

Знаходження відповіді на самому рядку не є достатнім для Бессі, тому вона хоче знати відповідь для ~Q~ (~1 \le Q \le 2\cdot 10^5~) підрядків рядка ~s~.

Input

Перший рядок містить ~s~.

Наступний рядок містить ~Q~.

Наступні ~Q~ рядків кожен містить два цілих числа ~l~ та ~r~ (~1 \le l \le r \le |s|~, де ~|s|~ позначає довжину ~s~).

Output

Рядок довжиною ~Q~, де ~i~-й символ буде 'Y', якщо ~i~-й підрядок може бути скорочений, та 'N' у протилежному випадку.

Sample Input 1

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

Sample Output 1

YNNNYN

Notes

Відповідь на перший запит - так, оскільки перший символ ~s~ вже дорівнює 'C'.

Відповідь на п'ятий запит - так, оскільки підрядок OW від другого до третього символу ~s~ може бути перетворений на 'C' за допомогою двох операцій:

   OW
-> CWW
-> C

Інші підрядки цього прикладного рядка COW не можуть бути скорочені до 'C'.