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

1. Вибрати два сусідніх однакових символи та видалити їх.

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

У задачі потрібно дати відповідь для \(Q\) (\(1\le Q\le 2\cdot 10^5\)) підрядків рядка \(s\).

Формат вхідних даних

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

Другий рядок містить \(Q\).

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

Формат вихідних даних

Рядок довжини \(Q\), де \(i\)-ий символ є 'Y', якщо \(i\)-ий підрядок може бути скорочений до 'C'. і 'N' інакше.

Приклад вхідних даних

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

Приклад вихідних даних

YNNNYN

Відповідь на перший запит 'Y' тому, що перший символ рядка \(s\) вже є 'C'.

Відповідь на п'ятий запит 'Y' тому, що підрядок OW (від 2 до 3 символів \(s\)) може бути конвертована в 'C' за 2 операції:

    OW
-> CWW
-> C

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

ОЦІНЮВАННЯ:

• У тестах 2-4 \(|s|\le 5000\) і \(Q\le 5000\).
• У тестах 5-11 немає додаткових обмежень.