Transform to Single C

Bessie has found a string \( s \) of length at most \(2\cdot10^5\) that consists only of the letters C, O, and W. She wants to know whether it is possible to transform the string into a single letter C (her favorite) using the following two operations:

1. Choose two adjacent equal letters and delete them.
2. Choose a letter and replace it with any permutation of the other two letters. That is, if the letter is \(X\), it is replaced by the two letters \(Y\) and \(Z\) (with \(\{X,Y,Z\} = \{C,O,W\}\)).

The operations can be applied in any order and any number of times. Note that operation 1 decreases the length of the string by 2 while operation 2 increases it by 1. It turns out that there is an invariant when we assign a weight to each letter. If we define the weight function \(f\) as follows:

[ f(C)=0,\quad f(O)=1,\quad f(W)=1 \quad \text{(in (\mathbb{Z}_2))}, ]

then both operations preserve the value of \(\sum f(\text{letter})\pmod{2}\). Since the target letter C has weight 0, a necessary (and in this problem, sufficient) condition for a string to be transformable to a single C is that the total weight of the string is 0 modulo 2, i.e. the total number of letters among O and W is even.

Bessie is not only interested in the transformation for the entire string \( s \) but also for Q substrings of \( s \). Given \( Q \) queries, each specifying a substring by its endpoints (1-indexed), determine for each query whether the substring can be transformed into a single letter C.

inputFormat

The first line contains the string \( s \) of characters, which is composed only of the letters C, O, and W.

The second line contains an integer \( Q \) (\(1 \le Q \le 2\cdot10^5\)), the number of queries.

Each of the next \( Q \) lines contains two integers \( l \) and \( r \) (1-indexed) representing the endpoints of a substring of \( s \).

outputFormat

For each query, output a line containing YES if the specified substring can be transformed into a single letter C using the allowed operations, and NO otherwise.

sample

COW
3
1 1
1 2
2 3

YES
NO
YES