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 <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <iomanip>
#include <limits.h>
#include <chrono>

#define fast                          \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0);

#define ll long long
#define ld long double

#define pb push_back
#define ins insert
#define er erase

#define f(i, a, b) for (int i = a; i < b; ++i)
#define rf(i, a, b) for (int i = a; i >= b; --i)
#define cmax(a, b) a = max(a, b)
#define cmin(a, b) a = min(a, b)
#define cadd(a, b) a = add(a, b)
#define csub(a, b) a = subt(a, b)
#define cmul(a, b) a = mult(a, b)
#define mem(a, b) memset(a, b, sizeof(a))

#define vi vector<int>
#define vst vector<string>
#define vpii vector<pii>

#define all(v) v.begin(), v.end()
#define lb lower_bound
#define ub upper_bound
#define mxe max_element
#define mne min_element

#define srt(v) sort(all(v))
#define rsrt(v) sort(v.rbegin(), v.rend())

#define pii pair<int, int>
#define ff first
#define ss second

#define bs bitset
#define bpc(a) __builtin_popcount(a)
#define prec(a) fixed << setprecision(a)

#define mii map<int, int>
#define umii unordered_map<int, int>

#define si set<int>
#define usi unordered_set<int>
#define spii set<pii>

#define pqi priority_queue<int>
#define pqpii priority_queue<pii>

#define dbg(a, st, end)                   \
    f(i, st, end + 1) cerr << a[i] << sp; \
    cerr << nl;
#define pnt(a, st, end)                   \
    f(i, st, end + 1) cout << a[i] << sp; \
    cout << nl;
#define dbgc(a)          \
    for (auto y : a)     \
        cerr << y << sp; \
    cerr << nl;
#define dbgm(a)                            \
    for (auto y : a)                       \
        cerr << y.ff << "," << y.ss << sp; \
    cerr << nl;

#define trace(a) cerr << a << nl;
#define trace2(a, b) cerr << a << sp << b << nl;
#define trace3(a, b, c) cerr << a << sp << b << sp << c << nl;
#define trace4(a, b, c, d) cerr << a << sp << b << sp << c << sp << d << nl;

#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a)*1ll * (b)) / gcd(a, b)

#define nl "\n"
#define sp " "

using namespace std;
using namespace std::chrono;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ok order_of_key
#define fo find_by_order

ll md = 1000000007;
ld pi = 3.141592653;
//ll md = 998244353;

ll pw(ll a, ll b)
{
    ll c = 1, m = a;
    while (b)
    {
        if (b & 1)
            c = (c * m);
        m = (m * m);
        b /= 2;
    }
    return c;
}

ll pwmd(ll a, ll b)
{
    ll c = 1, m = a;
    while (b)
    {
        if (b & 1)
            c = (c * m) % md;
        m = (m * m) % md;
        b /= 2;
    }
    return c;
}

ll modinv(ll n)
{
    return pwmd(n, md - 2);
}

ll my_ceil(ll a, ll b)
{
    if (a % b == 0)
        return a / b;
    return a / b + 1;
}

ll nc2(ll n)
{
    return (1ll * n * (n - 1)) / 2;
}

ll nsum(ll n)
{
    return (1ll * n * (n + 1)) / 2;
}

int my_log(ll n, int b)
{
    ll i = 1;
    int ans = 0;
    while (1)
    {
        if (i > n / b)
            break;
        i *= b;
        ans++;
    }
    return ans;
}

