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 namespace std;
namespace IO {
const int BUFFER_SIZE = 1 << 15;
char input_buffer[BUFFER_SIZE];
int input_pos = 0, input_len = 0;
char output_buffer[BUFFER_SIZE];
int output_pos = 0;
char number_buffer[100];
uint8_t lookup[100];
void _update_input_buffer() {
  input_len = fread(input_buffer, sizeof(char), BUFFER_SIZE, stdin);
  input_pos = 0;
  if (input_len == 0) input_buffer[0] = EOF;
}
inline char next_char(bool advance = true) {
  if (input_pos >= input_len) _update_input_buffer();
  return input_buffer[advance ? input_pos++ : input_pos];
}
template <typename T>
inline void read_int(T &number) {
  bool negative = false;
  number = 0;
  while (!isdigit(next_char(false)))
    if (next_char() == '-') negative = true;
  do {
    number = 10 * number + (next_char() - '0');
  } while (isdigit(next_char(false)));
  if (negative) number = -number;
}
template <typename T, typename... Args>
inline void read_int(T &number, Args &...args) {
  read_int(number);
  read_int(args...);
}
inline bool isspace(char c) {
  return (unsigned char)(c - '\t') < 5 || c == ' ';
}
inline void read_char(char &c) {
  while (isspace(next_char(false))) next_char();
  c = next_char();
}
inline void read_str(string &str) {
  while (isspace(next_char(false))) next_char();
  str.clear();
  do {
    str += next_char();
  } while (!isspace(next_char(false)));
}
void _flush_output() {
  fwrite(output_buffer, sizeof(char), output_pos, stdout);
  output_pos = 0;
}
inline void write_char(char c) {
  if (output_pos == BUFFER_SIZE) _flush_output();
  output_buffer[output_pos++] = c;
}
template <typename T>
inline void write_int(T number, char after = '\0') {
  if (number < 0) {
    write_char('-');
    number = -number;
  }
  int length = 0;
  while (number >= 10) {
    uint8_t lookup_value = lookup[number % 100];
    number /= 100;
    number_buffer[length++] = (lookup_value & 15) + '0';
    number_buffer[length++] = (lookup_value >> 4) + '0';
  }
  if (number != 0 || length == 0) write_char(number + '0');
  for (int i = length - 1; i >= 0; i--) write_char(number_buffer[i]);
  if (after) write_char(after);
}
void init() {
  bool exit_success = atexit(_flush_output) == 0;
  assert(exit_success);
  for (int i = 0; i < 100; i++) lookup[i] = (i / 10 << 4) + i % 10;
}
}  // namespace IO
struct splay_node {
  splay_node *parent = nullptr, *child[2] = {nullptr, nullptr};
  int size = 1;
  int value;
  static int get_size(splay_node *x) { return x == nullptr ? 0 : x->size; }
  int parent_index() const {
    if (parent == nullptr) return -1;
    return this == parent->child[0] ? 0 : 1;
  }
  void set_child(int index, splay_node *x) {
    child[index] = x;
    if (x != nullptr) x->parent = this;
  }
  void join() { size = get_size(child[0]) + get_size(child[1]) + 1; }
};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count() *
            ((uint64_t) new char | 1));
