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
#include <bits/stdc++.h>
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using ld = long double;
using vi = std::vector<int>;
using pii = std::pair<int, int>;
using vvi = std::vector<vi>;
using vii = std::vector<pii>;
using vll = std::vector<ll>;
using pll = std::pair<ll, ll>;
template <typename T>
int sign(const T& t) {
  return (t > 0) - (t < 0);
}
template <typename T, typename U>
bool remax(T& a, U b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T, typename U>
bool remin(T& a, U b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
T gcd(T a, T b) {
  a = std::abs(a);
  b = std::abs(b);
  while (b) {
    a %= b;
    std::swap(a, b);
  }
  return a;
}
template <typename T>
T lcm(T a, T b) {
  a = std::abs(a);
  b = std::abs(b);
  return a / gcd(a, b) * b;
}
double get_time() { return static_cast<double>(clock()) / CLOCKS_PER_SEC; }
long long current_nanoseconds() {
  return std::chrono::steady_clock::now().time_since_epoch().count();
}
long long default_seed = current_nanoseconds();
uint32_t mrand_32t() {
  static std::mt19937 rng(default_seed);
  return rng();
}
uint64_t mrand_64t() {
  static std::mt19937_64 rng(default_seed);
  return rng();
}
template <typename T>
void make_unique(std::vector<T>& v) {
  std::sort(std::begin(v), std::end(v));
  v.erase(std::unique(std::begin(v), std::end(v)), std::end(v));
}
namespace std {
template <typename A, typename B>
string to_string(const pair<A, B>& p) {
  string str;
  str += "(";
  str += to_string(p.first);
  str += ", ";
  str += to_string(p.second);
  str += ")";
  return str;
}
string to_string(bool value) { return value ? "true" : "false"; }
template <typename T>
string to_string(const vector<T>& vec) {
  string str = "{ ";
  bool first = true;
  for (const auto& it : vec) {
    if (!first) {
      str += ", ";
    }
    str += to_string(it);
    first = false;
  }
  str += " }";
  return str;
}
template <typename T>
string to_string(const set<T>& s) {
  string str = "{ ";
  bool first = true;
  for (const auto& it : s) {
    if (!first) {
      str += ", ";
    }
    str += to_string(it);
    first = false;
  }
  str += " }";
  return str;
}
template <typename K, typename V>
string to_string(const map<K, V>& m) {
  string str = "{ ";
  bool first = true;
  for (const auto& it : m) {
    if (!first) {
      str += ", ";
    }
    first = false;
    str += to_string(it.first);
    str += " -> ";
    str += to_string(it.second);
  }
  str += " }";
  return str;
}
string to_string(const string& s) { return "\"" + s + "\""; }
string to_string(const char* s) { return to_string(string(s)); }
string to_string(char ch) { return "\'" + string(1, ch) + "\'"; }
template <size_t N>
string to_string(const bitset<N>& b) {
  string res(N, '0');
  for (size_t i = 0; i < N; ++i) {
    res[i] = '0' + b[i];
  }
  return res;
}
template <typename T>
string to_string(const T& t) {
  std::stringstream ss;
  ss << t;
  return ss.str();
}
}  // namespace std
void debug_out() { std::cerr << std::endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  std::cerr << " " << std::to_string(H);
  debug_out(T...);
}
using namespace std;
int code(char ch) {
  if (ch == 'R') {
    return 0;
  }
  if (ch == 'P') {
    return 1;
  }
  if (ch == 'S') {
    return 2;
  }
  assert(0);
  return -1;
}
struct query {
  int pos;
  int nw;
  bool read() {
    if (!(cin >> pos)) {
      return 0;
    }
    --pos;
    char ch;
    cin >> ch;
    nw = code(ch);
    return 1;
  }
};
int n;
vi a;
vector<query> qs;
bool read() {
  if (!(cin >> n)) {
    return 0;
  }
  int q;
  cin >> q;
  string s;
  cin >> s;
  assert(int((s).size()) == n);
  a.resize(n);
  for (int i = int(0); i < int(int((s).size())); ++i) {
    a[i] = code(s[i]);
  }
  qs.resize(q);
  for (int i = int(0); i < int(q); ++i) {
    assert(qs[i].read());
  }
  return 1;
}
const int INF = 1e9;
struct node {
  array<int, 3> l{};
  array<int, 3> r;
  array<int, 3> cnt;
  node() { clear(); }
  node(int pos, int c) {
    clear();
    l[c] = pos;
    r[c] = pos;
    cnt[c] = 1;
  }
  void clear() {
    for (int c = int(0); c < int(3); ++c) {
      r[c] = -1;
      l[c] = INF;
      cnt[c] = 0;
    }
  }
  void merge(const node& other) {
    for (int c = int(0); c < int(3); ++c) {
      cnt[c] += other.cnt[c];
      remin(l[c], other.l[c]);
      remax(r[c], other.r[c]);
    }
  }
  void print() const {}
};
struct segm_tree {
  vector<node> t;
  int sz;
  segm_tree(int n = 0) {
    sz = 1;
    while (sz < n) {
      sz *= 2;
    }
    t.resize(sz * 2);
  }
  void put(int v, int tl, int tr, int pos, int val) {
    if (tl == tr) {
      t[v] = node(pos, val);
      return;
    }
    int tm = (tl + tr) >> 1;
    if (pos <= tm) {
      put(v * 2, tl, tm, pos, val);
    } else {
      put(v * 2 + 1, tm + 1, tr, pos, val);
    }
    t[v] = t[v * 2];
    t[v].merge(t[v * 2 + 1]);
  }
  void put(int pos, int val) { put(1, 0, sz - 1, pos, val); }
  node get(int v, int tl, int tr, int l, int r) {
    remin(r, tr);
    remax(l, tl);
    if (l > r) {
      return node();
    }
    if (l == tl && r == tr) {
      return t[v];
    }
    int tm = (tl + tr) >> 1;
    node L = get(v * 2, tl, tm, l, r);
    node R = get(v * 2 + 1, tm + 1, tr, l, r);
    L.merge(R);
    return L;
  }
  node get(int l, int r) { return get(1, 0, sz - 1, l, r); }
};
bool inter(const pii& a, const pii& b) {
  return max(a.first, b.first) < min(a.second, b.second);
}
void solve() {
  segm_tree T(n);
  for (int i = int(0); i < int(n); ++i) {
    T.put(i, a[i]);
  }
  const auto ask = [&]() {
    int ans = 0;
    node z = T.get(0, n - 1);
    for (int C = int(0); C < int(3); ++C) {
      const int bad = (C + 1) % 3;
      const int good = (C + 2) % 3;
      int b = z.l[bad];
      int g = z.l[good];
      vii segs;
      if (b < g) {
        segs.push_back(make_pair(b, g + 1));
      }
      b = z.r[bad];
      g = z.r[good];
      if (g < b) {
        segs.push_back(make_pair(g, b + 1));
      }
      vi cc;
      for (const auto& s : segs) {
        cc.push_back(s.first);
        cc.push_back(s.second);
      }
      cc.push_back(0);
      cc.push_back(n);
      make_unique(cc);
      for (int i = int(0); i < int(int((cc).size()) - 1); ++i) {
        int l = cc[i];
        int r = cc[i + 1];
        pii seg(l, r);
        bool ok = 1;
        for (const auto& s : segs) {
          if (inter(seg, s)) {
            ok = 0;
            break;
          }
        }
        if (!ok) {
          continue;
        }
        node cur = T.get(l, r - 1);
        ans += cur.cnt[C];
      }
    }
    return ans;
  };
  cout << ask() << "\n";
  for (const auto& q : qs) {
    T.put(q.pos, q.nw);
    cout << ask() << "\n";
  }
}
int main() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cout.precision(12);
  cout << fixed;
  while (read()) {
    solve();
  }
  return 0;
}
