Phép toán trên dãy (Sequence operation)

Nguồn: HDU

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

Đề bài

Duy trì dãy nhị phân với năm thao tác: gán 0, gán 1, đảo bit, đếm số 1 và tìm dãy 1 liên tiếp dài nhất trên đoạn.

Input

Dòng đầu chứa $n,m$, dòng kế chứa $n$ bit. Mỗi thao tác là op a b, chỉ số bắt đầu từ 0.

• 0: gán đoạn thành 0.
• 1: gán đoạn thành 1.
• 2: đảo mọi bit.
• 3: in số bit 1.
• 4: in độ dài dãy 1 liên tiếp dài nhất.

Output

In một dòng cho mỗi thao tác loại 3 hoặc 4.

Subtask

• 20 điểm: $n,m\le50$.
• 30 điểm: $n,m\le5000$.
• 50 điểm: $n,m\le10^5$, $0\le a\le b<n$.

Ví dụ

Input

5 6
0 1 1 0 1
3 0 4
4 0 4
2 1 3
3 0 4
1 0 2
4 0 4

Output

3
2
2
5

Giải thích

Ban đầu có 3 bit 1 và đoạn 1 liên tiếp dài nhất có độ dài 2. Đảo $[1,3]$ tạo 0 0 0 1 1, nên số bit 1 còn 2. Gán $[0,2]$ thành 1 tạo toàn dãy 1 1 1 1 1, nên đáp án cuối là 5.