#pragma GCC optimize("O3,unroll-loops,inline")

#include <bits/stdc++.h>

using namespace std;

vector<pair<char, char>> can = {{' ', ' '},
                                {'d', 'o'},
                                {'r', 'e'},
                                {'m', 'i'},
                                {'f', 'a'},
                                {'s', 'o'},
                                {'l', 'a'},
                                {'t', 'i'}};

bool ok(char c) {
    for (auto i : can)
        if (i.first == c || i.second == c)
            return true;
    return false;
}

bool ok1(char c) {
    for (auto i : can)
        if (i.first == c)
            return true;
    return false;
}

bool ok2(char c) {
    for (auto i : can)
        if (i.second == c)
            return true;
    return false;
}

template<>
struct std::hash<pair<char, char>> {
    int operator() (pair<char, char> p) const {
        return (int)p.first * 256 + p.second;
    }
};

struct node {
    unordered_map<pair<char, char>, pair<int, int>> dp;

    node() = default;

    node(char c) {
        dp[{c, c}] = {0, 1};
        dp[{' ', ' '}] = {1, 0};
    }
};

node operator+(node a, node b) {
    if (a.dp.empty())
        return b;
    if (b.dp.empty())
        return a;
    node c;
    for (auto note: can)
        for (auto [left, r1]: a.dp)
            for (auto [right, r2]: b.dp) {
                if (left.second == note.first && right.first == note.second) {
                    pair<int, int> now = {left.first, right.second};
                    if (r1.second == 1)
                        now.first = ' ';
                    if (r2.second == 1)
                        now.second = ' ';
                    if (c.dp.count(now))
                        c.dp[now] = min(c.dp[now], {r1.first + r2.first, r1.second + r2.second});
                    else
                        c.dp[now] = {r1.first + r2.first, r1.second + r2.second};
                }
                if (r1.second == 0) {
                    if (c.dp.count(right))
                        c.dp[right] = min(c.dp[right], {r1.first + r2.first, r1.second + r2.second});
                    else
                        c.dp[right] = {r1.first + r2.first, r1.second + r2.second};
                }
                if (r2.second == 0) {
                    if (c.dp.count(left))
                        c.dp[left] = min(c.dp[left], {r1.first + r2.first, r1.second + r2.second});
                    else
                        c.dp[left] = {r1.first + r2.first, r1.second + r2.second};
                }
            }
    vector<pair<pair<char, char>, pair<int, int>>> add;
    for (auto i: c.dp) {
        if (i.first.first != ' ')
            add.push_back({{' ',i.first.second},{i.second.first + 1, i.second.second - 1}});
        if (i.first.second != ' ')
            add.push_back({{i.first.first,' '},{i.second.first + 1, i.second.second - 1}});
        if (i.first.second != ' ' && i.first.first != ' ')
            add.push_back({{' ',' '},{i.second.first + 2, max(i.second.second - 2, 0)}});
    }
    for (auto [i, j]: add)
        if (c.dp.count(i))
            c.dp[i] = min(c.dp[i], j);
        else
            c.dp[i] = j;
    vector<pair<pair<char, char>, pair<int, int>>> del;
    for (auto [i, j] : c.dp) {
        if (!ok(i.first) || !ok(i.second))
            del.push_back({i, j});
    }
    for (auto i : del)
        c.dp.erase(i.first);
    return c;
}

const int N = 5e5;

node tr[2 * N];

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    for (int i = 0; i < n; ++i) {
        tr[i + n] = node(s[i]);
    }
    for (int i = n - 1; i; --i) tr[i] = tr[i << 1] + tr[i << 1 | 1];
    while (q--) {
        char t;
        cin >> t;
        if (t == '?') {
            int l, r;
            cin >> l >> r;
            --l, --r;
            node left, right;
            for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
                if (l & 1) left = left + tr[l++];
                if (~r & 1) right = tr[r--] + right;
            }
            cout << (left + right).dp[{' ', ' '}].first << '\n';
        } else {
            int l, r;
            cin >> l >> r;
            --l, --r;
            string ns;
            cin >> ns;
            for (int i = l; i <= r; ++i) {
                tr[i + n] = node(ns[i - l]);
                for (int j = i + n; j > 1; j >>= 1, tr[j] = tr[j << 1] + tr[j << 1 | 1]);
            }
        }
    }
}