Имеется строка \(s\) длиной не более \(2 \cdot 10^5\) символов (только трёх 'C', 'O', 'W').
Требуется узнать, можно ли её превратить в одну букву 'C', используя следующие
операции:
1. Выбрать два соседних одинаковых символа и удалить их.
2. Выбрать один символ и заменить его на два других символа в любом порядке.
В задаче требуется дать ответ для \(Q\) (\(1\le Q\le 2\cdot 10^5\)) подстрок строки \(s\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(s\).
Вторая строка содержит \(Q\).
Каждая из последующих \(Q\) строк содержит два целых числа \(l\) и \(r\) (\(1\le l\le r\le |s|\),
где \(|s|\) означает длину строки \(s\)).
ФОРМАТ ВЫВОДА (на экран / stdout):
Строка длины \(Q\), где \(i\)-ый символ есть 'Y', если \(i\)-ая подстрока может быть сокращена до 'C'.
и 'N' в противном случае.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
COW
6
1 1
1 2
1 3
2 2
2 3
3 3
|
YNNNYN
|