inline int nc()
{
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read()
{
    int ret = 0;
    bool f = 0;
    char ch = nc();
    while (ch > '9' || ch < '0')
        f ^= ch == '-', ch = nc();
    while (ch <= '9' && ch >= '0')
        ret = ret * 10 + ch - '0', ch = nc();
    return f ? -ret : ret;
}

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

inline ll add(ll a, ll b) { return (((a >= md) ? a % md : a) + ((b >= md) ? b % md : b) + md) % md; }
inline ll subt(ll a, ll b) { return (a - b + md) % md; }
inline ll mult(ll a, ll b) { return (1ll * ((a >= md) ? a % md : a) * ((b >= md) ? b % md : b)) % md; }

inline int manhatten(pii p1, pii p2) { return abs(p1.ff - p2.ff) + abs(p1.ss - p2.ss); }

inline bool kthbit(ll n, int k) { return (n >> k) & 1; }
inline ll setkthbit(ll n, int k) { return n | (1ll << k); }
inline ll unsetkthbit(ll n, int k) { return n & ~(1ll << k); }
inline ll flipkthbit(ll n, int k) { return n ^ (1ll << k); }

//#define int long long //UNCOMMENT IF NEEDED

/* 
    You have to stop the Q-Tip when there's resistance!
                                - Chandler Bing, S02E01
*/

int32_t main()
{
    fast;

    int h, e, m, k, n;
    int x, q, l, r, y;

    string s, t;

    auto start = high_resolution_clock::now();

    int tcnt = 0;

    int tests = 1;
    //pre();
    //cin >> tests;

    while (tests--)
    {
        //cout << "Case #" << ++tcnt << ": ";

        cin >> n >> q >> s;
        s = "#" + s;
        int dp[255][255][255], nxt[n + 2][26];
        f(i, 0, 26) nxt[n][i] = nxt[n + 1][i] = n + 1;
        rf(i, n - 1, 0)
        {
            f(j, 0, 26) nxt[i][j] = nxt[i + 1][j];
            nxt[i][s[i + 1] - 'a'] = i + 1;
        }
        f(i, 0, 255) f(j, 0, 255) f(k, 0, 255) dp[i][j][k] = n + 1;
        string a = "#", b = "#", c = "#";
        dp[0][0][0] = 0;
        while (q--)
        {
            char ch1, ch2;
            cin >> ch1 >> h;
            if (ch1 == '+')
            {
                cin >> ch2;
                if (h == 1)
                {
                    a.pb(ch2);
                    e = a.size();
                    f(j, 0, b.size()) f(k, 0, c.size()) dp[e - 1][j][k] = n + 1;
                    f(j, 0, b.size()) f(k, 0, c.size())
                    {
                        cmin(dp[e - 1][j][k], nxt[dp[e - 2][j][k]][a.back() - 'a']);
                        if (j)
                            cmin(dp[e - 1][j][k], nxt[dp[e - 1][j - 1][k]][b.back() - 'a']);
                        if (k)
                            cmin(dp[e - 1][j][k], nxt[dp[e - 1][j][k - 1]][c.back() - 'a']);
                    }
                }
                else if (h == 2)
                {
                    b.pb(ch2);
                    e = b.size();
                    f(i, 0, a.size()) f(k, 0, c.size()) dp[i][e - 1][k] = n + 1;
                    f(i, 0, a.size()) f(k, 0, c.size())
                    {
                        cmin(dp[i][e - 1][k], nxt[dp[i][e - 2][k]][b.back() - 'a']);
                        if (i)
                            cmin(dp[i][e - 1][k], nxt[dp[i - 1][e - 1][k]][a.back() - 'a']);
                        if (k)
                            cmin(dp[i][e - 1][k], nxt[dp[i][e - 1][k - 1]][c.back() - 'a']);
                    }
                }
                else
                {
                    c.pb(ch2);
                    e = c.size();
                    f(i, 0, a.size()) f(j, 0, b.size()) dp[i][j][e - 1] = n + 1;
                    f(i, 0, a.size()) f(j, 0, b.size())
                    {
                        cmin(dp[i][j][e - 1], nxt[dp[i][j][e - 2]][c.back() - 'a']);
                        if (i)
                            cmin(dp[i][j][e - 1], nxt[dp[i - 1][j][e - 1]][a.back() - 'a']);
                        if (j)
                            cmin(dp[i][j][e - 1], nxt[dp[i][j - 1][e - 1]][b.back() - 'a']);
                    }
                }
            }
            else
            {
                if (h == 1)
                    a.pop_back();
                else if (h == 2)
                    b.pop_back();
                else
                    c.pop_back();
            }
            cout << ((dp[a.size() - 1][b.size() - 1][c.size() - 1] == (n + 1)) ? "NO\n" : "YES\n");
        }

        // RESTORE SEGTREE SIZE
    }
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);
    cerr << "Time taken: "
         << duration.count() / 1000000.0 << "seconds" << nl;
    return 0;
}
