Patrick is a fan of `Maki`

from Love Live. One day, he decides to go a Love Live convention, where he hears a string of indistinct chanting. This string has length . Patrick decides to count the maximum number of times `MAKI`

appears as disjoint subsequences in substrings of . For example, in the string

MMAAKKII

there are two disjoint subsequences of `MAKI`

, so the number of times is .

Initially, is filled with only `Z`

s. However, the string occasionally changes. To be more precise, all characters in a specific substring are changed to a specific character (for example, `ABCD`

could change to `CCCC`

in a single one of these operations).

To summarize, there are two types of operations Patrick needs to handle:

`1 l r c`

All characters in the substring from to inclusive change to the character ( and is an uppercase character)

`2 l r`

Output the maximum number of times `MAKI`

appears as disjoint subsequences in the substring from to inclusive ()

operations of these two types will be given.

**Tip: If you're trying to solve the second subtask, you should include a line which purposely WAs for the first subtask. This way, your time won't be affected if you WA the second subtask (DMOJ takes the time of the most recent submission which gives the most amount of points).**

#### Constraints

represents the length of string .

##### Subtask 1 [10%]

##### Subtask 2 [90%]

#### Input Specification

The first line will contain two integers and . represents the length of string and is the number of operations.

The next lines will each contain an operation in the form outlined in the problem statement.

#### Output Specification

Output the answers to each type operation on separate lines.

#### Sample Input 1

```
10 10
1 1 9 M
1 2 2 A
1 3 3 K
1 4 4 I
1 6 6 K
1 7 7 A
1 8 8 K
1 9 9 I
2 1 9
2 6 10
```

#### Sample Output 1

```
2
0
```

#### Explanation for Sample Output 1

When the type operations are asked, is

MAKIMKAKIZ

`MAKIMKAKI`

contains two disjoint `MAKI`

s: the first four letters creates one and the fifth, seventh, eighth, and ninth letters form another.
`KAKIZ`

does not contain any `MAKI`

s so the answer for the second query is .

#### Sample Input 2

```
20 5
1 1 5 M
1 6 10 A
1 11 15 K
1 16 20 I
2 2 20
```

#### Sample Output 2

`4`

## Comments