#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
}

namespace SOLVE_2D {
#ifndef __OY_WAVELET__
#define __OY_WAVELET__
    namespace OY {
        namespace WaveLet {
            using size_type = uint32_t;
            using mask_type = uint64_t;
            struct Ignore {};
            static constexpr size_type MASK_SIZE = sizeof(mask_type) << 3, MASK_WIDTH = MASK_SIZE / 32 + 4;
            struct BitRank {
                std::vector<mask_type> m_bits;
                std::vector<size_type> m_sum;
                void resize(size_type length) { m_bits.assign((length >> MASK_WIDTH) + 1, 0), m_sum.resize(m_bits.size()); }
                void set(size_type i, mask_type val) { m_bits[i >> MASK_WIDTH] |= val << (i & (MASK_SIZE - 1)); }
                void prepare() {
                    for (size_type i = 1; i != m_bits.size(); i++) m_sum[i] = m_sum[i - 1] + std::popcount(m_bits[i - 1]);
                }
                size_type rank1(size_type i) const { return m_sum[i >> MASK_WIDTH] + std::popcount(m_bits[i >> MASK_WIDTH] & ((mask_type(1) << (i & (MASK_SIZE - 1))) - 1)); }
                size_type rank1(size_type l, size_type r) const { return rank1(r) - rank1(l); }
                size_type rank0(size_type i) const { return i - rank1(i); }
                size_type rank0(size_type l, size_type r) const { return rank0(r) - rank0(l); }
            };
            struct VoidTable {
                template <typename Iterator>
                void reset(Iterator first, Iterator last) {}
                template <typename InitMapping>
                void resize(size_type length, InitMapping) {}
                size_type query(size_type left, size_type right) const { return right - left + 1; }
            };
            template <typename Tp, typename SumTable = VoidTable>
            struct Table {
                size_type m_size, m_alpha;
                std::vector<BitRank> m_ranks;
                std::vector<size_type> m_pos;
                std::vector<SumTable> m_sumer;
                Table() = default;
                template <typename InitMapping, typename TableMapping = Ignore>
                Table(size_type length, InitMapping mapping, size_type alpha = 0, TableMapping table_mapping = TableMapping()) { resize(length, mapping, alpha, table_mapping); }
                template <typename Iterator, typename TableMapping = Ignore>
                Table(Iterator first, Iterator last, size_type alpha = 0, TableMapping table_mapping = TableMapping()) { reset(first, last, alpha, table_mapping); }
                template <typename InitMapping, typename TableMapping = Ignore>
                void resize(size_type length, InitMapping mapping, size_type alpha = 0, TableMapping table_mapping = TableMapping()) {
                    static_assert(std::is_unsigned<Tp>::value, "Tp Must Be Unsigned Type");
                    if (!(m_size = length)) return;
                    std::vector<Tp> numbers(m_size);
                    for (size_type i = 0; i != m_size; i++) numbers[i] = mapping(i);
                    m_alpha = alpha ? alpha : std::max<uint32_t>(1, std::bit_width(*std::max_element(numbers.begin(), numbers.end())));
                    m_ranks.resize(m_alpha), m_pos.resize(m_alpha);
                    m_sumer.resize(m_alpha);
                    for (size_type d = m_alpha - 1; ~d; d--) {
                        m_ranks[d].resize(m_size);
                        for (size_type i = 0; i != m_size; i++) m_ranks[d].set(i, numbers[i] >> d & 1);
                        m_ranks[d].prepare();
                        m_pos[d] = std::stable_partition(numbers.begin(), numbers.end(), [&](size_type val) { return !(val >> d & 1); }) - numbers.begin();
                        if constexpr (std::is_same<TableMapping, Ignore>::value)
                            m_sumer[d].reset(numbers.begin(), numbers.end());
                        else
                            m_sumer[d].resize(m_size, [&](size_type i) { return table_mapping(numbers[i]); });
                    }
                }
                template <typename Iterator, typename TableMapping = Ignore>
                void reset(Iterator first, Iterator last, size_type alpha = 0, TableMapping table_mapping = TableMapping()) {
                    resize(
                            last - first, [&](size_type i) { return *(first + i); }, alpha, table_mapping);
                }
                size_type count(size_type left, size_type right, Tp val) const {
                    right++;
                    for (size_type d = m_alpha - 1; ~d; d--) {
                        size_type zl = m_ranks[d].rank0(left), zr = m_ranks[d].rank0(right);
                        if (!(val >> d & 1))
                            left = zl, right = zr;
                        else
                            left += m_pos[d] - zl, right += m_pos[d] - zr;
                    }
                    return right - left;
                }
                size_type count(size_type left, size_type right, Tp minimum, Tp maximum) const {
                    size_type l1 = left, r1 = right + 1, l2 = left, r2 = right + 1, res = 0;
                    for (size_type d = m_alpha - 1; ~d; d--) {
                        size_type zl1 = m_ranks[d].rank0(l1), zr1 = m_ranks[d].rank0(r1), zl2 = m_ranks[d].rank0(l2), zr2 = m_ranks[d].rank0(r2);
                        if (!(minimum >> d & 1))
                            l1 = zl1, r1 = zr1;
                        else
                            res -= zr1 - zl1, l1 += m_pos[d] - zl1, r1 += m_pos[d] - zr1;
                        if (!(maximum >> d & 1))
                            l2 = zl2, r2 = zr2;
                        else
                            res += zr2 - zl2, l2 += m_pos[d] - zl2, r2 += m_pos[d] - zr2;
                    }
                    return r2 - l2 + res;
                }
                size_type rank(size_type left, size_type right, Tp val) const {
                    size_type ans = 0;
                    right++;
                    for (size_type d = m_alpha - 1; ~d; d--) {
                        size_type zl = m_ranks[d].rank0(left), zr = m_ranks[d].rank0(right);
                        if (!(val >> d & 1))
                            left = zl, right = zr;
                        else
                            left += m_pos[d] - zl, right += m_pos[d] - zr, ans += zr - zl;
                    }
                    return ans;
                }
                Tp minimum(size_type left, size_type right) const {
                    Tp ans = 0;
                    right++;
                    for (size_type d = m_alpha - 1; ~d; d--) {
                        size_type zl = m_ranks[d].rank0(left), zr = m_ranks[d].rank0(right);
                        if (zl != zr)
                            left = zl, right = zr;
                        else
                            left += m_pos[d] - zl, right += m_pos[d] - zr, ans |= Tp(1) << d;
                    }
                    return ans;
                }
                Tp maximum(size_type left, size_type right) const {
                    Tp ans = 0;
                    right++;
                    for (size_type d = m_alpha - 1; ~d; d--) {
                        size_type zl = m_ranks[d].rank0(left), zr = m_ranks[d].rank0(right);
                        if (zr - zl == right - left)
                            left = zl, right = zr;
                        else
                            left += m_pos[d] - zl, right += m_pos[d] - zr, ans |= Tp(1) << d;
                    }
                    return ans;
                }
                Tp quantile(size_type left, size_type right, size_type k) const {
                    Tp ans = 0;
                    right++;
                    for (size_type d = m_alpha - 1; ~d; d--) {
                        size_type zl = m_ranks[d].rank0(left), zr = m_ranks[d].rank0(right), z = zr - zl;
                        if (k < z)
                            left = zl, right = zr;
                        else
                            left += m_pos[d] - zl, right += m_pos[d] - zr, k -= z, ans |= Tp(1) << d;
                    }
                    return ans;
                }
                Tp max_bitxor(size_type left, size_type right, Tp val) const {
                    Tp ans = 0;
                    right++;
                    for (size_type d = m_alpha - 1; ~d; d--) {
                        size_type zl = m_ranks[d].rank0(left), zr = m_ranks[d].rank0(right), z = zr - zl;
                        if (val >> d & 1)
                            if (z)
                                left = zl, right = zr, ans |= Tp(1) << d;
                            else
                                left += m_pos[d] - zl, right += m_pos[d] - zr;
                        else if (right - left - z)
                            left += m_pos[d] - zl, right += m_pos[d] - zr, ans |= Tp(1) << d;
                        else
                            left = zl, right = zr;
                    }
                    return ans;
                }
                template <typename Callback>
                void do_for_rank_range(size_type left, size_type right, size_type rk1, size_type rk2, Callback &&call) const {
                    right++;
                    auto handle = [&](size_type l1, size_type r1, size_type l2, size_type r2, size_type k1, size_type k2, size_type d) {
                        for (; ~d; d--) {
                            size_type one_l = m_ranks[d].rank1(l1), one_r = m_ranks[d].rank1(r1), one = one_r - one_l, zl = m_ranks[d].rank0(l2), zr = m_ranks[d].rank0(r2), z = zr - zl;
                            if (k1 < one)
                                l1 = m_pos[d] + one_l, r1 = m_pos[d] + one_r;
                            else {
                                l1 -= one_l, r1 -= one_r, k1 -= one;
                                if (one) call(m_sumer[d].query(m_pos[d] + one_l, m_pos[d] + one_r - 1));
                            }
                            if (k2 < z)
                                l2 = zl, r2 = zr;
                            else {
                                l2 += m_pos[d] - zl, r2 += m_pos[d] - zr, k2 -= z;
                                if (z) call(m_sumer[d].query(zl, zr - 1));
                            }
                        }
                        if (k1) call(m_sumer[0].query(l1, l1 + k1 - 1));
                        if (k2) call(m_sumer[0].query(r2 - k2, r2 - 1));
                    };
                    for (size_type d = m_alpha - 1; ~d; d--) {
                        size_type zl = m_ranks[d].rank0(left), zr = m_ranks[d].rank0(right), z = zr - zl;
                        if (rk2 < z)
                            left = zl, right = zr;
                        else if (rk1 >= z)
                            left += m_pos[d] - zl, right += m_pos[d] - zr, rk1 -= z, rk2 -= z;
                        else
                            return handle(zl, zr, left + m_pos[d] - zl, right + m_pos[d] - zr, z - rk1, rk2 - z + 1, d - 1);
                    }
                    if (left != right) call(m_sumer[0].query(left + rk1, left + rk2));
                }
                template <typename Callback>
                void do_for_value_range(size_type left, size_type right, Tp floor, Tp ceil, Callback &&call) const {
                    right++;
                    auto handle = [&](size_type l1, size_type r1, size_type l2, size_type r2, size_type d) {
                        for (; ~d; d--) {
                            size_type one_l = m_ranks[d].rank1(l1), one_r = m_ranks[d].rank1(r1), one = one_r - one_l, zl = m_ranks[d].rank0(l2), zr = m_ranks[d].rank0(r2), z = zr - zl;
                            if (floor >> d & 1)
                                l1 = m_pos[d] + one_l, r1 = m_pos[d] + one_r;
                            else {
                                l1 -= one_l, r1 -= one_r;
                                if (one) call(m_sumer[d].query(m_pos[d] + one_l, m_pos[d] + one_r - 1));
                            }
                            if (!(ceil >> d & 1))
                                l2 = zl, r2 = zr;
                            else {
                                l2 += m_pos[d] - zl, r2 += m_pos[d] - zr;
                                if (z) call(m_sumer[d].query(zl, zr - 1));
                            }
                        }
                        if (l1 != r1) call(m_sumer[0].query(l1, r1 - 1));
                        if (l2 != r2) call(m_sumer[0].query(l2, r2 - 1));
                    };
                    for (size_type d = m_alpha - 1; ~d; d--) {
                        size_type zl = m_ranks[d].rank0(left), zr = m_ranks[d].rank0(right), z = zr - zl;
                        if ((floor >> d & 1) == (ceil >> d & 1))
                            if (!(floor >> d & 1))
                                left = zl, right = zr;
                            else
                                left += m_pos[d] - zl, right += m_pos[d] - zr;
                        else
                            return handle(zl, zr, left + m_pos[d] - zl, right + m_pos[d] - zr, d - 1);
                    }
                    if (left != right) call(m_sumer[0].query(left, right - 1));
                }
                template <typename Callback>
                void do_in_table(size_type pos, Callback &&call) {
                    for (size_type d = m_alpha - 1; ~d; d--) {
                        size_type zl = m_ranks[d].rank0(pos), zr = m_ranks[d].rank0(pos + 1);
                        call(m_sumer[d], pos = zl == zr ? pos + m_pos[d] - zl : zl);
                    }
                }
            };
            template <typename Tp, typename SumTable = VoidTable>
            struct Tree {
                Table<size_type, SumTable> m_table;
                std::vector<Tp> m_discretizer;
                size_type m_size;
                size_type _find(const Tp &val) const { return std::lower_bound(m_discretizer.begin(), m_discretizer.end(), val) - m_discretizer.begin(); }
                size_type _upper_find(const Tp &val) const { return std::upper_bound(m_discretizer.begin(), m_discretizer.end(), val) - m_discretizer.begin(); }
                Tree() = default;
                template <typename InitMapping, typename TableMapping = Ignore>
                Tree(size_type length, InitMapping mapping, TableMapping table_mapping = TableMapping()) { resize(length, mapping, table_mapping); }
                template <typename Iterator, typename TableMapping = Ignore>
                Tree(Iterator first, Iterator last, TableMapping table_mapping = TableMapping()) { reset(first, last, table_mapping); }
                template <typename InitMapping, typename TableMapping = Ignore>
                void resize(size_type length, InitMapping mapping, TableMapping table_mapping = TableMapping()) {
                    if (!(m_size = length)) return;
                    std::vector<Tp> items(m_size);
                    for (size_type i = 0; i != m_size; i++) items[i] = mapping(i);
                    m_discretizer = items;
                    std::sort(m_discretizer.begin(), m_discretizer.end());
                    m_discretizer.erase(std::unique(m_discretizer.begin(), m_discretizer.end()), m_discretizer.end());
                    if constexpr (std::is_same<TableMapping, Ignore>::value)
                        m_table.resize(
                                m_size, [&](size_type i) { return _find(items[i]); }, std::bit_width(m_discretizer.size()), [&](size_type val) { return m_discretizer[val]; });
                    else
                        m_table.resize(
                                m_size, [&](size_type i) { return _find(items[i]); }, std::bit_width(m_discretizer.size()), [&](size_type val) { return table_mapping(m_discretizer[val]); });
                }
                template <typename Iterator, typename TableMapping>
                void reset(Iterator first, Iterator last, TableMapping table_mapping = TableMapping()) {
                    resize(
                            last - first, [&](size_type i) { return *(first + i); }, table_mapping);
                }
                size_type count(size_type left, size_type right, const Tp &val) const {
                    size_type find = _find(val);
                    return find < m_discretizer.size() && m_discretizer[find] == val ? m_table.count(left, right, find) : 0;
                }
                size_type count(size_type left, size_type right, const Tp &minimum, const Tp &maximum) const {
                    size_type find1 = _find(minimum);
                    if (find1 == m_discretizer.size()) return 0;
                    size_type find2 = _find(maximum);
                    return find2 < m_discretizer.size() && m_discretizer[find2] == maximum ? m_table.count(left, right, find1, find2) : m_table.count(left, right, find1, find2 - 1);
                }
                size_type rank(size_type left, size_type right, const Tp &val) const { return m_table.rank(left, right, _find(val)); }
                Tp minimum(size_type left, size_type right) const { return m_discretizer[m_table.minimum(left, right)]; }
                Tp maximum(size_type left, size_type right) const { return m_discretizer[m_table.maximum(left, right)]; }
                Tp quantile(size_type left, size_type right, size_type k) const { return m_discretizer[m_table.quantile(left, right, k)]; }
                template <typename Callback>
                void do_for_rank_range(size_type left, size_type right, size_type rk1, size_type rk2, Callback &&call) const { m_table.do_for_rank_range(left, right, rk1, rk2, call); }
                template <typename Callback>
                void do_for_value_range(size_type left, size_type right, const Tp &floor, const Tp &ceil, Callback &&call) const { m_table.do_for_value_range(left, right, _find(floor), _upper_find(ceil) - 1, call); }
            };
        }
    }
#endif
#ifndef __OY_POINTADDRECTSUMCOUNTER2D__
#define __OY_POINTADDRECTSUMCOUNTER2D__
    namespace OY {
        namespace PARSC2D {
            using size_type = uint32_t;
            template <typename SizeType, typename WeightType, bool HasModify>
            struct Point {
                SizeType m_x, m_y;
                WeightType m_w;
            };
            template <typename SizeType, typename WeightType>
            struct Point<SizeType, WeightType, true> {
                SizeType m_x, m_y;
                size_type m_index;
                WeightType m_w;
            };
            template <typename SizeType>
            struct Point<SizeType, bool, false> {
                SizeType m_x, m_y;
            };
            template <typename SizeType>
            struct Point<SizeType, bool, true> {
                SizeType m_x, m_y;
                size_type m_index;
            };
            template <typename Tp>
            struct AdjTable {
                std::vector<Tp> m_sum;
                template <typename InitMapping>
                void resize(size_type length, InitMapping mapping) {
                    m_sum.resize(length + 1);
                    for (size_type i = 0; i != length; i++) m_sum[i + 1] = m_sum[i] + mapping(i);
                }
                Tp query(size_type left, size_type right) const { return m_sum[right + 1] - m_sum[left]; }
            };
            template <typename Tp>
            struct SimpleBIT {
                std::vector<Tp> m_sum;
                static size_type _lowbit(size_type x) { return x & -x; }
                template <typename InitMapping>
                void resize(size_type length, InitMapping mapping) {
                    m_sum.resize(length);
                    for (size_type i = 0; i != length; i++) m_sum[i] = mapping(i);
                    for (size_type i = 0; i != length; i++) {
                        size_type j = i + _lowbit(i + 1);
                        if (j < length) m_sum[j] += m_sum[i];
                    }
                }
                void add(size_type i, size_type inc) {
                    while (i < m_sum.size()) m_sum[i] += inc, i += _lowbit(i + 1);
                }
                Tp presum(size_type i) const {
                    Tp res{};
                    for (size_type j = i; ~j; j -= _lowbit(j + 1)) res += m_sum[j];
                    return res;
                }
                Tp query(size_type left, size_type right) const { return presum(right) - presum(left - 1); }
            };
            template <typename SizeType, typename WeightType = bool, typename SumType = typename std::conditional<std::is_same<WeightType, bool>::value, size_type, WeightType>::type, bool HasModify = false>
            struct Table {
                static constexpr bool is_bool = std::is_same<WeightType, bool>::value;
                using point = Point<SizeType, WeightType, HasModify>;
                using inner_table = typename std::conditional<HasModify, SimpleBIT<SumType>, AdjTable<SumType>>::type;
                using wavelet = WaveLet::Table<size_type, inner_table>;
                std::vector<point> m_points;
                std::vector<SizeType> m_sorted_xs, m_ys;
                std::vector<size_type> m_point_pos;
                wavelet m_table;
                Table() = default;
                Table(size_type point_cnt) { m_points.reserve(point_cnt); }
                void add_point(SizeType x, SizeType y, WeightType w = 1) {
                    if constexpr (is_bool)
                        if constexpr (HasModify)
                            m_points.push_back({x, y, size_type(m_points.size())});
                        else
                            m_points.push_back({x, y});
                    else if constexpr (HasModify)
                        m_points.push_back({x, y, size_type(m_points.size()), w});
                    else
                        m_points.push_back({x, y, w});
                }
                void prepare() {
                    std::sort(m_points.begin(), m_points.end(), [](const point &x, const point &y) { return x.m_y < y.m_y; });
                    m_ys.reserve(m_points.size());
                    std::vector<WeightType> wtable;
                    if constexpr (!is_bool) wtable.reserve(m_points.size());
                    for (auto &p : m_points) {
                        m_ys.push_back(p.m_y), p.m_y = m_ys.size() - 1;
                        if constexpr (!is_bool) wtable.push_back(p.m_w);
                    }
                    std::sort(m_points.begin(), m_points.end(), [](const point &x, const point &y) { return x.m_x < y.m_x; });
                    auto mapping = [&](size_type i) { return m_points[i].m_y; };
                    auto table_mapping = [&](size_type y) -> SumType {
                        if constexpr (is_bool)
                            return 1;
                        else
                            return wtable[y];
                    };
                    m_table.resize(m_points.size(), mapping, std::bit_width(m_points.size()), table_mapping);
                    m_sorted_xs.reserve(m_points.size());
                    for (auto &p : m_points) m_sorted_xs.push_back(p.m_x);
                    if constexpr (HasModify) {
                        m_point_pos.resize(m_points.size());
                        for (size_type i = 0; i != m_points.size(); i++) m_point_pos[m_points[i].m_index] = i;
                    }
                }
                SumType query(SizeType x_min, SizeType x_max, SizeType y_min, SizeType y_max) const {
                    auto y1 = std::lower_bound(m_ys.begin(), m_ys.end(), y_min) - m_ys.begin(), y2 = std::upper_bound(m_ys.begin(), m_ys.end(), y_max) - m_ys.begin() - 1;
                    SumType res{};
                    if (y1 != y2 + 1) m_table.do_for_value_range(std::lower_bound(m_sorted_xs.begin(), m_sorted_xs.end(), x_min) - m_sorted_xs.begin(), std::upper_bound(m_sorted_xs.begin(), m_sorted_xs.end(), x_max) - m_sorted_xs.begin() - 1, y1, y2, [&](SumType val) { res += val; });
                    return res;
                }
                void add_point_value(size_type point_id, WeightType w) {
                    static_assert(HasModify, "HasModify Must Be True");
                    m_table.do_in_table(m_point_pos[point_id], [w](inner_table &tr, size_type pos) { tr.add(pos, w); });
                }
            };
        };
    }
#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;

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

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

};

