Binary String Count / Flip Queries

Given a string of 0s and 1s, process the operations in order. flip swaps 0 and 1 throughout the string; count i asks for the number of 0s in the current string from index 0 to i (inclusive).

Standard input/output, this site's supplementary ranges, and the examples follow this problem's description.

输入格式

The first line contains n q (1≤n≤200000, 0≤q≤8000); the second line contains a binary string of length n; then q lines of operations: flip or count i, where 0≤i<n. The ranges of q and the indices are site supplements that make the standard input protocol explicit and keep the standard output within the judge's limit. Indices in operations are counted from 0.

输出格式

Output the counts in the order the queries appear, separated by spaces; if there are no count operations, output an empty line.

样例 1

输入：

7 6
1111010
count 4
count 6
flip
count 4
flip
count 2

输出：

1 2 4 0

样例 2

输入：

4 5
0000
count 0
flip
count 3
flip
count 1

输出：

1 0 2

样例 3

输入：

1 4
1
flip
count 0
flip
count 0

输出：

1 0