#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

#define el '\n'
#define FIO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef complex<ld> pt;
typedef unsigned long long ull;

template<typename T, typename X>
using hashTable = gp_hash_table<T, X>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

// mt19937_64 for long long
mt19937 rng(std::chrono::system_clock::now().time_since_epoch().count());

const int N = 1e6 + 5, P1 = 29, P2 = 31, MOD1 = 1e9 + 7, MOD2 = 1e9 + 9;
int pw1[N], inv1[N], pw2[N], inv2[N];
int prefixPW1[N], prefixPW2[N];

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

int sub(int a, int b, int mod)
{
    return ((a - b) % mod + mod) % mod;
}

int mul(int a, int b, int mod)
{
    return 1ll * a * b % mod;
}

int fp(int base, int power, int mod)
{
    if(!power)
        return 1;

    int ret = fp(base, power >> 1, mod);
    ret = mul(ret, ret, mod);

    if(power & 1)
        ret = mul(ret, base, mod);

    return ret;
}

struct Hash
{
    vector<pair<int, int>> prefix;

    Hash(const string &s)
    {
        prefix.resize(s.size() + 1);
        for(int i = 0; i < int(s.size()); ++i)
            prefix[i + 1] = make_pair(add(prefix[i].first, mul(pw1[i], s[i] - 'a' + 1, MOD1), MOD1),
                                      add(prefix[i].second, mul(pw2[i], s[i] - 'a' + 1, MOD2), MOD2));
    }

    int size() const
    {
        return prefix.size() - 1;
    }

    pair<int, int> getHash() const
    {
        return prefix.back();
    }

    pair<int, int> getRange(int l, int r) const
    {
        return make_pair(mul(inv1[l], sub(prefix[r + 1].first, prefix[l].first, MOD1), MOD1),
                         mul(inv2[l], sub(prefix[r + 1].second, prefix[l].second, MOD2), MOD2));
    }

    static void prepare()
    {
        pw1[0] = inv1[0] = pw2[0] = inv2[0] = prefixPW1[0] = prefixPW2[0] = 1;
        int iv1 = fp(P1, MOD1 - 2, MOD1);
        int iv2 = fp(P2, MOD2 - 2, MOD2);
        for(int i = 1; i < N; ++i)
        {
            pw1[i] = mul(pw1[i - 1], P1, MOD1);
            prefixPW1[i] = add(pw1[i], prefixPW1[i - 1], MOD1);

            pw2[i] = mul(pw2[i - 1], P2, MOD2);
            prefixPW2[i] = add(pw2[i], prefixPW2[i - 1], MOD2);

            inv1[i] = mul(inv1[i - 1], iv1, MOD1);
            inv2[i] = mul(inv2[i - 1], iv2, MOD2);
        }
    }
};

struct Node
{
    pair<int, int> hash;
};

struct segTree
{
    int len;
    vector<Node> tree;
    Node neutral = Node({{0, 0}});
    vector<pair<int, int>> lazy;

    segTree(int n)
    {
        len = n;
        int sz = 1;
        while(sz < n)
            sz *= 2;

        tree = vector<Node>(2 * sz);
        lazy = vector<pair<int, int>>(2 * sz, {-1, -1});
    }

    Node single(int s, int e, char val)
    {
        Node ret;
        ret.hash.first = mul(val - 'a' + 1, pw1[s], MOD1);
        ret.hash.second = mul(val - 'a' + 1, pw2[s], MOD2);
        return ret;
    }

    Node merge(Node a, Node b)
    {
        Node ret;
        ret.hash.first = add(a.hash.first, b.hash.first, MOD1);
        ret.hash.second = add(a.hash.second, b.hash.second, MOD2);
        return ret;
    }

    void propagate(int node, int s, int e)
    {
        if(lazy[node].first == -1)
            return;

        tree[node].hash.first = mul(lazy[node].first, sub(prefixPW1[e], prefixPW1[s - 1], MOD1), MOD1);
        tree[node].hash.second = mul(lazy[node].second, sub(prefixPW2[e], prefixPW2[s - 1], MOD2), MOD2);

        if(s != e)
        {
            lazy[node * 2] = lazy[node];
            lazy[node * 2 + 1] = lazy[node];
        }
        lazy[node] = {-1, -1};
    }

