n players are going to play a rock-paper-scissors tournament. As you probably know, in a one-on-one match of rock-paper-scissors, two players choose their shapes independently. The outcome is then determined depending on the chosen shapes: "paper" beats "rock", "rock" beats "scissors", "scissors" beat "paper", and two equal shapes result in a draw.

At the start of the tournament all players will stand in a row, with their numbers increasing from 1 for the leftmost player, to n for the rightmost player. Each player has a pre-chosen shape that they will use in every game throughout the tournament. Here's how the tournament is conducted:

  * If there is only one player left, he is declared the champion.
  * Otherwise, two adjacent players in the row are chosen arbitrarily, and they play the next match. The losing player is eliminated from the tournament and leaves his place in the row (with his former neighbours becoming adjacent). If the game is a draw, the losing player is determined by a coin toss.



The organizers are informed about all players' favoured shapes. They wish to find out the total number of players who have a chance of becoming the tournament champion (that is, there is a suitable way to choose the order of the games and manipulate the coin tosses). However, some players are still optimizing their strategy, and can inform the organizers about their new shapes. Can you find the number of possible champions after each such request?

Input

The first line contains two integers n and q — the number of players and requests respectively (1 ≤ n ≤ 2 ⋅ 10^5, 0 ≤ q ≤ 2 ⋅ 10^5).

The second line contains a string of n characters. The i-th of these characters is "R", "P", or "S" if the player i was going to play "rock", "paper", or "scissors" before all requests respectively.

The following q lines describe the requests. The j-th of these lines contain an integer p_j and a character c_j meaning that the player p_j is going to use the shape described by the character c_j from this moment (1 ≤ p_j ≤ n).

Output

Print q + 1 integers r_0, …, r_q, where r_k is the number of possible champions after processing k requests.

Example

Input


3 5
RPS
1 S
2 R
3 P
1 P
2 P


Output


