template<typename T, class F>
struct Spares_Table {
    using ui = size_t;
    std::vector<std::vector<T>> f;
    std::vector<ui> lg;
    F mg;
    ui n;
    Spares_Table(const std::vector<T>& v) {
        n = v.size();
        lg.resize(n + 1), lg[0] = -1;
        for (ui i = 1; i <= n; ++i) {
            lg[i] = lg[i >> 1] + 1;
        }
        f = std::vector(n, std::vector<T>(lg[n] + 1));
        for (ui i = 0; i < n; ++i) {
            f[i][0] = v[i];
        }
        for (ui j = 1; j <= lg[n]; ++j) { 
            for (ui i = 0; i + (1 << j) - 1 < n; ++i) {
                f[i][j] = mg(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
            }
        }
    }
    Spares_Table(const T* a, const ui& m) {
        n = m;
        lg.resize(n + 1), lg[0] = -1;
        for (ui i = 1; i <= n; ++i) {
            lg[i] = lg[i >> 1] + 1;
        }
        f = std::vector(n, std::vector<T>(lg[n] + 1));
        for (ui i = 0; i < n; ++i) {
            f[i][0] = a[i];
        }
        for (ui j = 1; j <= lg[n]; ++j) {
            for (ui i = 0; i + (1 << j) - 1 < n; ++i) {
                f[i][j] = mg(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
            }
        }
    }
    T ask(const ui& l, const ui& r) {
        if (l > r) return T();
        ui x = lg[r - l + 1];
        return mg(f[l][x], f[r - (1 << x) + 1][x]);
    }
};
template<typename T, class F>
using ST = Spares_Table<T, F>;