34689번 - Paint It Anything Other Than White

문제

우리는 빛의 3가지 원색 R, G, B을 조합하여 다양한 색을 만들어 낼 수 있다. 이 문제에서는 R, G, B가 이분법적으로 포함되어 있거나, 포함되어 있지 않은 2ドル^3 = 8$가지 색에 대해서만 생각해 보자.

각 색의 R, G, B 포함 여부는 다음과 같다.

두 가지 이상의 색의 합성은, 각 색에 포함된 원색의 집합을 합집합한 색을 의미한다. 예를 들어, 여러 개의 색 중 원색 R을 포함하는 색이 하나라도 있다면 최종 색은 원색 R을 포함하게 된다.

1ドル$부터 $N$까지 번호가 매겨진 $N$개의 칸이 있고, 각 칸은 검정, 빨강, 초록, 파랑, 노랑, 청록, 보라, 흰색 중 하나의 색을 가질 수 있다.

모든 칸은 흰색인 상태에서 시작한다.

이때 다음의 쿼리를 수행하는 프로그램을 작성하시오.

• $Q$ $i$ $j$: $i\le a\le b\le j$를 만족하며, $a,a+1\dots b-1,b$번째 칸을 합성한 색이 흰색이 아닌 $a,b$에 대해 $b-a+1$의 최댓값을 출력한다. 만약 이와 같은 $a,b$가 존재하지 않는다면 0ドル$을 출력한다.
• $U$ $i$ $X$: $i$번째 칸의 색을 $X$로 바꾼다. $X$는 K, R, G, B, Y, C, P, W 중 하나이며, 위 표의 ID에 대응된다.

입력

첫째 줄에 칸의 개수 $N,ドル 쿼리의 개수 $K$가 공백으로 구분되어 주어진다. $(1\le N\le 100,円 000;$ 1ドル \le K \le 200,000円)$

다음 $K$개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 하나씩, 각각의 쿼리의 결과를 순서대로 출력한다.

제한

노트