Cho 1 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 1 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, ví dụ: ~S = “GGBBBGGYRRR”~ Độ 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~). 2, “get L R” – tính “độ sặc sỡ” của xâu con từ vị trí ~L~ đến ~R~.

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

Input

• Dòng đầu tiên gồm 2 số nguyên dương ~N~ và ~Q~ (~N, Q \le 10^5~).
• Dòng thứ 2 là một xâu kí tự có độ dài ~N~.
• ~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.

Output

• Với mỗi truy vấn loại 2, cần đưa ra kết quả trên mỗi dòng.

Sample Input 1

11 5
GGBBBGGYRRR
get 1 11
get 3 9
get 4 7
change 4 8 B
get 1 11

Sample Output 1

5
4
2
3