Có một chiếc xe taxi tự lái trên một đường phố dài ở Innopolis. Đường phố này có \(n+1\) điểm dừng taxi và \(n\) đoạn đường nối các điểm dừng liền nhau. Trên mỗi đoạn đường có một cây đèn đường. Nếu cây đèn thứ \(i\) bật sáng, nó chiếu sáng đoạn đường nối điểm dừng thứ \(i\) và điểm dừng thứ \(i+1\). Ngược lại, đoạn đường này bị tối.

Để đảm bảo an toàn, xe taxi tự lái chỉ có thể chạy trên các đoạn đường được chiếu sáng. Hay nói cách khác, xe taxi có thể chạy từ điểm dừng \(a\) tới điểm dừng \(b\) (\(a<b\)) nếu các đoạn đường nằm giữa \(a\) và \(a+1\), \(a+1\) và \(a+2\), \(\ldots\), \(b-1\) và \(b\) được chiếu sáng tại thời điểm đó.

Sau khi bị hỏng hoặc sửa chữa, các cây đèn đường có thể bật hoặc tắt. Bạn được cho trạng thái ban đầu của các cây đèn đường tại thời điểm \(0\). Sau đó, có các sự kiện diễn ra vào thời điểm cuối của các giờ \(1,2,\ldots,q\). Có chính xác một sự kiện diễn ra vào thời điểm cuối của mỗi giờ. Có hai loại sự kiện:

• toggle \(i\) — cây đèn thứ \(i\) chuyển trạng thái: nếu nó đang bật thì nó sẽ được tắt; nếu nó đang tắt thì nó sẽ được bật.
• query \(a\) \(b\) — trưởng phòng taxi tự lái muốn biết tổng số giờ từ thời điểm \(0\) tới thời điểm hiện tại mà chiếc xe taxi có khả năng lái từ điểm dừng \(a\) tới điểm dừng \(b\).

Hãy giúp trưởng phòng taxi tự lái trả lời các câu hỏi này.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(1\le n,q\le 300\,000\)) — số lượng cây đèn và số lượng sự kiện.

Dòng thứ hai chứa một xâu kí tự \(s\) mô tả trạng thái ban đầu của các cây đèn (\(|s|=n\)). \(s_i\) là 1 nếu cây đèn thứ \(i\) đang bật, và \(s_i\) là 0 nếu cây đèn thứ \(i\) đang tắt.

Mỗi dòng trong \(q\) dòng tiếp theo mô tả các sự kiện. Dòng thứ \(i\) mô tả một sự kiện sẽ diễn ra sau giờ \(i\).

• toggle \(i\) (\(1\le i\le n\)) — cây đèn thứ \(i\) đổi trạng thái.
• query \(a\) \(b\) (\(1\le a<b\le n+1\)) — tính số lượng giờ cho đến thời điểm hiện tại mà taxi có thể lái từ điểm dừng \(a\) đến điểm dừng \(b\).

Ít nhất một trong các sự kiện là query.

Dữ liệu ra

Với mỗi sự kiện query, in ra một số nguyên là đáp án cho câu hỏi.

Phân nhóm

Ví dụ

5 7
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6

1
2
0
0
1
2

Giải thích

Trong ví dụ này:

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2019, được lưu trong kho đề APIO.