long long splay_count = 0;
struct splay_tree {
  static const int POOL_SIZE = 10000;
  static vector<splay_node *> node_pool;
  static splay_node *new_node(const int &value) {
    if (node_pool.empty()) {
      splay_node *ptr = new splay_node[POOL_SIZE];
      for (int i = POOL_SIZE - 1; i >= 0; i--) node_pool.push_back(ptr + i);
    }
    splay_node *node = node_pool.back();
    node_pool.pop_back();
    node->value = value;
    return node;
  }
  splay_node *root = nullptr;
  bool empty() const { return root == nullptr; }
  int size() const { return root == nullptr ? 0 : root->size; }
  splay_node *set_root(splay_node *x) {
    if (x != nullptr) x->parent = nullptr;
    return root = x;
  }
  void rotate_up(splay_node *x) {
    splay_node *p = x->parent, *gp = p->parent;
    int index = x->parent_index();
    if (gp == nullptr)
      set_root(x);
    else
      gp->set_child(p->parent_index(), x);
    p->set_child(index, x->child[!index]);
    x->set_child(!index, p);
    p->join();
  }
  void splay(splay_node *x) {
    splay_count++;
    while (x != root) {
      splay_node *p = x->parent;
      if (p != root) rotate_up(x->parent_index() == p->parent_index() ? p : x);
      rotate_up(x);
    }
    x->join();
  }
  static constexpr double LOG_CONSTANT = 2.0;
  static constexpr double SPLAY_PROBABILITY = 0.25;
  static const int SIZE_CUTOFF = 100;
  void check_splay(splay_node *x, int depth) {
    int n = size(), log_n = 32 - __builtin_clz(n);
    if (depth > LOG_CONSTANT * log_n ||
        (n < SIZE_CUTOFF && rng() < SPLAY_PROBABILITY * (rng.max() + 1.0)))
      splay(x);
  }
  pair<splay_node *, int> insert(const int &value,
                                 bool require_unique = false) {
    if (root == nullptr) return {set_root(new_node(value)), 0};
    splay_node *current = root, *prev = nullptr;
    int below = 0, depth = 0;
    bool skip_insert = false;
    while (current != nullptr) {
      prev = current;
      depth++;
      current->size++;
      if (current->value < value) {
        below += splay_node::get_size(current->child[0]) + 1;
        current = current->child[1];
      } else {
        if (require_unique && !(value < current->value)) skip_insert = true;
        current = current->child[0];
      }
    }
    if (skip_insert) {
      for (splay_node *fix_node = prev; fix_node != nullptr;
           fix_node = fix_node->parent)
        fix_node->size--;
      check_splay(prev, depth);
      return {nullptr, below};
    }
    splay_node *x = new_node(value);
    prev->set_child(prev->value < value ? 1 : 0, x);
    check_splay(x, depth);
    return {x, below};
  }
  splay_node *begin() {
    splay_node *x = root;
    int depth = 0;
    while (x->child[0] != nullptr) {
      x = x->child[0];
      depth++;
    }
    check_splay(x, depth);
    return x;
  }
  splay_node *rbegin() {
    splay_node *x = root;
    int depth = 0;
    while (x->child[1] != nullptr) {
      x = x->child[1];
      depth++;
    }
    check_splay(x, depth);
    return x;
  }
  splay_node *successor(splay_node *x) const {
    if (x->child[1] != nullptr) {
      x = x->child[1];
      while (x->child[0] != nullptr) x = x->child[0];
      return x;
    }
    while (x->parent_index() == 1) x = x->parent;
    return x->parent;
  }
  void erase(splay_node *x) {
    splay_node *new_x = nullptr, *fix_node = nullptr;
    if (x->child[0] == nullptr || x->child[1] == nullptr) {
      new_x = x->child[x->child[0] == nullptr ? 1 : 0];
      fix_node = x->parent;
    } else {
      splay_node *next = successor(x);
      assert(next != nullptr && next->child[0] == nullptr);
      new_x = next;
      fix_node = next->parent == x ? next : next->parent;
      next->parent->set_child(next->parent_index(), next->child[1]);
      next->set_child(0, x->child[0]);
      next->set_child(1, x->child[1]);
    }
    if (x == root)
      set_root(new_x);
    else
      x->parent->set_child(x->parent_index(), new_x);
    int depth = 0;
    for (splay_node *node = fix_node; node != nullptr; node = node->parent) {
      node->join();
      depth++;
    }
    if (fix_node != nullptr) check_splay(fix_node, depth);
    *x = splay_node();
    node_pool.push_back(x);
  }
  pair<splay_node *, int> lower_bound(const int &value) {
    splay_node *current = root, *prev = nullptr, *answer = nullptr;
    int below = 0, depth = 0;
    while (current != nullptr) {
      prev = current;
      depth++;
      if (current->value < value) {
        below += splay_node::get_size(current->child[0]) + 1;
        current = current->child[1];
      } else {
        answer = current;
        current = current->child[0];
      }
    }
    if (prev != nullptr) check_splay(prev, depth);
    return make_pair(answer, below);
  }
  bool erase(const int &value) {
    splay_node *x = lower_bound(value).first;
    if (x == nullptr || x->value != value) return false;
    erase(x);
    return true;
  }
  int less_than(const int &value) { return lower_bound(value).second; }
  int less_equal(const int &value) {
    assert(is_integral<int>::value);
    return less_than(value + 1);
  }
  splay_node *node_at_index(int index) {
    if (index < 0 || index >= size()) return nullptr;
    splay_node *current = root;
    int depth = 0;
    while (current != nullptr) {
      int left_size = splay_node::get_size(current->child[0]);
      depth++;
      if (index == left_size) {
        check_splay(current, depth);
        return current;
      }
      if (index < left_size) {
        current = current->child[0];
      } else {
        current = current->child[1];
        index -= left_size + 1;
      }
    }
    assert(false);
  }
};
vector<splay_node *> splay_tree::node_pool;
const string SHAPES = "RPS";
int N, Q;
string shapes;
vector<splay_tree> locations(128);
char get_scared(char c) {
  switch (c) {
    case 'R':
      return 'P';
    case 'P':
      return 'S';
    case 'S':
      return 'R';
  }
  assert(false);
}
char get_likes(char c) {
  switch (c) {
    case 'R':
      return 'S';
    case 'P':
      return 'R';
    case 'S':
      return 'P';
  }
  assert(false);
}
int query_piece_count(char piece, int start, int end) {
  return locations[piece].less_than(end) - locations[piece].less_than(start);
}
int compute_union_count(char piece, int start1, int end1, int start2,
                        int end2) {
  if (end1 - start1 < end2 - start2) {
    swap(start1, start2);
    swap(end1, end2);
  }
  int count = 0;
  if (start1 < end1) count += query_piece_count(piece, start1, end1);
  if (start1 <= start2 && end2 <= end1) return count;
  if (start1 <= start2)
    start2 = max(start2, end1);
  else
    end2 = min(end2, start1);
  if (start2 < end2) count += query_piece_count(piece, start2, end2);
  return count;
}
int possible() {
  int total = 0;
  for (char piece : SHAPES) {
    char scared = get_scared(piece);
    char likes = get_likes(piece);
    int count = locations[piece].size();
    if (locations[scared].empty()) {
      total += count;
      continue;
    }
    int left_start = locations[scared].begin()->value;
    int left_end =
        locations[likes].empty() ? N : locations[likes].begin()->value;
    int right_start =
        locations[likes].empty() ? 0 : locations[likes].rbegin()->value;
    int right_end = locations[scared].rbegin()->value;
    count -= compute_union_count(piece, left_start, left_end, right_start,
                                 right_end);
    total += count;
  }
  return total;
}
int main() {
  IO::init();
  IO::read_int(N, Q);
  IO::read_str(shapes);
  for (int i = 0; i < N; i++) locations[shapes[i]].insert(i);
  for (int q = 0; q <= Q; q++) {
    IO::write_int(possible(), '\n');
    if (q < Q) {
      int index;
      char shape;
      IO::read_int(index);
      IO::read_char(shape);
      index--;
      locations[shapes[index]].erase(index);
      shapes[index] = shape;
      locations[shapes[index]].insert(index);
    }
  }
}
