Binary String Requests

You are given a binary string and a sequence of operations. flip swaps every 0 and 1 in the string; count i asks for the number of 0s in the current string from 0 to i (inclusive).

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

输入格式

The first line contains n q (1≤n≤200000, 1≤q≤8000), the second line contains a 0/1 string of length n, followed by q lines of operations flip or count i (0≤i<n). The upper bound on q is a site supplement.

输出格式

Output the answers to all count queries in order on one line, separated by spaces; if there are no count queries, 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 2
1
flip
count 0

输出：

1