Patrick is a fan of Maki from Love Live. One day, he decides to go to a Love Live convention, where he hears a string ~S~ of indistinct chanting. This string has length ~N~. Patrick decides to count the maximum number of times MAKI appears as disjoint subsequences in substrings of ~S~. For example, in the string

MMAAKKII

there are two disjoint subsequences of MAKI, so the number of times is ~2~.

Initially, ~S~ is filled with only Zs. However, the string ~S~ 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. 1 l r c All characters in the substring from ~l~ to ~r~ inclusive change to the character ~c~ (~1 \le l \le r \le N~ and ~c~ is an uppercase character)
2. 2 l r Output the maximum number of times MAKI appears as disjoint subsequences in the substring from ~l~ to ~r~ inclusive (~1 \le l \le r \le N~)

~Q~ 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

~N~ represents the length of string ~S~.

Subtask 1 [10%]

~1 \le N \le 200\,000~
~1 \le Q \le 10~

Subtask 2 [90%]

~1 \le N \le 200\,000~
~1 \le Q \le 100\,000~

Input Specification

The first line will contain two integers ~N~ and ~Q~. ~N~ represents the length of string ~S~ and ~Q~ is the number of operations.
The next ~Q~ lines will each contain an operation in the form outlined in the problem statement.

Output Specification

Output the answers to each type ~2~ 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 ~2~ operations are asked, ~S~ is

MAKIMKAKIZ

MAKIMKAKI contains two disjoint MAKIs: the first four letters create one and the fifth, seventh, eighth, and ninth letters form another.
KAKIZ does not contain any MAKIs so the answer for the second query is ~0~.

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