Ersel has a string of length \(\mathbf{N}\) is given and there are 2 different operations he has defined on this operation.

**t**oggle \(l\ r\): Inverts all characters from the \(l\)\(^{\mathbf{th}}\) position to the \(r\)\(^{\mathbf{th}}\). (Including \(l\) and \(r\), \(1\)s become \(0\) and \(0\)s come \(1\))**c**ount: Prints the length of the longest non-decreasing subsequence of string.

Ersel spends too much time executing those operations. Can you help Ersel and write a program that executes those operations quickly?

#### Input

The first line contains two integers \(\mathbf{N}\) and \(\mathbf{M}\). These integers indicate the length of the string and the number of queries, respectively.

The second line of input contains a string of length \(\mathbf{N}\) which consists of only "**0**" and "**1**".

Next \(\mathbf{M}\) lines contain the queries **t** and **c**.

- \(1 \leq l \leq r \leq \mathbf{N} \leq 10^{6} \)
- \(1 \leq \mathbf{M} \leq 10^{6} \)

#### Output

For each query **c**ount, print an answer on a single line.

#### Examples

Input 1:

```
2 3
01
c
t 1 2
c
```

Output 1:

```
2
1
```

Input 2:

```
5 5
10101
c
t 2 4
c
t 1 3
c
```

Output 2:

```
3
4
5
```

#### Explanation

- 1
**0**1**01**

The first query is **c**. The longest subsequence is the substring **001** which consists of **2.**, **4.** and **5.** characters of the strings and its length is **3**.

The second query is **t**, and **2** and **4** are given as parameters. After numbers from **2.** position to **4.** position is inverted, the string becomes **11011**.

**11**0**11**

The third query is **c**. The longest subsequence is the substring **1111** which consists of **1.**, **2.**, **4.** and **5.** characters of the strings and its length is **4**.

The fourth query is **t**, and **1** and **3** are given as parameters. After numbers from **1.** position to **3.** position is inverted, the string becomes **00111**.

**00111**

The fifth and the last query is **c**. The longest subsequence is the substring **00111** which consists of all characters of the strings and its length is **5**.