Patrick is a fan of
Maki from Love Live. One day, he decides to go 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
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 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 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).
~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~
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 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
Explanation for Sample Output 1
When the type ~2~ operations are asked, ~S~ is
MAKIMKAKI contains two disjoint
MAKIs: the first four letters creates 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