Truy vấn may mắn (Lucky Queries)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Chuỗi chỉ gồm 4 và 7. Có thể đổi 4 thành 7 và ngược lại trên cả đoạn; truy vấn count hỏi độ dài dãy con không giảm dài nhất.

Input

Dòng đầu chứa $n,m$, dòng thứ hai là chuỗi $s$. Mỗi trong $m$ dòng là:

• switch l r: đổi 4 thành 7 và 7 thành 4 trên $[l,r]$.
• count: in độ dài dãy con không giảm dài nhất của toàn chuỗi.

Output

In một dòng cho mỗi lệnh count.

Subtask

• 20 điểm: $n,m\le50$.
• 30 điểm: $n,m\le5000$.
• 50 điểm: $n\le10^6$, $m\le3\cdot10^5$.

Ví dụ

Input

2 3
47
count
switch 1 2
count

Output

2
1

Giải thích

Ban đầu chuỗi 47 đã không giảm nên đáp án là 2. Sau khi đổi cả đoạn, chuỗi thành 74; mọi dãy con không giảm dài nhất chỉ lấy được một ký tự, nên đáp án là 1.