    void build(int node, int s, int e, string &st)
    {
        if(s == e)
        {
            tree[node] = single(s, e, st[s - 1]);
            return;
        }

        int mid = (s + e) >> 1;

        build(node * 2, s, mid, st);
        build(node * 2 + 1, mid + 1, e, st);

        tree[node] = merge(tree[node * 2], tree[node * 2 + 1]);
    }

    void update(int node, int s, int e, int l, int r, int val)
    {
        propagate(node, s, e);

        if(s > r || e < l)
            return;

        if(s >= l && e <= r)
        {
            tree[node].hash.first = mul(val, sub(prefixPW1[e], prefixPW1[s - 1], MOD1), MOD1);
            tree[node].hash.second = mul(val, sub(prefixPW2[e], prefixPW2[s - 1], MOD2), MOD2);
            if(s != e)
            {
                lazy[node * 2] = {val, val};
                lazy[node * 2 + 1] = {val, val};
            }

            lazy[node] = {-1, -1};
            return;
        }

        int mid = (s + e) >> 1;

        update(node * 2, s, mid, l, r, val);
        update(node * 2 + 1, mid + 1, e, l, r, val);

        tree[node] = merge(tree[node * 2], tree[node * 2 + 1]);
    }

    pair<Node, int> query(int node, int s, int e, Hash &tHash)
    {
        if(s > tHash.size())
            return {neutral, 0};

        propagate(node, s, e);
        if(s == e)
        {
            auto A = tHash.getRange(s - 1, e - 1);
            auto B = tree[node].hash;
            B.first = mul(B.first, inv1[s], MOD1);
            B.second = mul(B.second, inv2[s], MOD2);
            if(A == B)
                return {tree[node], 1};
            else
                return {neutral, 0};
        }

        int m = (s + e) >> 1;
        auto u = query(node * 2, s, m, tHash);

        auto A = tHash.getRange(s - 1, m - 1);
        auto B = u.first.hash;
        B.first = mul(B.first, inv1[s], MOD1);
        B.second = mul(B.second, inv2[s], MOD2);

        if(A == B)
        {
            auto v = query(2 * node + 1, m + 1, e, tHash);
            return make_pair(merge(u.first, v.first), u.second + v.second);
        }
        else
            return u;
    }

    Node query2(int node, int s, int e, int l, int r)
    {
        if(s > r || e < l)
            return neutral;

        propagate(node, s, e);

        if(s >= l && e <= r)
            return tree[node];

        int m = (s + e) >> 1;

        Node u = query2(node * 2, s, m, l, r);
        Node v = query2(node * 2 + 1, m + 1, e, l, r);

        return merge(u, v);
    }
} st(0);

vector<Hash> v;

bool cmp(int idx)
{
    Hash &t = v[idx];
    auto x = st.query(1, 1, st.len, t);

    int res = x.second + 1;
    if(res <= min(st.len, t.size()))
    {
        auto A = t.getRange(res - 1, res - 1);
        auto B = st.query2(1, 1, st.len, res, res).hash;
        B.first = mul(B.first, inv1[res], MOD1);
        if(A.first > B.first)
            return false;
        return true;
    }
    else
    {
        if(st.len > t.size())
            return true;
        return false;
    }
}

int getAns()
{
    int s = 0, e = v.size() - 1, mid, res = -1;
    while(s <= e)
    {
        mid = (s + e) >> 1;
        if(cmp(mid))
            s = mid + 1, res = mid;
        else
            e = mid - 1;
    }
    return res + 1;
}

void doWork()
{
    int n, q;
    string str;
    cin >> n >> q >> str;

    st = segTree(str.length());
    st.build(1, 1, str.length(), str);

    vector<string> x(n);
    for(int i = 0; i < n; i++)
        cin >> x[i];


    sort(x.begin(), x.end());
    for(int i = 0; i < n; i++)
        v.emplace_back(Hash(x[i]));

    cout << getAns() << '\n';

    char c;
    int idx;
    while(q--)
    {
        cin >> idx >> c;
        st.update(1, 1, str.length(), idx, str.length(), c - 'a' + 1);
        cout << getAns() << '\n';
    }
}

signed main()
{
    FIO
    Hash::prepare();
    int T = 1;
//    cin >> T;
    for(int i = 1; i <= T; i++)
        doWork();
}