During the archaeological research in the Middle East you found the traces of three ancient religions: First religion, Second religion and Third religion. You compiled the information on the evolution of each of these beliefs, and you now wonder if the followers of each religion could coexist in peace.

The Word of Universe is a long word containing the lowercase English characters only. At each moment of time, each of the religion beliefs could be described by a word consisting of lowercase English characters.

The three religions can coexist in peace if their descriptions form disjoint subsequences of the Word of Universe. More formally, one can paint some of the characters of the Word of Universe in three colors: 1, 2, 3, so that each character is painted in at most one color, and the description of the i-th religion can be constructed from the Word of Universe by removing all characters that aren't painted in color i.

The religions however evolve. In the beginning, each religion description is empty. Every once in a while, either a character is appended to the end of the description of a single religion, or the last character is dropped from the description. After each change, determine if the religions could coexist in peace.

Input

The first line of the input contains two integers n, q (1 ≤ n ≤ 100 000, 1 ≤ q ≤ 1000) — the length of the Word of Universe and the number of religion evolutions, respectively. The following line contains the Word of Universe — a string of length n consisting of lowercase English characters.

Each of the following line describes a single evolution and is in one of the following formats: 

  * + i c (i ∈ \{1, 2, 3\}, c ∈ \{a, b, ..., z\}: append the character c to the end of i-th religion description. 
  * - i (i ∈ \{1, 2, 3\}) – remove the last character from the i-th religion description. You can assume that the pattern is non-empty. 



You can assume that no religion will have description longer than 250 characters.

Output

Write q lines. The i-th of them should be YES if the religions could coexist in peace after the i-th evolution, or NO otherwise.

You can print each character in any case (either upper or lower).

Examples

Input


6 8
abdabc
+ 1 a
+ 1 d
+ 2 b
+ 2 c
+ 3 a
+ 3 b
+ 1 c
- 2


Output


YES
YES
YES
YES
YES
YES
NO
YES


Input


6 8
abbaab
+ 1 a
+ 2 a
+ 3 a
+ 1 b
+ 2 b
+ 3 b
- 1
+ 2 z


Output


YES
YES
YES
YES
YES
NO
YES
NO

Note

In the first example, after the 6th evolution the religion descriptions are: ad, bc, and ab. The following figure shows how these descriptions form three disjoint subsequences of the Word of Universe:

<image>
1 1
t
+ 2 p
 2 12
aa
+ 1 a
+ 2 a
+ 3 a
- 1
+ 1 a
- 2
+ 2 a
- 3
+ 3 a
+ 2 a
- 1
- 3
 2 10
uh
+ 1 h
+ 2 u
+ 3 h
- 1
- 2
+ 2 h
+ 3 u
- 2
+ 1 u
- 3
 1 1
z
+ 3 z

NO
 YES
YES
NO
YES
NO
YES
NO
YES
NO
NO
NO
YES
 YES
YES
NO
YES
YES
NO
NO
NO
NO
YES
 YES

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
namespace io {
class input_reader {
  std::istream &in;
  void throw_error() {
    throw std::runtime_error("No more inputs while reading number");
  }
  template <typename T>
  inline void readIntegerValue(T &f) {
    bool positive = true;
    f = 0;
    char c;
    if (!in.get(c)) throw_error();
    while (c < '0' || c > '9') {
      if (c == '-') positive = false;
      if (!in.get(c)) throw_error();
    }
    while (c >= '0' && c <= '9') {
      f = (f << 3) + (f << 1) + (c & 15);
      if (!in.get(c)) break;
    }
    if (!positive) f *= -1;
  }

 public:
  explicit input_reader(std::istream &in) : in(in) {}
  inline void read(int &f) { readIntegerValue(f); }
  inline void read(short &f) { readIntegerValue(f); }
  inline void read(long int &f) { readIntegerValue(f); }
  inline void read(long long int &f) { readIntegerValue(f); }
  inline void read(unsigned int &f) { readIntegerValue(f); }
  inline void read(unsigned short &f) { readIntegerValue(f); }
  inline void read(unsigned long int &f) { readIntegerValue(f); }
  inline void read(unsigned long long int &f) { readIntegerValue(f); }
  template <typename T>
  inline void read(std::vector<T> &f) {
    for (auto &i : f) read(i);
  }
  template <typename T, int N>
  inline void read(std::array<T, N> &res) {
    for (auto &i : res) read(i);
  }
  template <typename T1, typename T2>
  inline void read(std::pair<T1, T2> &p) {
    in.read(p.first, p.second);
  }
  template <typename T>
  inline void read(T &f) {
    in >> f;
  }
  template <typename T, typename... Args>
  inline void read(T &t, Args &...args) {
    read(t), read(args...);
  }
  template <typename T>
  inline void readArray(int n, T *res) {
    while (n--) read(*(res++));
  }
  template <typename T>
  inline input_reader &operator>>(T &t) {
    return read(t), *this;
  }
};
}  // namespace io
namespace io {
class output_writer {
  std::ostream &out;
  template <typename T>
  inline void printIntegerHelper(T x) {
    if (x >= 10) printIntegerHelper(x / 10);
    out.put(x % 10 + 48);
  }
  template <typename T>
  inline void printInteger(T x) {
    if (x < 0) out.put('-'), x = -x;
    printIntegerHelper(x);
  }
  template <typename T>
  inline void printArray(T &ar) {
    bool first = true;
    for (auto &t : ar) print((first) ? first = false, "" : " ", t);
  }

 public:
  explicit output_writer(std::ostream &out) : out(out) {}
  inline void flush() { out.flush(); }
  inline void print() {}
  inline void print(char x) { out.put(x); }
  inline void print(short x) { printInteger(x); }
  inline void print(int x) { printInteger(x); }
  inline void print(long int x) { printInteger(x); }
  inline void print(long long int x) { printInteger(x); }
  inline void print(unsigned short x) { printInteger(x); }
  inline void print(unsigned int x) { printInteger(x); }
  inline void print(unsigned long int x) { printInteger(x); }
  inline void print(unsigned long long int x) { printInteger(x); }
  template <typename T1>
  inline void print(const T1 &t1) {
    out << t1;
  }
  template <typename T1>
  inline void print(const std::vector<T1> &t1) {
    printArray(t1);
  }
  template <typename T1, int N>
  inline void print(const std::array<T1, N> &t1) {
    printArray(t1);
  }
  template <typename T1, int N, int M>
  inline void print(const std::array<std::array<T1, M>, N> &t1) {
    for (auto &t : t1) println(t);
  }
  template <typename T1>
  inline void print(const std::vector<std::vector<T1>> &t1) {
    for (auto &t : t1) println(t);
  }
  template <typename T, typename... Args>
  inline void print(const T &t, Args... args) {
    print(t), print(args...);
  }
  template <typename... Args>
  inline void println(Args... args) {
    print(args...), print('\n');
  }
  template <typename T>
  output_writer &operator<<(const T &t) {
    return print(t), *this;
  }
};
}  // namespace io
inline long long int pow_mod(long long int a, long long int b,
                             const long long int MOD) {
  long long int res = 1;
  for (long long int i = 1; b; b ^= b & i, i <<= 1, a = (a * a) % MOD)
    if (b & i) res = (res * a) % MOD;
  return res;
}
inline long long int mod_inv(const long long int a, const long long int MOD) {
  return pow_mod(a, MOD - 2, MOD);
}
template <typename T>
inline T gcd(T a, T b) {
  T t;
  while (a != 0) t = a, a = b % a, b = t;
  return b;
}
template <typename T>
T lcm(const T &a, const T &b) {
  assert(a != 0 && b != 0);
  return a / gcd(a, b) * b;
}
using namespace std;
constexpr int A = 26;
constexpr int N = 100100;
constexpr int M = 256;
int n, q;
string s;
string op;
int ind;
string temp_string;
vector<int> desc[3];
int dp[M][M][M];
int next_ocurence[A][N];
void init(const string &s) {
  for (int i = 0; i < M; i++)
    for (int j = 0; j < M; j++)
      for (int k = 0; k < M; k++) dp[i][j][k] = N;
  int nxt[A];
  for (int i = 0; i < A; i++) nxt[i] = N;
  for (int i = (s.size() - 1); i >= (0); --i) {
    nxt[s[i]] = i;
    for (int j = 0; j < A; j++) next_ocurence[j][i] = nxt[j];
  }
  dp[0][0][0] = 0;
}
void reset(int ind) {
  int n1 = desc[0].size(), n2 = desc[1].size(), n3 = desc[2].size();
  if (ind == 1) {
    for (int j = (0); j <= (n2); ++j)
      for (int k = 0; k < n3; k++) dp[n1][j][k] = N;
  } else if (ind == 2) {
    for (int i = (0); i <= (n1); ++i)
      for (int k = (0); k <= (n3); ++k) dp[i][n2][k] = N;
  } else {
    for (int i = (0); i <= (n1); ++i)
      for (int j = (0); j <= (n2); ++j) dp[i][j][n3] = N;
  }
}
void update(int ind) {
  int n1 = desc[0].size(), n2 = desc[1].size(), n3 = desc[2].size();
  for (int i = (ind == 1 ? n1 - 1 : 0); i <= (n1); ++i)
    for (int j = (ind == 2 ? n2 - 1 : 0); j <= (n2); ++j)
      for (int k = (ind == 3 ? n3 - 1 : 0); k <= (n3); ++k)
        if (dp[i][j][k] != N) {
          int v = dp[i][j][k];
          if (v >= s.size()) continue;
          if (i < n1) {
            int nxt = next_ocurence[desc[0][i]][v];
            dp[i + 1][j][k] = min(dp[i + 1][j][k], nxt + 1);
          }
          if (j < n2) {
            int nxt = next_ocurence[desc[1][j]][v];
            dp[i][j + 1][k] = min(dp[i][j + 1][k], nxt + 1);
          }
          if (k < n3) {
            int nxt = next_ocurence[desc[2][k]][v];
            dp[i][j][k + 1] = min(dp[i][j][k + 1], nxt + 1);
          }
        }
}
class BThreeReligions {
  class Solver {
    io::input_reader in;
    io::output_writer out;

   public:
    Solver(std::istream &in, std::ostream &out) : in(in), out(out) {}
    void solve() {
      in >> n >> q >> s;
      for (int i = 0; i < n; i++) s[i] -= 'a';
      init(s);
      while (q--) {
        in >> op >> ind;
        if (op[0] == '-') {
          reset(ind);
          desc[ind - 1].pop_back();
        } else {
          in >> temp_string;
          desc[ind - 1].push_back(temp_string[0] - 'a');
          update(ind);
        }
        if (dp[desc[0].size()][desc[1].size()][desc[2].size()] <= s.size()) {
          out << "YES";
        } else {
          out << "NO";
        }
        out << '\n';
      }
    }
  };

 public:
  void solve(std::istream &in, std::ostream &out) { Solver(in, out).solve(); }
};
int main() {
  std::ios_base::sync_with_stdio(false), cin.tie(0);
  BThreeReligions solver;
  std::istream &in(std::cin);
  std::ostream &out(std::cout);
  solver.solve(in, out);
  return 0;
}
