#pragma GCC optimize("Ofast")

#include "bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
#define rep1n(i, n) for (int i = 1; i <= (n); ++i)
#define repr(i, n) for (int i = (n) - 1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define each(x, a) for (auto &x : a)
#define ar array
#define vec vector
#define range(i, n) rep(i, n)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vi>;

int Bit(int mask, int b) { return (mask >> b) & 1; }

template<class T>
bool ckmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool ckmax(T &a, const T &b) {
    if (b > a) {
        a = b;
        return true;
    }
    return false;
}

// [l, r)
template<typename T, typename F>
T FindFirstTrue(T l, T r, const F &predicat) {
    --l;
    while (r - l > 1) {
        T mid = l + (r - l) / 2;
        if (predicat(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    return r;
}


template<typename T, typename F>
T FindLastFalse(T l, T r, const F &predicat) {
    return FindFirstTrue(l, r, predicat) - 1;
}

namespace SPARSE {
#ifndef __OY_CATTREE__
#define __OY_CATTREE__
    namespace OY {
        namespace CAT {
            using size_type = uint32_t;
            template <typename Tp, typename Operation>
            struct BaseMonoid {
                using value_type = Tp;
                static value_type op(const value_type &x, const value_type &y) { return Operation()(x, y); }
            };
            template <typename Tp, typename Compare>
            struct ChoiceByCompare {
                Tp operator()(const Tp &x, const Tp &y) const { return Compare()(x, y) ? y : x; }
            };
            template <typename Tp, Tp (*Fp)(Tp, Tp)>
            struct FpTransfer {
                Tp operator()(const Tp &x, const Tp &y) const { return Fp(x, y); }
            };
            template <typename Monoid, size_t MAX_LEVEL = 30>
            class Table {
            public:
                using monoid = Monoid;
                using value_type = typename Monoid::value_type;
            private:
                std::vector<value_type> m_sub[MAX_LEVEL];
                size_type m_size, m_depth;
                void _update(size_type i) {
                    auto sub = m_sub[0].data();
                    for (size_type j = 1, k = 4; j != m_depth; j++, k <<= 1) {
                        auto cur = m_sub[j].data();
                        size_type l = i & -(1 << (j + 1));
                        if (i >> j & 1) {
                            size_type j = i, end = std::min(l + k, m_size);
                            cur[j] = (j == l + (k >> 1)) ? sub[j] : Monoid::op(cur[j - 1], sub[j]);
                            while (++j != end) cur[j] = Monoid::op(cur[j - 1], sub[j]);
                        } else {
                            if (m_size <= l + k / 2) continue;
                            size_type j = i + 1;
                            cur[j - 1] = (j == l + (k >> 1)) ? sub[j - 1] : Monoid::op(sub[j - 1], cur[j]);
                            while (--j != l) cur[j - 1] = Monoid::op(sub[j - 1], cur[j]);
                        }
                    }
                }
            public:
                Table() = default;
                template <typename InitMapping>
                Table(size_type length, InitMapping mapping) { resize(length, mapping); }
                template <typename Iterator>
                Table(Iterator first, Iterator last) { reset(first, last); }
                template <typename InitMapping>
                void resize(size_type length, InitMapping mapping) {
                    if (!(m_size = length)) return;
                    m_depth = m_size == 1 ? 1 : std::bit_width(m_size - 1);
                    for (size_type i = 0; i != m_depth; i++) m_sub[i].resize(m_size);
                    auto sub = m_sub[0].data();
                    for (size_type i = 0; i != m_size; i++) sub[i] = mapping(i);
                    for (size_type j = 1, k = 4, l; j != m_depth; j++, k <<= 1) {
                        auto cur = m_sub[j].data();
                        for (l = 0; l + k <= m_size; l += k) {
                            size_type i = l + (k >> 1);
                            cur[i - 1] = sub[i - 1];
                            while (--i != l) cur[i - 1] = Monoid::op(sub[i - 1], cur[i]);
                            i = l + (k >> 1);
                            cur[i] = sub[i];
                            while (++i != l + k) cur[i] = Monoid::op(cur[i - 1], sub[i]);
                        }
                        if (l != m_size && (l + (k >> 1) < m_size)) {
                            size_type i = l + (k >> 1);
                            cur[i - 1] = sub[i - 1];
                            while (--i != l) cur[i - 1] = Monoid::op(sub[i - 1], cur[i]);
                            i = l + (k >> 1);
                            cur[i] = sub[i];
                            while (++i != m_size) cur[i] = Monoid::op(cur[i - 1], sub[i]);
                        }
                    }
                }
                template <typename Iterator>
                void reset(Iterator first, Iterator last) {
                    resize(last - first, [&](size_type i) { return *(first + i); });
                }
                size_type size() const { return m_size; }
                void modify(size_type i, value_type val) { m_sub[0][i] = val, _update(i); }
                value_type query(size_type i) const { return m_sub[0][i]; }
                value_type query(size_type left, size_type right) const {
                    if (left == right) return m_sub[0][left];
                    size_type d = std::bit_width(left ^ right) - 1;
                    return Monoid::op(m_sub[d][left], m_sub[d][right]);
                }
                value_type query_all() const { return query(0, m_size - 1); }
                template <typename Judger>
                size_type max_right(size_type left, Judger &&judge) const {
                    value_type val = m_sub[0][left];
                    if (!judge(val)) return left - 1;
                    if (++left == m_size) return left - 1;
                    size_type d = std::bit_width(left ^ (m_size - 1));
                    while (d && left < m_size) {
                        size_type split = (left & -(1 << (d - 1))) | (1 << (d - 1));
                        if (m_size <= split)
                            while (--d && (left >> (d - 1) & 1)) {}
                        else {
                            value_type a = Monoid::op(val, m_sub[d - 1][left]);
                            if (judge(a))
                                val = a, --d, left = split;
                            else
                                while (--d && (left >> (d - 1) & 1)) {}
                        }
                    }
                    if (left < m_size && judge(Monoid::op(val, m_sub[0][left]))) left++;
                    return std::min(left, m_size) - 1;
                }
                template <typename Judger>
                size_type min_left(size_type right, Judger &&judge) const {
                    value_type val = m_sub[0][right];
                    if (!judge(val)) return right + 1;
                    if (!right--) return right + 1;
                    size_type d = std::bit_width(right);
                    while (d) {
                        value_type a = Monoid::op(m_sub[d - 1][right], val);
                        if (judge(a))
                            val = a, --d, right = (right & -(1 << d)) - 1;
                        else
                            while (--d && !(right >> (d - 1) & 1)) {}
                    }
                    if (!(right & 1) && judge(Monoid::op(m_sub[0][right], val))) right--;
                    return right + 1;
                }
            };
            template <typename Ostream, typename Monoid, size_t MAX_LEVEL>
            Ostream &operator<<(Ostream &out, const Table<Monoid, MAX_LEVEL> &x) {
                out << "[";
                for (size_type i = 0; i != x.size(); i++) {
                    if (i) out << ", ";
                    out << x.query(i);
                }
                return out << "]";
            }
        }
        template <typename Tp, size_t MAX_LEVEL = 30, typename Operation, typename InitMapping, typename TreeType = CAT::Table<CAT::BaseMonoid<Tp, Operation>, MAX_LEVEL>>
        auto make_CatTree(CAT::size_type length, Operation op, InitMapping mapping) -> TreeType { return TreeType(length, mapping); }
        template <size_t MAX_LEVEL = 30, typename Iterator, typename Operation, typename Tp = typename std::iterator_traits<Iterator>::value_type, typename TreeType = CAT::Table<CAT::BaseMonoid<Tp, Operation>, MAX_LEVEL>>
        auto make_CatTree(Iterator first, Iterator last, Operation op) -> TreeType { return TreeType(first, last); }
        template <typename Tp, size_t MAX_LEVEL = 30>
        using CatMaxTable = CAT::Table<CAT::BaseMonoid<Tp, CAT::ChoiceByCompare<Tp, std::less<Tp>>>, MAX_LEVEL>;
        template <typename Tp, size_t MAX_LEVEL = 30>
        using CatMinTable = CAT::Table<CAT::BaseMonoid<Tp, CAT::ChoiceByCompare<Tp, std::greater<Tp>>>, MAX_LEVEL>;
        template <typename Tp, size_t MAX_LEVEL = 30>
        using CatGcdTable = CAT::Table<CAT::BaseMonoid<Tp, CAT::FpTransfer<Tp, std::gcd<Tp>>>, MAX_LEVEL>;
        template <typename Tp, size_t MAX_LEVEL = 30>
        using CatLcmTable = CAT::Table<CAT::BaseMonoid<Tp, CAT::FpTransfer<Tp, std::lcm<Tp>>>, MAX_LEVEL>;
        template <typename Tp, size_t MAX_LEVEL = 30>
        using CatBitAndTable = CAT::Table<CAT::BaseMonoid<Tp, std::bit_and<Tp>>, MAX_LEVEL>;
        template <typename Tp, size_t MAX_LEVEL = 30>
        using CatBitOrTable = CAT::Table<CAT::BaseMonoid<Tp, std::bit_or<Tp>>, MAX_LEVEL>;
        template <typename Tp, size_t MAX_LEVEL = 30>
        using CatBitXorTable = CAT::Table<CAT::BaseMonoid<Tp, std::bit_xor<Tp>>, MAX_LEVEL>;
        template <typename Tp, size_t MAX_LEVEL = 30>
        using CatSumTable = CAT::Table<CAT::BaseMonoid<Tp, std::plus<Tp>>, MAX_LEVEL>;
    }
#endif
#ifndef __OY_SQRTTREE__
#define __OY_SQRTTREE__
    namespace OY {
        namespace SQRT {
            using size_type = uint32_t;
            using CAT::BaseMonoid;
            using CAT::ChoiceByCompare;
            using CAT::FpTransfer;
            template <size_type BlockSize = 16>
            struct StaticController {
                void reserve(size_type capacity) {}
                static constexpr bool is_first(size_type i) { return i % BlockSize == 0; }
                static constexpr size_type block_id(size_type i) { return i / BlockSize; }
                static constexpr size_type block_first(size_type i) { return i / BlockSize * BlockSize; }
                static constexpr size_type block_size() { return BlockSize; }
                static constexpr size_type block_count(size_type length) { return (length + BlockSize - 1) / BlockSize; }
            };
            template <size_type DefaultDepth = 5>
            struct RandomController {
                size_type m_mask = (1 << DefaultDepth) - 1, m_depth = DefaultDepth;
                void reserve(size_type capacity) { m_depth = (std::bit_width(capacity) - 1) / 2, m_mask = (1 << m_depth) - 1; }
                bool is_first(size_type i) const { return !(i & m_mask); }
                size_type block_id(size_type i) const { return i >> m_depth; }
                size_type block_first(size_type i) const { return i & ~m_mask; }
                size_type block_size() const { return m_mask + 1; }
                size_type block_count(size_type length) const { return (length + m_mask) >> m_depth; }
            };
            template <size_type DefaultDepth = 5>
            struct NonRandomController {
                size_type m_mask = (1 << DefaultDepth) - 1, m_depth = DefaultDepth;
                void reserve(size_type capacity) { m_depth = capacity >= 32 ? std::bit_width<size_type>(std::bit_width(capacity / std::bit_width(capacity)) - 1) : (std::bit_width(capacity) - 1) / 2, m_mask = (size_type(1) << m_depth) - 1; }
                bool is_first(size_type i) const { return !(i & m_mask); }
                size_type block_id(size_type i) const { return i >> m_depth; }
                size_type block_first(size_type i) const { return i & ~m_mask; }
                size_type block_size() const { return m_mask + 1; }
                size_type block_count(size_type length) const { return (length + m_mask) >> m_depth; }
            };
            template <typename Monoid, typename Controller = RandomController<>, size_t MAX_LEVEL = 30>
            class Table {
            public:
                using monoid = Monoid;
                using value_type = typename Monoid::value_type;
                using inner_table = CAT::Table<Monoid, MAX_LEVEL>;
            private:
                inner_table m_table;
                std::vector<value_type> m_data, m_prefix, m_suffix;
                size_type m_size;
                Controller m_ctrl;
                template <typename Judger>
                size_type _max_right(size_type left, size_type end, Judger &&judge) const {
                    value_type val = m_data[left];
                    if (judge(val))
                        while (++left != end) {
                            value_type a = Monoid::op(val, m_data[left]);
                            if (!judge(a)) break;
                            val = a;
                        }
                    return left - 1;
                }
                template <typename Judger>
                size_type _max_right2(size_type left, size_type end, Judger &&judge) const {
                    size_type low = left, high = end;
                    while (low != high) {
                        size_type mid = (low + high) / 2;
                        if (judge(m_prefix[mid]))
                            low = mid + 1;
                        else
                            high = mid;
                    }
                    return low - 1;
                }
                template <typename Judger>
                size_type _min_left(size_type end, size_type right, Judger &&judge) const {
                    value_type val = m_data[right];
                    if (judge(val))
                        while (--right != end) {
                            value_type a = Monoid::op(m_data[right], val);
                            if (!judge(a)) break;
                            val = a;
                        }
                    return right + 1;
                }
                template <typename Judger>
                size_type _min_left2(size_type end, size_type right, Judger &&judge) const {
                    size_type low = end, high = right;
                    while (low != high) {
                        size_type mid = (low + high + 1) / 2;
                        if (judge(m_suffix[mid]))
                            high = mid - 1;
                        else
                            low = mid;
                    }
                    return low + 1;
                }
                void _update(size_type i) {
                    size_type cur = m_ctrl.block_first(i), nxt = std::min(cur + m_ctrl.block_size(), m_size);
                    m_prefix[i] = (i == cur) ? m_data[i] : Monoid::op(m_prefix[i - 1], m_data[i]);
                    for (size_type j = i + 1; j != nxt; j++) m_prefix[j] = Monoid::op(m_prefix[j - 1], m_data[j]);
                    m_suffix[i] = (i == nxt - 1) ? m_data[i] : Monoid::op(m_data[i], m_suffix[i + 1]);
                    for (size_type j = i - 1; j != cur - 1; j--) m_suffix[j] = Monoid::op(m_data[j], m_suffix[j + 1]);
                    m_table.modify(m_ctrl.block_id(i), m_suffix[cur]);
                }
            public:
                Table() = default;
                template <typename InitMapping>
                Table(size_type length, InitMapping mapping) { resize(length, mapping); }
                template <typename Iterator>
                Table(Iterator first, Iterator last) { reset(first, last); }
                size_type size() const { return m_size; }
                template <typename InitMapping>
                void resize(size_type length, InitMapping mapping) {
                    if (!(m_size = length)) return;
                    m_ctrl.reserve(m_size);
                    m_data.resize(m_size);
                    for (size_type i = 0; i != m_size; i++) m_data[i] = mapping(i);
                    m_prefix = m_suffix = m_data;
                    for (size_type i = 1; i != m_size; i++)
                        if (!m_ctrl.is_first(i)) m_prefix[i] = Monoid::op(m_prefix[i - 1], m_prefix[i]);
                    for (size_type i = m_size - 1; i; i--)
                        if (!m_ctrl.is_first(i)) m_suffix[i - 1] = Monoid::op(m_suffix[i - 1], m_suffix[i]);
                    m_table.resize(m_ctrl.block_count(m_size), [&](size_type i) { return m_suffix[i * m_ctrl.block_size()]; });
                }
                template <typename Iterator>
                void reset(Iterator first, Iterator last) {
                    resize(last - first, [&](size_type i) { return *(first + i); });
                }
                void modify(size_type i, value_type val) { m_data[i] = val, _update(i); }
                value_type query(size_type i) const { return m_data[i]; }
                value_type query(size_type left, size_type right) const {
                    size_type l = m_ctrl.block_id(left), r = m_ctrl.block_id(right);
                    if (l == r) {
                        value_type res = m_data[left];
#ifndef __clang__
#pragma GCC unroll 64
#endif
                        for (size_type i = left + 1; i <= right; i++) res = Monoid::op(res, m_data[i]);
                        return res;
                    } else if (l + 1 == r)
                        return Monoid::op(m_suffix[left], m_prefix[right]);
                    else
                        return Monoid::op(Monoid::op(m_suffix[left], m_table.query(l + 1, r - 1)), m_prefix[right]);
                }
                value_type query_all() const { return m_table.query_all(); }
                template <typename Judger>
                size_type max_right(size_type left, Judger &&judge) const {
                    value_type val = m_suffix[left];
                    if (!judge(val)) return _max_right(left, std::min(m_size, m_ctrl.block_first(left) + m_ctrl.block_size()), judge);
                    size_type l = m_ctrl.block_id(left);
                    if (l + 1 == m_table.size()) return m_size - 1;
                    size_type r = m_table.max_right(l + 1, [&](const value_type &x) { return judge(Monoid::op(val, x)); });
                    if (r + 1 == m_table.size()) return m_size - 1;
                    if (r > l) val = Monoid::op(val, m_table.query(l + 1, r));
                    return _max_right2((r + 1) * m_ctrl.block_size(), std::min(m_size, (r + 2) * m_ctrl.block_size()), [&](const value_type &x) { return judge(Monoid::op(val, x)); });
                }
                template <typename Judger>
                size_type min_left(size_type right, Judger &&judge) const {
                    value_type val = m_prefix[right];
                    if (!judge(val)) return _min_left(m_ctrl.block_first(right) - 1, right, judge);
                    size_type r = m_ctrl.block_id(right);
                    if (!r) return 0;
                    size_type l = m_table.min_left(r - 1, [&](const value_type &x) { return judge(Monoid::op(x, val)); });
                    if (!l) return 0;
                    if (l < r) val = Monoid::op(m_table.query(l, r - 1), val);
                    return _min_left2(((l - 1) * m_ctrl.block_size()) - 1, (l * m_ctrl.block_size()) - 1, [&](const value_type &x) { return judge(Monoid::op(x, val)); });
                }
            };
            template <typename Ostream, typename Node, typename Controller, size_t MAX_LEVEL>
            Ostream &operator<<(Ostream &out, const Table<Node, Controller, MAX_LEVEL> &x) {
                out << "[";
                for (size_type i = 0; i != x.size(); i++) {
                    if (i) out << ", ";
                    out << x.query(i);
                }
                return out << "]";
            }
        }
        template <typename Tp, typename Controller = SQRT::RandomController<>, size_t MAX_LEVEL = 30, typename Operation, typename InitMapping, typename TreeType = SQRT::Table<SQRT::BaseMonoid<Tp, Operation>, Controller, MAX_LEVEL>>
        auto make_SqrtTree(SQRT::size_type length, Operation op, InitMapping mapping) -> TreeType { return TreeType(length, mapping); }
        template <typename Controller = SQRT::RandomController<>, size_t MAX_LEVEL = 30, typename Iterator, typename Operation, typename Tp = typename std::iterator_traits<Iterator>::value_type, typename TreeType = SQRT::Table<SQRT::BaseMonoid<Tp, Operation>, Controller, MAX_LEVEL>>
        auto make_SqrtTree(Iterator first, Iterator last, Operation op) -> TreeType { return TreeType(first, last); }
        template <typename Tp,typename Controller = SQRT::RandomController<>,  size_t MAX_LEVEL = 30>
        using SqrtMaxTable = SQRT::Table<SQRT::BaseMonoid<Tp, SQRT::ChoiceByCompare<Tp, std::less<Tp>>>, Controller, MAX_LEVEL>;
        template <typename Tp,typename Controller = SQRT::RandomController<>,  size_t MAX_LEVEL = 30>
        using SqrtMinTable = SQRT::Table<SQRT::BaseMonoid<Tp, SQRT::ChoiceByCompare<Tp, std::greater<Tp>>>, Controller, MAX_LEVEL>;
        template <typename Tp,typename Controller = SQRT::RandomController<>,  size_t MAX_LEVEL = 30>
        using SqrtGcdTable = SQRT::Table<SQRT::BaseMonoid<Tp, SQRT::FpTransfer<Tp, std::gcd<Tp>>>, Controller, MAX_LEVEL>;
        template <typename Tp,typename Controller = SQRT::RandomController<>,  size_t MAX_LEVEL = 30>
        using SqrtLcmTable = SQRT::Table<SQRT::BaseMonoid<Tp, SQRT::FpTransfer<Tp, std::lcm<Tp>>>, Controller, MAX_LEVEL>;
        template <typename Tp, typename Controller = SQRT::RandomController<>, size_t MAX_LEVEL = 30>
        using SqrtBitAndTable = SQRT::Table<SQRT::BaseMonoid<Tp, std::bit_and<Tp>>, Controller, MAX_LEVEL>;
        template <typename Tp,typename Controller = SQRT::RandomController<>,  size_t MAX_LEVEL = 30>
        using SqrtBitOrTable = SQRT::Table<SQRT::BaseMonoid<Tp, std::bit_or<Tp>>, Controller, MAX_LEVEL>;
        template <typename Tp, typename Controller = SQRT::RandomController<>, size_t MAX_LEVEL = 30>
        using SqrtBitXorTable = SQRT::Table<SQRT::BaseMonoid<Tp, std::bit_xor<Tp>>, Controller, MAX_LEVEL>;
        template <typename Tp,typename Controller = SQRT::RandomController<>,  size_t MAX_LEVEL = 30>
        using SqrtSumTable = SQRT::Table<SQRT::BaseMonoid<Tp, std::plus<Tp>>, Controller, MAX_LEVEL>;
    }
#endif
}


// faster implementation
// source: https://judge.yosupo.jp/submission/42086
void SA_IS(const int *s, int *SA, int n, int K) {
    // s 为字符串数组[0..n-1] 必须保证 s[n-1]=0 且为最小值
    // SA 为存储后缀数组[0..n-1]
    // n 为字符串长度
    // K 为值域

    bool *t = new bool[n]; // 类型数组
    int *bkt = new int[K]; // 桶
    int *bkt_l = new int[K];
    int *bkt_r = new int[K];
    int n1 = 0; // LMS-后缀的数量
    int *p1;    //按出现顺序存储所有 LMS-后缀的索引

#define is_S_type(x) (t[x])
#define is_L_type(x) (!t[x])
#define is_LMS_type(x) (is_S_type(x) && x != 0 && is_L_type(x - 1))

    // 预处理每一个后缀的类型
    t[n - 1] = true; // 0 为 S-型后缀且为 LMS-型后缀
    for (int i = n - 2; i >= 0; --i) {
        t[i] = (s[i] < s[i + 1] || (is_S_type(i + 1) && s[i] == s[i + 1]));
        n1 += is_LMS_type(i + 1); // s[0] 必然不是 LMS-型后缀，不会影响
    }

    // 预处理桶的边界
    for (int i = 0; i != K; ++i) bkt[i] = 0;
    for (int i = 0; i != n; ++i) ++bkt[s[i]];
    for (int i = 0, sum = 0; i != K; ++i) sum += bkt[i], bkt_r[i] = sum, bkt_l[i] = sum - bkt[i];

#define indecud_sort()                                                                             \
  do {                                                                                             \
    for (int i = 0; i != K; ++i) bkt[i] = bkt_l[i];                                                \
    for (int i = 0, j; i != n; ++i)                                                                \
      if ((j = SA[i] - 1) >= 0 && is_L_type(j)) SA[bkt[s[j]]++] = j;                               \
    for (int i = 0; i != K; ++i) bkt[i] = bkt_r[i];                                                \
    for (int i = n - 1, j; i >= 0; --i)                                                            \
      if ((j = SA[i] - 1) >= 0 && is_S_type(j)) SA[--bkt[s[j]]] = j;                               \
  } while (0)

    // 将所有 LMS-后缀放入 SA 对应桶的末尾并诱导排序
    p1 = new int[n1];
    for (int i = 0, j = 0; i != n; ++i) {
        SA[i] = -1;
        if (is_LMS_type(i)) p1[j++] = i;
    }
    for (int i = 0; i != K; ++i) bkt[i] = bkt_r[i];
    for (int i = n1 - 1; i >= 0; --i) SA[--bkt[s[p1[i]]]] = p1[i];
    indecud_sort();

    int *s1 = new int[n1];  // 新的字符串
    int *SA1 = new int[n1]; // 存储新的字符串排的后缀数组
    for (int i = 0, j = 0; i != n; ++i)
        if (is_LMS_type(SA[i])) SA1[j++] = SA[i]; // 存储 LMS-子串的相对顺序
    int name = 0;
    // 对所有 LMS-子串命名
    for (int i = 0, prev = -1; i != n1; ++i) {
        int pos = SA1[i];
        for (int j = 0;; ++j) // 无需设置范围，因为 s[n-1]=0 为最小值且不会出现在其余位置
            if (prev == -1 || s[pos + j] != s[prev + j] || is_S_type(pos + j) != is_S_type(prev + j)) {
                prev = pos, ++name;
                break;
            } else if (j != 0 && (is_LMS_type(pos + j) || is_LMS_type(prev + j))) // 到末尾了停止比较
                break;
        SA[pos] = name - 1; // 利用 SA 暂时存储新字符串的 name
    }
    for (int i = 0; i != n1; ++i) s1[i] = SA[p1[i]];

    if (name != n1)
        SA_IS(s1, SA1, n1, name);
    else
        for (int i = 0; i != n1; ++i) SA1[s1[i]] = i;

    for (int i = 0; i != K; ++i) bkt[i] = bkt_r[i];
    for (int i = 0; i != n; ++i) SA[i] = -1;
    for (int i = n1 - 1; i >= 0; --i) SA[--bkt[s[p1[SA1[i]]]]] = p1[SA1[i]];
    indecud_sort();

    delete[] SA1;
    delete[] s1;
    delete[] p1;
    delete[] bkt_r;
    delete[] bkt_l;
    delete[] bkt;
    delete[] t;

#undef is_S_type
#undef is_L_type
#undef is_LMS_type
#undef indecud_sort
}


const ll INF = 2e18;
const int INFi = 1e9;
const int N = 2e5 + 50;
const int LG = 20;


std::vector<int> get_sa(const std::string &s) {
    int len = s.size();
    std::vector<int> SA(len + 1), s_cpy(len + 1);
    for (int i = 0; i != len; ++i) s_cpy[i] = s[i];
    s_cpy.back() = 0;
    SA_IS(s_cpy.data(), SA.data(), len + 1, 128);
    return std::vector<int>(SA.begin() + 1, SA.end());
}

auto min_merge = [](int x, int y) {
    return min(x, y);
};

struct suffix_array {
    std::vector<int> order, suffix_position, lcp;
    string s;

    SPARSE::OY::SqrtMinTable<uint32_t, SPARSE::OY::SQRT::NonRandomController<4>, 16> sp;


    suffix_array() {
    }

    void build(std::string str) {
        order.clear();
        suffix_position.clear();
        lcp.clear();
        s.clear();

        s = str;
        int n = str.size() + 1;
        order = get_sa(str);
        order.insert(order.begin(), n - 1);

        suffix_position.resize(n);
        for (int i = 0; i < n; i++) {
            suffix_position[order[i]] = i;
        }

        lcp.resize(n);
        int current_lcp = 0;
        for (int suffix = 0; suffix < n - 1; suffix++, current_lcp = current_lcp == 0 ? 0 : current_lcp - 1) {
            int previous_suffix = order[suffix_position[suffix] - 1];
            while (str[suffix + current_lcp] == str[previous_suffix + current_lcp])
                current_lcp++;

            lcp[suffix_position[suffix]] = current_lcp;
        }

        sp = SPARSE::OY::SqrtMinTable<uint32_t, SPARSE::OY::SQRT::NonRandomController<4>, 16>(all(lcp));
    }

    int LCP(int l, int r) {
        if (l == r) return (int) suffix_position.size() - 1 - l;
        l = suffix_position[l];
        r = suffix_position[r];
        if (l > r) swap(l, r);
        return sp.query(l + 1, r);
    }

    char Get(int pos) {
        return s[pos];
    }
} S;

namespace rect_solve {
    template<typename Val = long long>
    struct binary_indexed_tree {
        int M, H;
        std::vector<Val> sum;

        binary_indexed_tree() {}

        binary_indexed_tree(int N) : M(N), H(31 - __builtin_clz(M)), sum(M + 1, 0) { assert(N > 0); }

        binary_indexed_tree(const std::vector<Val> &v) : M(v.size()), H(31 - __builtin_clz(M)), sum(1) {
            assert(v.size() > 0);
            sum.insert(sum.begin() + 1, v.begin(), v.end());
            for (int i = 1; i <= v.size(); i++) {
                int nxt = i + (i & (-i));
                if (nxt <= M) sum[nxt] += sum[i];
            }
        }

        void update(int k, Val x) {
            for (int i = k + 1; i <= M; i += (i & (-i))) sum[i] += x;
        }

        Val query(int r) {
            Val ret = 0;
            for (int k = r; k > 0; k -= (k & (-k))) ret += sum[k];
            return ret;
        }

        Val query(int l, int r) {
            return query(r) - query(l);
        }
        // sum[0, k]がx以上になるような最小のkとsum[0, k], 無い場合は{M, 総和}
        // sumが単調非減少であることが必要
        using p = std::pair<int, Val>;

        p lower_bound(Val x) {
            int v = 1 << H, h = H;
            Val s = 0, t = 0;
            while (h--) {
                if (M < v) v -= 1 << h;
                else if (x <= s + sum[v]) t = s + sum[v], v -= 1 << h;
                else s += sum[v], v += 1 << h;
            }
            if (v == M + 1) return {M, s};
            return (x <= s + sum[v] ? p{v - 1, s + sum[v]} : p{v, t});
        }
    };
//#line 3 ".lib/minior/map_sum_cache.hpp"
//#include <limits>
//#line 5 ".lib/minior/map_sum_cache.hpp"

    template<typename Key, typename Val>
    struct map_sum_cache {
        static constexpr Key inf = std::numeric_limits<Key>::max();
        static constexpr Val inf_val = std::numeric_limits<Val>::max();
        static constexpr int limit_size_per_node = 16;
    private:
        struct node {
            int h, sz, sz_sum;
            std::array<Key, limit_size_per_node> keys;
            std::array<Val, limit_size_per_node> vals;
            Val sum, sumsub;
            node *l, *r;

            node() : h(1), l(nullptr), r(nullptr), sum(0) {}

            node(Key _key, Val _val) : h(1), sz(1), sz_sum(1), l(nullptr), r(nullptr) {
                keys[0] = _key;
                vals[0] = sum = sumsub = _val;
            }

            node(const std::vector<std::pair<Key, Val>> &v, int l, int r) : h(1), sz(r - l), sz_sum(sz), sum(0),
                                                                            l(nullptr), r(nullptr) {
                assert(sz < limit_size_per_node);
                for (int i = 0; i < sz; i++) {
                    keys[i] = v[l + i].first;
                    vals[i] = v[l + i].second;
                    sum += vals[i];
                }
                sumsub = sum;
            }

            int balanace_factor() {
                return (l ? l->h : 0) - (r ? r->h : 0);
            }

            node *split_half() {
                assert(sz == limit_size_per_node);
                node *u = new node();
                sz = limit_size_per_node / 2;
                u->sz_sum = u->sz = limit_size_per_node - sz;
                for (int i = 0; i < u->sz; i++) {
                    u->keys[i] = keys[sz + i];
                    u->vals[i] = vals[sz + i];
                    u->sum += u->vals[i];
                }
                u->sumsub = u->sum;
                sum -= u->sum;
                return u;
            }
        };

        node *root;

        int size(node *v) { return v ? v->sz_sum : 0; }

        void update(node *v) {
            v->h = std::max(v->l ? v->l->h : 0, v->r ? v->r->h : 0) + 1;
            v->sz_sum = (v->l ? v->l->sz_sum : 0) + (v->r ? v->r->sz_sum : 0) + v->sz;
            v->sumsub = (v->l ? v->l->sumsub : 0) + (v->r ? v->r->sumsub : 0) + v->sum;
        }

        node *rotate_right(node *v) {
            node *l = v->l;
            v->l = l->r;
            l->r = v;
            update(v);
            update(l);
            return l;
        }

        node *rotate_left(node *v) {
            node *r = v->r;
            v->r = r->l;
            r->l = v;
            update(v);
            update(r);
            return r;
        }

        node *balance(node *v) {
            int bf = v->balanace_factor();
            assert(-2 <= bf && bf <= 2);
            if (bf == 2) {
                if (v->l->balanace_factor() == -1) {
                    v->l = rotate_left(v->l);
                    update(v);
                }
                return rotate_right(v);
            } else if (bf == -2) {
                if (v->r->balanace_factor() == 1) {
                    v->r = rotate_right(v->r);
                    update(v);
                }
                return rotate_left(v);
            }
            return v;
        }

        node *build(const std::vector<node *> &nodes, int l, int r) {
            int m = (l + r) >> 1;
            node *v = nodes[m];
            if (m > l) v->l = build(nodes, l, m);
            if (r > m + 1) v->r = build(nodes, m + 1, r);
            update(v);
            return v;
        }

        node *insert_leftmost(node *v, node *u) {
            if (!v) return u;
            v->l = insert_leftmost(v->l, u);
            update(v);
            return balance(v);
        }

        node *emplace_inner(node *v, Key k, Val val, bool replace = false) {
            if (!v) return new node(k, val);
            if (v->l && k < v->keys[0]) {
                v->l = emplace_inner(v->l, k, val, replace);
            } else if (v->r && v->keys[v->sz - 1] < k) {
                v->r = emplace_inner(v->r, k, val, replace);
            } else {
                int idx = std::lower_bound(v->keys.begin(), v->keys.begin() + v->sz, k) - v->keys.begin();
                if (idx < v->sz && v->keys[idx] == k) {
                    v->vals[idx] += val;
                    v->sum += val;
                    v->sumsub += val;
                    return v;
                }
                for (int i = v->sz; i > idx; i--) {
                    v->keys[i] = v->keys[i - 1];
                    v->vals[i] = v->vals[i - 1];
                }
                v->keys[idx] = k;
                v->vals[idx] = val;
                v->sum += val;
                v->sz++;
                if (v->sz == limit_size_per_node) {
                    v->r = insert_leftmost(v->r, v->split_half());
                }
            }
            update(v);
            return balance(v);
        }

        Val query_inner(node *v, Key k) {
            Val ret = 0;
            while (v) {
                if (k < v->keys[0]) {
                    v = v->l;
                } else if (k > v->keys[v->sz - 1]) {
                    ret += (v->l ? v->l->sumsub : 0) + v->sum;
                    v = v->r;
                } else {
                    ret += (v->l ? v->l->sumsub : 0);
                    for (int i = 0; i < v->sz; i++) {
                        if (v->keys[i] >= k) return ret;
                        ret += v->vals[i];
                    }
                }
            }
            return ret;
        }

    public:
        map_sum_cache() : root(nullptr) {}

        map_sum_cache(std::vector<std::pair<Key, Val>> v) {
            std::sort(v.begin(), v.end());
            init_sorted(v);
        }

        // すでにソート済みかつキーがユニーク
        void init_sorted(const std::vector<std::pair<Key, Val>> &v) {
            if (v.empty()) {
                root = nullptr;
                return;
            }
            int n = v.size();
            int size_per_node = limit_size_per_node / 2;
            int m = (n + size_per_node - 1) / size_per_node;
            std::vector<node *> nodes(m);
            for (int i = 0; i < m; i++) {
                nodes[i] = new node(v, i * size_per_node, std::min((i + 1) * size_per_node, n));
            }
            root = build(nodes, 0, m);
        }

        int size() {
            return size(root);
        }

        void update(Key key, Val val) {
            root = emplace_inner(root, key, val);
        }

        Val query(Key l, Key r) {
            return query_inner(root, r) - query_inner(root, l);
        }
    };
//#line 8 ".lib/data_structure/range_query/point_add_rectangle_sum.hpp"

    template<typename Idx, typename Val>
    struct offline_point_add_rectangle_sum {
    private:
        struct query_type {
            int id;
            Idx lx, rx, ly, ry;
            Val z;

            query_type(int a, Idx b, Idx c, Idx d, Idx e, Val f) : id(a), lx(b), rx(c), ly(d), ry(e), z(f) {}
        };

        struct event_type {
            Idx x;
            int q, id;
            int lyc, ryc;
            Val z;

            event_type(Idx a, int b, int c, int d, int e, Val f) : x(a), q(b), id(c), lyc(d), ryc(e), z(f) {}
        };

        std::vector<query_type> q;
        std::vector<int> qcount{0};
        int qs = 0;

        void solve(int l, int r, std::vector<Val> &ans) {
            if (r - l < 2) return;
            int mid = (l + r) >> 1;
            solve(l, mid, ans);
            solve(mid, r, ans);
            int left_update = (mid - l) - (qcount[mid] - qcount[l]);
            int right_query = qcount[r] - qcount[mid];
            if (left_update == 0 || right_query == 0) return;

            // compress y
            std::vector<Idx> y;
            for (int i = l; i < mid; i++) if (q[i].id == -1) y.push_back(q[i].ly);
            std::sort(y.begin(), y.end());
            y.erase(std::unique(y.begin(), y.end()), y.end());

            binary_indexed_tree<Val> bit(y.size());
            std::vector<event_type> e;
            for (int i = l; i < mid; i++) {
                if (q[i].id == -1) {
                    int y_idx = std::lower_bound(y.begin(), y.end(), q[i].ly) - y.begin();
                    e.push_back(event_type(q[i].lx, 2, -1, y_idx, 0, q[i].z));
                }
            }
            for (int i = mid; i < r; i++) {
                if (q[i].id != -1) {
                    int ly_idx = std::lower_bound(y.begin(), y.end(), q[i].ly) - y.begin();
                    int ry_idx = std::lower_bound(y.begin(), y.end(), q[i].ry) - y.begin();
                    e.push_back(event_type(q[i].lx, 0, q[i].id, ly_idx, ry_idx, 0));
                    e.push_back(event_type(q[i].rx, 1, q[i].id, ly_idx, ry_idx, 0));
                }
            }
            std::sort(e.begin(), e.end(), [](event_type &a, event_type &b) {
                if (a.x != b.x) return a.x < b.x;
                return a.q < b.q;
            });
            for (event_type &ei: e) {
                if (ei.q == 0) {
                    ans[ei.id] -= bit.query(ei.lyc, ei.ryc);
                } else if (ei.q == 1) {
                    ans[ei.id] += bit.query(ei.lyc, ei.ryc);
                } else {
                    bit.update(ei.lyc, ei.z);
                }
            }
        }

    public:
        offline_point_add_rectangle_sum() {}

        void update(Idx x, Idx y, Val z) {
            q.push_back(query_type(-1, x, 0, y, 0, z));
            qcount.push_back(0);
        }

        void query(Idx lx, Idx rx, Idx ly, Idx ry) {
            q.push_back(query_type(qs++, lx, rx, ly, ry, 0));
            qcount.push_back(1);
        }

        std::vector<Val> solve() {
            std::vector<Val> ret(qs, 0);
            for (int i = 1; i < qcount.size(); i++) qcount[i] += qcount[i - 1];
            solve(0, q.size(), ret);
            return ret;
        }
    };
}

struct Element {
    vpi a;
    int idx;
    int priority;

    void read() {
        int k;
        cin >> k;
        a.resize(k);
        for (auto &[l, r]: a) {
            cin >> l >> r;
            l--;
        }
    }
};

bool operator<(const Element &a, const Element &b) {
    int i = 0;
    int used_i = 0;
    int j = 0;
    int used_j = 0;
    while (true) {
        if (j == b.a.size() && i == a.a.size()) return a.priority < b.priority;
        if (j == b.a.size()) return b.priority > 0 ? true : false;
        if (i == a.a.size()) return a.priority > 0 ? false : true;

        int mx_i = a.a[i].second - a.a[i].first - used_i;
        int mx_j = b.a[j].second - b.a[j].first - used_j;
        int mx = min(mx_i, mx_j);
        int len = S.LCP(a.a[i].first + used_i, b.a[j].first + used_j);
        ckmin(len, mx);
        used_i += len;
        used_j += len;
        if (len < mx) return S.Get(a.a[i].first + used_i) < S.Get(b.a[j].first + used_j);
        if (mx_i == len) {
            i++;
            used_i = 0;
        }
        if (mx_j == len) {
            j++;
            used_j = 0;
        }
    }
    return false;
}

void solve() {
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    vector<Element> elems;
    vector<int> ban;
    auto Add = [&](Element e, int ww) {
        e.idx = elems.size();
        elems.push_back(e);
        ban.push_back(ww);
        return e.idx;
    };
    vector<ar<int, 5>> qs(q, {-1, -1, -1, -1, -1});
    for (auto &[tp, l1, r1, l2, r2]: qs) {
        char t;
        cin >> t;
        if (t == '+') {
            Element e;
            e.read();
            e.priority = -1;
            tp = 1;
            l1 = Add(e, -1);
        } else if (t == '-') {
            tp = -1;
            int pos;
            cin >> pos;
            pos--;
            l1 = qs[pos][1];
        } else {
            tp = 0;

            Element e1, e2;
            e1.read();
            e2.read();
            e1.priority = -2;
            l1 = Add(e1, 1);
            e1.priority = 2;
            r1 = Add(e1, 1);
            e2.priority = -2;
            l2 = Add(e2, 0);
            e2.priority = 2;
            r2 = Add(e2, 0);
        }
    }
    vector<ar<int, 2>> pos(elems.size());

    rep(rot, 2) {
        S.build(s);

        vector<Element> els;
        rep(i, elems.size()) if (ban[i] != rot) {
            els.push_back(elems[i]);
        }
        sort(all(els));

        rep(i, els.size()) pos[els[i].idx][rot] = i;


        reverse(all(s));
        for (auto &e: elems) {
            for (auto &[l, r]: e.a) {
                r--;
                swap(l, r);
                l = n - 1 - l;
                r = n - 1 - r;
                r++;
            }
            reverse(all(e.a));
        }
    }

    rect_solve::offline_point_add_rectangle_sum<int, ll> rect1, rect2;

    for (auto &[tp, l1, r1, l2, r2]: qs) {
        if (tp == 1) {
            int i = l1;
            l1 = r1 = pos[i][0];
            l2 = r2 = pos[i][1];
//            cerr << "+ " << l1 << ' ' << l2 << endl;
            rect1.update(l1, l2, 1);
        } else if (tp == -1) {
            int i = l1;
            l1 = r1 = pos[i][0];
            l2 = r2 = pos[i][1];
//            cerr << "- " << l1 << ' ' << l2 << endl;
            rect2.update(l1, l2, 1);
        } else {
            l1 = pos[l1][0];
            r1 = pos[r1][0];
            l2 = pos[l2][1];
            r2 = pos[r2][1];
//            cerr << "? " << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << endl;
            rect1.query(l1, r1, l2, r2);
            rect2.query(l1, r1, l2, r2);
        }
    }

    auto ans1 = rect1.solve();
    auto ans2 = rect2.solve();
    rep(i, ans1.size()) {
        cout << ans1[i] - ans2[i] << '\n';
    }
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(12) << fixed;
    int t = 1;
//    cin >> t;
    rep(i, t) {
        solve();
    }
    return 0;
}