For the first subtask, greedily form prefixes of MAKI. For each type ~2~ operation, loop through the letters and keep track of how many of each prefix can be formed (all at once).

Time Complexity: ~\mathcal O(QN)~

For the second subtask, consider greedily forming substrings of MAKI. For example, if a K is encountered and there is a MA substring, then attach the K to the MA. If not, but there is an A substring, then create the AK substring. If neither of those exist, create the K substring. The number of each substring which may be formed as subsequences over a substring of ~S~ can be represented as a ~4~ by ~4~ array. Now create a segment tree where each node of the segment tree is that ~4~ by ~4~ array for the node's substring of ~S~.

The main difficulty in this solution is merging the ~4~ by ~4~ arrays of two sections of ~S~. Consider the substrings of the left section of ~S~ by prioritizing the starting character of each substring and then prioritizing by length. For each of these substrings, a longer one can be created by using the characters of the right section of ~S~. Now when merging these substrings, it's important that the middle overlap is treated properly. In this case, the middle overlap should be treated as if this substring exists in a section between the left and right section. That is because there is a choice of whether to take the overlap from the left or the right.

Time Complexity: ~\mathcal O(Q\log N)~