A8453 | Lucky Queries

Petya loves lucky numbers very much. Everybody knows that lucky numbers are positive integers whose decimal record contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya brought home string $s$ with the length of $n$ . The string only consists of lucky digits. The digits are numbered from the left to the right starting with $1$ . Now Petya should execute $m$ queries of the following form:

- switch $l$ $r$ — "switch" digits (i.e. replace them with their opposites) at all positions with indexes from $l$ to $r$ , inclusive: each digit $4$ is replaced with $7$ and each digit $7$ is replaced with $4$ $(1<=l<=r<=n)$ ;
- count — find and print on the screen the length of the longest non-decreasing subsequence of string $s$ .

Subsequence of a string $s$ is a string that can be obtained from $s$ by removing zero or more of its elements. A string is called non-decreasing if each successive digit is not less than the previous one.

Help Petya process the requests.

The first line contains two integers $n$ and $m$ ( $1<=n<=10^{6},1<=m<=3·10^{5}$ ) — the length of the string $s$ and the number of queries correspondingly. The second line contains $n$ lucky digits without spaces — Petya's initial string. Next $m$ lines contain queries in the form described in the statement.

For each query count print an answer on a single line.