pair<bool, ll> Comp(const Element &a, const Element &b) {
    ll total = 0;
    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 make_pair(a.priority < b.priority, total);
        if (j == b.a.size()) return make_pair(b.priority > 0 ? true : false, total);
        if (i == a.a.size()) return make_pair(a.priority > 0 ? false : true, total);

        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;
        total += len;
        if (len < mx) return make_pair(S.Get(a.a[i].first + used_i) < S.Get(b.a[j].first + used_j), total);
        if (mx_i == len) {
            i++;
            used_i = 0;
        }
        if (mx_j == len) {
            j++;
            used_j = 0;
        }
    }
    return {false, 0};
}

bool operator<(const Element &a, const Element &b) {
    return Comp(a, b).first;
}

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()), pos2(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));

        vector<pair<ll, int>> stk;
        rep(i, els.size()) {
            if (i) {
                ll val = Comp(els[i - 1], els[i]).second;
                int j = i - 1;
                while (!stk.empty() && stk.back().first >= val) {
                    j = stk.back().second;
                    stk.pop_back();
                }
                stk.emplace_back(val, j);
            }
            pos[els[i].idx][rot] = i;
            if (!stk.empty() && stk.back().first == els[i].length) {
                pos2[els[i].idx][rot] = stk.back().second;
            } else {
                pos2[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));
        }
    }


    SOLVE_2D::OY::PARSC2D::Table<uint32_t, uint32_t, uint64_t, true> sol(0);

    vector<ar<int, 4>> queries;

    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;
            sol.add_point(l1, l2, 0);
//            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;
            sol.add_point(l1, l2, 0);
//            rect2.update(l1, l2, 1);
        } else {
            l1 = pos2[r1][0];
            r1 = pos[r1][0];
            l2 = pos2[r2][1];
            r2 = pos[r2][1];
//            cerr << "? " << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << endl;
//            rect1.query(l1, r1, l2, r2);
//            rect2.query(l1, r1, l2, r2);
        }
    }
    sol.prepare();
    int id = 0;
    for (auto &[tp, l1, r1, l2, r2]: qs) {
        if (tp == 1 || tp == -1) {
            sol.add_point_value(id++, (tp + q) % q);
        } else {
            cout << sol.query(l1, r1, l2, r2) % q << '\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;
}