#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

#define fi first
#define se second
#define pp push_back
#define all(x) (x).begin(), (x).end()
#define Ones(n) __builtin_popcount(n)
#define endl '\n'
#define mem(arrr, xx) memset(arrr,xx,sizeof arrr)
#define PI acos(-1)
//#define int long long
#define debug(x) cout << (#x) << " = " << x << endl

void Gamal() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef Clion
    freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#endif
}

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

const int N = 1e6 + 5, M = 1e9 + 7;
int pw[2][N], inv[2][N], pre[2][N], P[2];

int mul(int a, int b) {
    a = (a % M + M) % M;
    b = (b % M + M) % M;
    return 1ll * a * b % M;
}

int add(int a, int b) {
    a = (a % M + M) % M;
    b = (b % M + M) % M;
    return (a + b) % M;
}

int fp(int b, int p) {
    if (!p)return 1;
    int ret = fp(b, p >> 1);
    ret = mul(ret, ret);
    if (p & 1)ret = mul(ret, b);
    return ret;
}

void build() {
    pw[0][0] = pw[1][0] = inv[0][0] = inv[1][0] = pre[0][0] = pre[1][0] = 1;
    int in[2];
    P[0] = 31, P[1] = 37;
    in[0] = fp(P[0], M - 2);
    in[1] = fp(P[1], M - 2);
    for (int i = 1; i < N; ++i) {
        for (int j = 0; j < 2; ++j) {
            pw[j][i] = mul(pw[j][i - 1], P[j]);
            inv[j][i] = mul(inv[j][i - 1], in[j]);
            pre[j][i] = add(pre[j][i - 1], pw[j][i]);
        }
    }
}

struct Hash {
    vector<pii> prefix;

    Hash() {

    }

    Hash(string &s) {
        prefix = vector<pii>(s.size(), {0, 0});
        for (int i = 0; i < s.size(); ++i) {
            prefix[i].fi = mul(s[i] - 'a' + 1, pw[0][i]);
            prefix[i].se = mul(s[i] - 'a' + 1, pw[1][i]);
            if (i) {
                prefix[i].fi = add(prefix[i].fi, prefix[i - 1].fi);
                prefix[i].se = add(prefix[i].se, prefix[i - 1].se);
            }
        }
    }

    pii getRange(int l,int r){
        return {mul(add(prefix[r].fi,-(l ? prefix[l-1].fi:0)),inv[0][l]),
                mul(add(prefix[r].se,-(l ? prefix[l-1].se:0)),inv[1][l])
        };
    }
};


struct SEG{
    pii h={0,0};
    int lz = -1;
    SEG(){

    }
    SEG(pii hh){
        h = hh;
    }
};

struct segTree{
    vector<SEG>seg;
    int sz = 1,n,NO_OP = -1;
    segTree(int nn){
        n = nn;
        while (sz < nn)
            sz *= 2;
        seg.assign(2 * sz,SEG());
    }

    SEG merge(SEG s1,SEG s2){
        SEG ret;
        ret.h.fi = add(s1.h.fi,s2.h.fi);
        ret.h.se = add(s1.h.se,s2.h.se);
        return ret;
    }

    void push(int x,int lx,int rx){
        if(seg[x].lz == NO_OP)return;
        seg[x].h.fi = mul(seg[x].lz, add(pre[0][rx],-(lx ? pre[0][lx-1]:0)));
        seg[x].h.se = mul(seg[x].lz, add(pre[1][rx],-(lx ? pre[1][lx-1]:0)));
        int lf = 2*x+1,rt=2*x+2;
        if(lx != rx){
            seg[lf].lz = seg[x].lz;
            seg[rt].lz = seg[x].lz;
        }
        seg[x].lz = NO_OP;
    }

    void update(int l,int r,int v,int x,int lx,int rx){
        push(x,lx,rx);
        if(l > rx || r < lx)return;
        if(l <= lx && r >= rx){
            seg[x].lz = v;
            push(x,lx,rx);
            return;
        }
        int mid = (lx + rx)/2,lf = 2*x+1,rt=2*x+2;
        update(l,r,v,lf,lx,mid);
        update(l,r,v,rt,mid+1,rx);
        seg[x] = merge(seg[lf],seg[rt]);
    }

    void update(int l,int r,int v){
        update(l,r,v,0,0,n-1);
    }

    SEG query(int l,int r,int x,int lx,int rx){
        push(x,lx,rx);
        if(l <= lx && r >= rx)
            return seg[x];
        if(l > rx || r < lx)
            return SEG();
        int mid = (lx + rx)/2,lf = 2*x+1,rt=2*x+2;
        return merge(query(l,r,lf,lx,mid), query(l,r,rt,mid+1,rx));
    }
    SEG query(int l,int r){
        return query(l,r,0,0,n-1);
    }

};

void solve() {
    int n,q;cin >> n >> q;
    string s;cin >> s;
    vector<string>v(n);
    vector<Hash>h(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
    sort(all(v));
    for (int i = 0; i < n; ++i) h[i] = Hash(v[i]);
    int ptr = -1;
    for (int i = 0; i < n; ++i) {
        if(s > v[i])ptr = i;
        else break;
    }

    segTree st(s.size());
    for (int i = 0; i < s.size(); ++i) {
        st.update(i,i,s[i] - 'a' + 1);
    }
    cout << ptr + 1 << endl;
    while (q--){
        int i;cin >> i;
        char c;cin >> c;
        i--;
        // first i such that s[0,i-1] == v[0,i-1]
        int l = 0,r = n - 1,match = (i ? -1:1);

        if(i){
            int lx = 0,rx = max(ptr,0);
            while (lx <= rx){
                int mid = (lx + rx)/2;
                if(v[mid].size() < i){
                    lx = mid + 1;
                    continue;
                }
                pii a = h[mid].getRange(0,i-1);
                pii b = st.query(0,i-1).h;
                if(a == b){
                    l = mid;
                    match = 1;
                    rx = mid - 1;
                }
                else lx = mid + 1;
            }
            lx = max(ptr,0),rx = n - 1;
            while (lx <= rx){
                int mid = (lx + rx)/2;
                if(v[mid].size() < i){
                    rx = mid - 1;
                    continue;
                }
                pii a = h[mid].getRange(0,i-1);
                pii b = st.query(0,i-1).h;
                if(a == b){
                    match = 1;
                    r = mid;
                    lx = mid + 1;
                }
                else rx = mid - 1;
            }
        }

        if(match != -1){
            ptr = l - 1;
            while (l <= r){
                int mid = (l + r)/2;
                int lx = 1,rx = min(s.size(),v[mid].size()) - i,f = -1;
                while (lx <= rx){
                    int m2 = (lx + rx)/2;
                    pii a = h[mid].getRange(i,i+m2-1);
                    pii b = {mul(pre[0][m2-1], c - 'a' + 1), mul(pre[1][m2-1],c - 'a' + 1)};
                    if(a == b){
                        lx = m2 + 1;
                    }
                    else{
                        f = m2;
                        rx = m2 - 1;
                    }
                }
                if(~f){
                    if(v[mid][i+f-1] > c){
                        r = mid - 1;
                    }
                    else{
                        ptr = mid;
                        l = mid + 1;
                    }
                }
                else{
                    if(v[mid].size() >= s.size()){
                        r = mid - 1;
                    }
                    else{
                        ptr = mid;
                        l = mid + 1;
                    }
                }
            }
        }
        st.update(i,s.size()-1,c-'a'+1);
        cout << ptr + 1 << endl;
    }

}


signed main() {
    Gamal();
    build();
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}