G. Cut and Splice
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Dr. Zarif is studying the genome of a certain prokaryote and has developed an ingenious gene editing technology called the Lateral Omni-genomic Precision Integration and Targeting Apparatus and Laboratory (LOPITAL) to assist him.

An RNA strand is a string of nucleotides that are represented by one of the characters "A", "U", "C", or "G" which can be either circular or linear. For the organism that he is currently studying, Dr. Zarif is more interested in the number of linear RNA strands and doesn't care about circular RNA.

Dr. Zarif is planning to carry out some tests on the organism's genome, which is initially a single circular strand of RNA with $$$n$$$ nucleotides. Using LOPITAL, Dr. Zarif will do $$$q$$$ cumulative operations on the RNA, where each operation is one of the following types:

  • CUT: LOPITAL cuts all RNA strands between every consecutive occurrence of nucleotides $$$x$$$ and $$$y$$$. As a result of this operation, circular RNA strands may become linear, and linear RNA may separate into two or more different strands.

  • SPLICE: LOPITAL splices two different RNA strands wherever one of them ends with nucleotide $$$x$$$ and the other begins with nucleotide $$$y$$$. Only linear RNA can be spliced since circular RNA does not have a beginning or an end. LOPITAL can splice strands in any order but will keep splicing until no strands satisfy the above condition.

Note that since RNA strands are not bidirectional, cuts between $$$x$$$ and $$$y$$$ are not the same as between $$$y$$$ and $$$x$$$, and similarly for splices.

Dr. Zarif is interested in knowing the maximum possible number of linear RNA strands that could exist after each operation. Given the nucleotide sequence of the original circular RNA strand and the $$$q$$$ operations he performs, help Dr. Zarif compute these values.

Input

The first line of the input will contain the integers $$$n$$$, $$$q$$$ ($$$1 \leq n, q \leq 2 \cdot 10^5$$$).

The second line will contain a string of length $$$n$$$ consisting of RNA nucleotides: the RNA strand used by Dr. Zarif.

The next $$$q$$$ lines each contain one operation that Dr. Zarif performs. An operation is described with three strings $$$t$$$, $$$x$$$, and $$$y$$$.

If $$$t$$$ is the string "CUT", then Dr. Zarif will use LOPITAL to make a cut between nucleotides $$$x$$$ and $$$y$$$.

If $$$t$$$ is the string "SPLICE", then Dr. Zarif will use LOPITAL to splice strands between nucleotides $$$x$$$ and $$$y$$$.

Output

Print $$$q$$$ lines, where the $$$i$$$-th line contains the maximum possible number of linear strands after the first $$$i$$$ operations.

Examples
Input
9 4
GGAAUGUCA
CUT U C
CUT G G
SPLICE U G
CUT A G
Output
1
2
1
2
Input
20 10
GAAUUCAUAUUCAGGCGGCC
SPLICE C G
CUT U C
SPLICE G U
CUT U A
SPLICE C A
SPLICE G G
SPLICE U C
CUT G U
SPLICE C U
CUT A U
Output
0
2
2
3
3
3
1
1
1
4
Note

In the first sample test case, the operations have the following effects.

  1. Convert the circular strand "CAGGAAUGU" into a linear strand.
  2. Split the linear strand "CAGGAAUGU" into "CAG" and "GAAUGU".
  3. Convert the linear strand "GAAUGU" into a circular strand.
  4. Split the linear strand "CAG" into "CA" and "G".