Truy vấn kỳ nghỉ (Vacation Query)

Nguồn: AtCoder

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

Đề bài

Duy trì chuỗi nhị phân với thao tác đảo bit trên đoạn và truy vấn độ dài dãy 1 liên tiếp dài nhất trong một đoạn.

Input

Dòng đầu chứa $N,Q$, dòng thứ hai là chuỗi nhị phân $S$. Mỗi truy vấn c L R:

• 1 L R: đảo bit trên $[L,R]$.
• 2 L R: in độ dài đoạn 1 liên tiếp dài nhất nằm trong $S_L\ldots S_R$.

Output

In một dòng cho mỗi truy vấn loại 2.

Subtask

• 20 điểm: $N,Q\le50$.
• 30 điểm: $N,Q\le5000$.
• 50 điểm: $N\le5\cdot10^5$, $Q\le10^5$.

Ví dụ

Input

7 6
1101110
2 1 7
2 2 4
1 3 6
2 5 6
1 4 7
2 1 7

Output

3
1
0
7

Giải thích

Hai truy vấn đầu cho 3 và 1. Sau khi đảo $[3,6]$, chuỗi thành 1110000, nên $[5,6]$ không có bit 1. Đảo tiếp $[4,7]$ tạo 1111111, vì vậy truy vấn cuối cho 7.