33620번 - 식당

문제

$a_0[i]=i,ドル $s[i] \in \{ \text{C, P} \}$ $(1 \leq i \leq N),ドル $d_t[i] = \begin{cases} 0 & \text{if } i = 1 \text{ or } s[a_t[i]] \neq s[a_t[i-1]] \\ 1 & \text{otherwise.} \end{cases}$

$a_{t+1}[i]= a_t[\min \{x \mid (\sum_{j=1}^x d_t[j]) = i\}]$ $(1 \leq i \leq \sum d_t)$ 라고 할 때 $s[x]$의 값을 업데이트 하는 쿼리와 $\min \{ t \mid x \not\in a_t \}$의 값을 구하는 쿼리를 처리하라.

식당으로 비유하면 다음과 같다.

식당의 입구에 피돌이 $N$명이 일렬로 식당 쪽을 향해 줄을 서 있다. 식당에 가까운 순으로 1ドル$번 부터 $N$번까지 번호를 매긴다고 할 때 $i$번 피돌이의 바로 앞에 $i-1$번 피돌이가 있다. 각 피돌이들은 C++이나 파이썬중 단 하나의 언어를 쓰며 서로 다른 언어를 쓰는 피돌이들끼리는 보기만 해도 기분이 나빠진다고 한다. 이에 따라 1초마다 다음과 같은 일이 일어난다.

• 맨 앞에 서 있는 피돌이는 줄을 벗어나 식당으로 들어간다.
• 바로 앞에 자신과 다른 언어를 쓰는 피돌이가 있는 피돌이는 기분이 나빠져 줄을 벗어나 집에 간다.

이는 매 초마다 모든 피돌이들에게 동시에 적용된다. 예를 들어 C++를 쓰는 피돌이를 C, 파이썬을 쓰는 피돌이를 P라고 했을 때 줄의 상황은 다음과 같을 수 있다.

당신은 줄의 초기 상태를 알고 있으며, 피돌이들이 줄을 언제 벗어나는지 계산하려고 한다. 그러나 피돌이들이 사용하는 언어에 대한 정보가 잘못되었을 가능성이 있어, 업데이트가 이루어질 수 있다. 즉, 당신의 목표는 다음 쿼리를 처리하는 프로그램을 작성하는 것이다.

• 1ドル$ $x$: $x$번 피돌이가 사용하는 언어에 대한 정보가 바뀐다. 파이썬은 C++로, C++는 파이썬으로 바뀐다.
• 2ドル$ $x$: 현재 알고 있는 정보를 기준으로, $x$번 피돌이가 몇 초째에 줄을 벗어나는지 출력한다. 단, 피돌이들이 실제로 줄 밖으로 나가진 않는다.

입력

첫째 줄에 피돌이의 수와 쿼리의 개수 $N,ドル $Q$가 공백을 두고 주어진다. $(1 \leq N,Q \leq 300\ 000)$

둘째 줄에 줄의 초기 상황을 나타내는 문자열 $S$가 주어진다. $S_i$는 $i$번 피돌이가 사용하는 언어를 나타내며 C는 C++, P는 파이썬을 나타낸다. $(S_i \in \{ $C, P$\})$

다음 $Q$줄에 쿼리가 $a$ $x$의 형식으로 주어진다. $(a \in \{1,2\}; 1 \leq x \leq N)$

2번 쿼리가 하나 이상 주어짐이 보장된다.

출력

2번 쿼리가 주어질 때마다 각 줄에 쿼리의 답을 출력한다.

제한

힌트