Sặc sỡ

Cho một xâu ký tự $S$ có độ dài $N$ chỉ gồm $4$ màu sắc tương ứng với các kí tự G, R, B, Y. Ta định nghĩa "độ sặc sỡ" của một xâu là số lần đổi màu các kí tự trên xâu đó khi xét từ trái qua phải, trong đó màu của kí tự đầu tiên cũng được đếm là một lần. Nói cách khác, độ sặc sỡ là số đoạn liên tiếp lớn nhất gồm các kí tự cùng màu. Ví dụ:

$S=\text{GGBBBGGYRRR}$ gồm $5$ đoạn cùng màu $\text{GG}$, $\text{BBB}$, $\text{GG}$, $\text{Y}$, $\text{RRR}$, nên độ sặc sỡ của xâu trên là $5$.

Cho $Q$ truy vấn có dạng:

1. change L R x: thay đổi xâu con của $S$ từ vị trí $L$ đến $R$ thành xâu con gồm có $1$ kí tự duy nhất là $x$ ($1\le L\le R\le N$), tức là gán $S_L=S_{L+1}=\dots =S_R=x$.
2. get L R: tính độ sặc sỡ của xâu con từ vị trí $L$ đến $R$ ($1\le L\le R\le N$).

Yêu cầu: Thực hiện các truy vấn trên.

Dữ liệu vào

• Dòng đầu tiên gồm $2$ số nguyên dương $N$ và $Q$ ($N,Q\le {10}^5$).
• Dòng thứ hai là một xâu kí tự có độ dài $N$, chỉ gồm các kí tự G, R, B, Y.
• $Q$ dòng tiếp theo, dòng thứ $i$ trong $Q$ dòng mô tả $1$ trong $2$ loại truy vấn trên. Kí tự $x$ thuộc G, R, B, Y. Các vị trí được đánh số từ $1$.

Dữ liệu ra

Với mỗi truy vấn loại $2$, in ra kết quả trên một dòng.

Ràng buộc

• $1\le N,Q\le {10}^5$.
• $1\le L\le R\le N$ trong mọi truy vấn.
• Có $25\%$ số điểm của bài tương ứng với $N,Q\le 1000$.
• Có $25\%$ số điểm của bài tương ứng với không có truy vấn loại $1$.
• Có $25\%$ số điểm của bài tương ứng với truy vấn $1$ có $L=R$ và truy vấn $2$ có $L=1$ và $R=N$.
• Có $25\%$ số điểm của bài tương ứng ràng buộc đề bài.

Ví dụ