2
2
1
2
2
3
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author prakharjain
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        DRockPaperScissorsChampion solver = new DRockPaperScissorsChampion();
        solver.solve(1, in, out);
        out.close();
    }

    static class DRockPaperScissorsChampion {
        int tp = 0;
        int tr = 0;
        int ts = 0;

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.nextInt();

            int q = in.nextInt();

            StringBuilder s = new StringBuilder(in.next());

            int[] ra = new int[n];
            int[] pa = new int[n];
            int[] sa = new int[n];

            for (int i = 0; i < n; i++) {
                if (s.charAt(i) == 'R') {
                    ra[i] = 1;
                    tr++;
                } else if (s.charAt(i) == 'P') {
                    pa[i] = 1;
                    tp++;
                } else {
                    sa[i] = 1;
                    ts++;
                }
            }

            SegmentTree sr = new SegmentTree(n);
            sr.build(0, ra, 0, n - 1);

            SegmentTree sp = new SegmentTree(n);
            sp.build(0, pa, 0, n - 1);

            SegmentTree ss = new SegmentTree(n);
            ss.build(0, sa, 0, n - 1);

            int i = -1;
            do {
                if (i >= 0) {
                    int p = in.nextInt();
                    char ch = in.nextCharacter();

                    p--;
                    if (s.charAt(p) != ch) {
                        if (s.charAt(p) == 'R') {
                            ra[p] = 0;
                            tr--;
                            sr.update(0, 0, n - 1, p, 0);
                        } else if (s.charAt(p) == 'P') {
                            pa[p] = 0;
                            sp.update(0, 0, n - 1, p, 0);
                        } else {
                            sa[p] = 0;
                            ss.update(0, 0, n - 1, p, 0);
                        }

                        if (ch == 'R') {
                            ra[p] = 1;
                            sr.update(0, 0, n - 1, p, 1);
                        } else if (ch == 'P') {
                            pa[p] = 1;
                            sp.update(0, 0, n - 1, p, 1);
                        } else {
                            sa[p] = 1;
                            ss.update(0, 0, n - 1, p, 1);
                        }

                        s.setCharAt(p, ch);
                    }
                }

                int ans = n;

                ans -= cal(pa, sp, sa, ss, ra, sr, n);
                ans -= cal(ra, sr, pa, sp, sa, ss, n);
                ans -= cal(sa, ss, ra, sr, pa, sp, n);

                out.println(ans);

                i++;
            } while (i < q);
        }

        int cal(int[] fa, SegmentTree fs, int[] sa, SegmentTree ss, int[] ta, SegmentTree ts, int n) {

            int tf = ts.first(0, 0, n - 1);

            if (tf == -1) {
                int sf = ss.first(0, 0, n - 1);
                if (sf == -1) {
                    return 0;
                } else {
                    return fs.query(0, 0, n - 1, 0, n - 1);
                }
            }

            int tl = ts.last(0, 0, n - 1);

            int sf = ss.first(0, 0, n - 1);

            int ans = 0;
            if (sf != -1 && sf < tf) {
                ans += fs.query(0, 0, n - 1, sf, tf);
            }

            int sl = ss.last(0, 0, n - 1);

            if (sl > tl) {
                ans += fs.query(0, 0, n - 1, tl, sl);
            }

            return ans;

//        long scnt = ts.query(0, 0, n - 1, 0, n - 1);
//
//        if (scnt == 0) {
//            long tcnt = ss.query(0, 0, n - 1, 0, n - 1);
//            if (tcnt == 0) {
//                return 0;
//            } else
//                return (int) fs.query(0, 0, n - 1, 0, n - 1);
//        }
//
//        int ans = 0;
//        int ind2 = -1;
//        if (sa[0] == 1) {
//            int lo = 0;
//            int hi = n - 1;
//
//            int ind = -1;
//            while (lo <= hi) {
//                int mid = (lo + hi) / 2;
//
//                long cnt = ss.query(0, 0, n - 1, 0, mid);
//
//                if (cnt == mid + 1) {
//                    lo = mid + 1;
//                    ind = mid;
//                } else {
//                    hi = mid - 1;
//                }
//            }
//
//            if (ind < n - 1 && fa[ind + 1] == 1) {
//                lo = ind + 1;
//                hi = n - 1;
//
//                ind2 = ind + 1;
//                while (lo <= hi) {
//                    int mid = (lo + hi) / 2;
//
//                    long cnt = fs.query(0, 0, n - 1, ind + 1, mid);
//
//                    if (cnt == mid - ind) {
//                        lo = mid + 1;
//                        ind2 = mid;
//                    } else {
//                        hi = mid - 1;
//                    }
//                }
//
//                ans += (ind2 - ind);
//            }
//        }
//
//
//        if (sa[n - 1] == 1) {
//            int lo = 0;
//            int hi = n - 1;
//
//            int ind = n;
//            while (lo <= hi) {
//                int mid = (lo + hi) / 2;
//
//                long cnt = ss.query(0, 0, n - 1, mid, n - 1);
//
//                if (cnt == n - mid) {
//                    hi = mid - 1;
//                    ind = mid;
//                } else {
//                    lo = mid + 1;
//                }
//            }
//
//            if (ind > 0 && fa[ind - 1] == 1 && ind2 < ind - 1) {
//                lo = 0;
//                hi = ind - 1;
//
//                int ind3 = ind - 1;
//                while (lo <= hi) {
//                    int mid = (lo + hi) / 2;
//
//                    long cnt = fs.query(0, 0, n - 1, mid, ind - 1);
//
//                    if (cnt == ind - mid) {
//                        hi = mid - 1;
//                        ind3 = mid;
//                    } else {
//                        lo = mid + 1;
//                    }
//                }
//
//                ans += (ind - ind3);
//            }
//        }
//
//        return ans;
        }

        class SegmentTree {
            int[] st;
            int n;

            public SegmentTree(int n) {
                st = new int[4 * n];
                this.n = n;
            }

            void build(int i, int[] a, int r1, int r2) {
                if (r1 == r2) {
                    st[i] = a[r1];
                } else {
                    build(i * 2 + 1, a, r1, (r1 + r2) / 2);
                    build(i * 2 + 2, a, (r1 + r2) / 2 + 1, r2);

                    st[i] = st[i * 2 + 1] + st[i * 2 + 2];
                }
            }

            int query(int i, int ra, int rb, int r1, int r2) {
                if (ra > r2 || rb < r1) {
                    return 0;
                }

                if (ra >= r1 && rb <= r2) {
                    return st[i];
                }

                int p1 = query(i * 2 + 1, ra, (ra + rb) / 2, r1, r2);
                int p2 = query(i * 2 + 2, (ra + rb) / 2 + 1, rb, r1, r2);

                return p1 + p2;
            }

            int update(int i, int ra, int rb, int ind, int val) {
                if (ra == rb && rb == ind) {
                    st[i] = val;
                    return st[i];
                }

                if (ra > ind || rb < ind) {
                    return st[i];
                }

                int p1 = update(i * 2 + 1, ra, (ra + rb) / 2, ind, val);
                int p2 = update(i * 2 + 2, (ra + rb) / 2 + 1, rb, ind, val);

                return st[i] = p1 + p2;
            }

            int first(int i, int ra, int rb) {
                if (ra == rb) {
                    if (st[i] > 0)
                        return ra;
                    else return -1;
                }

                if (st[i * 2 + 1] > 0) {
                    return first(i * 2 + 1, ra, (ra + rb) / 2);
                } else {
                    return first(i * 2 + 2, (ra + rb) / 2 + 1, rb);
                }
            }

            int last(int i, int ra, int rb) {
                if (ra == rb) {
                    if (st[i] > 0)
                        return ra;
                    else return -1;
                }

                if (st[i * 2 + 2] > 0) {
                    return last(i * 2 + 2, (ra + rb) / 2 + 1, rb);
                } else {
                    return last(i * 2 + 1, ra, (ra + rb) / 2);
                }
            }

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void close() {
            writer.close();
        }

        public void println(int i) {
            writer.println(i);
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public String nextString() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                if (Character.isValidCodePoint(c)) {
                    res.appendCodePoint(c);
                }
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public char nextCharacter() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            return (char) c;
        }

        public String next() {
            return nextString();
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}

