Placeholder

#5302

소 연산자 (COW Operations) 2초 1024MB

문제

베시는 최대 2*105길이의 문자열 s를 발견했다. 해당 문자열은 'C', 'O', 'W'만 포함한다.

베시는 이 문자열이 자신이 가장 좋아하는 문자인 'C'로 바뀔 수 있는지 궁금하다.


문자열의 변경 조건은 아래와 같다.

1. 인접한 두 개의 동일한 문자를 삭제한다.

2. 한 문자를 다른 두 문자로 치환한다.


​Q개의 ​s의 부분문자열에 대하여 각각 'C'로 바뀔 수 있는지 출력하시오.

 


입력

첫 번째 줄에 s가 입력된다.

두 번째 줄에 Q가 입력된다. (1<= Q <= 2*105)

세 번째 줄부터 Q줄에 걸쳐 정수 l과 r이 입력된다. (1 <= l <= r <= s의 길이)


출력

Q 길이의 문자열을 출력하시오.

이 때, i번째 문자가 줄어들 수 있으면 i번째 문자를 'Y'로, 아니면 'N'으로 한다.


예제1

입력
COW

6

1 1

1 2

1 3

2 2

2 3

3 3
출력
YNNNYN

다섯 번째 쿼리의 경우 OW인데,

O가 CW로 바뀌어 CWW가 되고,

WW가 삭제되어 C로 변하기 때문에 'Y'가 출력된다.


출처

USACO 2022 US Open Silver


역링크 공식 문제집만

로그인해야 코드를 작성할 수 있어요.