#ifndef LOCAL
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#endif

#include <bits/stdc++.h>


#include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_cxx;
//using namespace __gnu_pbds;

using namespace std;

template<class T>
using V = vector<T>;
template<class T>
using VV = V<V<T>>;

using ld = long double;
using ll = long long;
using PLL = pair<ll, ll>;
using PII = pair<int, int>;
using VI = V<int>;
using VLL = V<ll>;
using VVI = VV<int>;
using VVLL = VV<ll>;
using Gr = VVI;
using MLL = map<ll, ll>;
#define UMLL unordered_map<ll, ll, custom_hash>

#define fast ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr);

#define CR const&

#define ALL(obj) begin(obj), end(obj)
#define RALL(obj) rbegin(obj), rend(obj)

#ifdef LOCAL
#define OK cerr << "OK" << endl;
#else
#define OK
#endif

template<class T>
T sqr(T x) {
    return x * x;
}

template<class T, class U = T>
void cmin(T &a, U const &b) {
    if (b < a)
        a = b;
}

template<class T, class U = T>
void cmax(T &a, U const &b) {
    if (a < b)
        a = b;
}

#ifdef LOCAL

void print_raw() {}

template<class T>
void print_raw(T CR);

void print_raw(string CR);

template<class T, class U>
void print_raw(pair<T, U> CR);

template<ranges::range T>
void print_raw(T CR);

void print_raw(const char *);


template<class T>
void print_raw(T CR t) {
    cerr << t << " ";
}

void print_raw(string CR t) {
    cerr << t << " ";
}

template<class T, class U>
void print_raw(pair<T, U> CR t) {
    cerr << '{';
    print_raw(t.first);
    cerr << "\b, ";
    print_raw(t.second);
    cerr << "\b} ";
}

template<ranges::range T>
void print_raw(T CR t) {
    cerr << '{';

    for (auto i: t)
        print_raw(i);
    if (!empty(t))
        cerr << '\b';

    cerr << "} ";
}

void print_raw(const char *t) {
    if (!t)
        return; //?

    auto sz = strlen(t);
    cerr << t;
    if (sz == 0 || t[sz - 1] != '\n')
        cerr << ' ';
}

template<class T, class... Ts>
void print_raw(T CR t, Ts CR...vals) {
    print_raw(t);
    print_raw(vals...);
}

template<class... Ts>
void print(Ts CR...vals) {
    print_raw(vals...);
    cerr << '\n';
}

#else

template<class... Ts>
void print_raw(Ts CR...vals) {}

template<class... Ts>
inline void print(Ts CR...vals) {}

#endif

template<class T>
void show(T CR t, ostream &os = cerr) {
    for (auto CR i: t)
        os << i << " ";
    os << "\n";
}

template<class T>
void show2d(T CR t, ostream &os = cerr) {
    for (auto CR i: t)
        show(i, os);
    os << "\n";
}

constexpr ll MOD = 1e9 + 7;

constexpr ll INF = 1e16;

const ld PI = atanl(1.0L) * 4;
constexpr ld eps = 1e-6, EPS = 1e-9;

//https://codeforces.com/blog/entry/62393
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

template<class T>
T &addfix(T &x, ll mod = MOD) {
    if (x >= mod)
        x -= mod;
    return x;
}

template<class T>
T &subfix(T &x, T mod = MOD) {
    if (x < 0)
        x += mod;
    return x;
}

template<class T>
T &afix(T &x, ll mod = MOD) {
    if (x < 0)
        x += mod;
    else if (x >= mod)
        x -= mod;
    return x;
}

template<class T>
T &fix(T &x, T mod = MOD) {
    x %= mod;
    subfix(x, mod);
    return x;
}

ll qpow(ll a, ll b, ll mod = MOD) {
    ll res = 1;
    while (b) {
        if (b & 1LL)
            res = res * a % mod;

        b >>= 1LL;
        a = sqr(a) % mod;
    }

    return res;
}

ll inv(ll a, ll mod = MOD) {
    return qpow(a, mod - 2, mod);
}

ll rand(ll l, ll r) {
    return rand() % (r - l + 1) + l;
}

void init() {}

struct T {
    int len, g;
    ll sum;

    T(int x) : len(1), g(x), sum(x) {}

    void add(T CR x) {
        g = __gcd(g, x.g);
        len += x.len;
        sum += x.sum;
    }
};

void rem_copy(V<T> &x) {
//    T *prev{nullptr};
//    x.erase(remove_if(ALL(x), [&](T &v) { //probably undefined behavior :3
//        if(prev && v.g == prev->g) {
//            *prev = v;
//            return true;
//        }
//        prev = &v;
//        return false;
//    }), end(x));

    V<T> res;
    for(auto CR i : x)
        if(!res.empty() && res.back().g == i.g)
            res.back() = i;
        else
            res.push_back(i);
    x = res;
}

V<T> combine(V<T> f, V<T> s, T CR d) {
    for(auto& i : s)
        i.add(d);

    f.insert(end(f), ALL(s));
    rem_copy(f);
    return f;
}

//TODO: optimize
ll calc_ans(V<T> CR x, V<T> CR y) {
    ll res = 0;
    for(auto i : x)
        for(auto j : y)
            cmax(res, __gcd(i.g, j.g) * (i.sum + j.sum));
    return res;
}

struct U {
    V<T> pref, suff;
    ll ans;
    T full;

    U() : full{0} {}
    U(int x) : pref{x}, suff{x}, ans{1LL * x * x}, full{x} {}

    static U combine(U CR x, U CR y) {
        U res;

        res.pref = ::combine(x.pref, y.pref, x.full);
        res.suff = ::combine(y.suff, x.suff, y.full);

        res.full = x.full;
        res.full.add(y.full);

        res.ans = max({x.ans, y.ans, calc_ans(x.suff, y.pref)});

//        for(auto i : res.pref)
//            print(i.g, i.sum, i.len);
//        print(x.ans, y.ans, x.suff.size(), y.pref.size(), res.ans);

        return res;
    }
};

int fast_log(int x) {
    return 31 - __builtin_clz(x);
}

constexpr int N = 2e5 + 10;

struct ShitOfPiece {
    array<U, N> jmp;
    array<ll, N> pref;

    int n, h;

    ll sum(int l, int r) const {
        return pref[r] - (l ? pref[l - 1] : 0);
    }

    ll _get_h(int l, int r) const {
        const U &x = jmp[l], &y = jmp[r - (1 << h) + 1];

        ll ans = max(x.ans, y.ans);
//        print(y.full.sum, x.full.sum);

        int R = l + (1 << h), L = r - (1 << h); //off by 1
        for(auto CR i : x.suff)
            for(auto CR j : y.pref) {
                int actual_l = R - i.len, actual_r = L + j.len;
//                print(1 << h, i.len, j.len, actual_l, actual_r, __gcd(i.g, j.g), sum(actual_l, actual_r));
                if(actual_l <= actual_r)
                    cmax(ans, __gcd(i.g, j.g) * sum(actual_l, actual_r));
            }
        return ans;
    }

    void update_layer() {
        for(int j = 0; j + (1 << h) <= n; ++j)
            jmp[j] = U::combine(jmp[j], jmp[j + (1 << (h - 1))]);
    }

    VLL query(VI CR a, V<pair<PII, int>> Q) {
        n = a.size();
        h = 0;
        for(int i = 0; i < n; ++i) {
            jmp[i] = a[i];
            pref[i] = a[i];
        }
        partial_sum(begin(pref), begin(pref) + n, begin(pref));

        sort(ALL(Q), [](pair<PII, int> CR x, pair<PII, int> CR y) {
            return x.first.second - x.first.first < y.first.second - y.first.first;
        });

        VLL ans(Q.size());
        for(auto [lr, ind] : Q) {
            auto [l, r] = lr;
            int curr_h = fast_log(r - l + 1);

            while(h < curr_h) {
                ++h;
                update_layer();
            }
            ans[ind] = _get_h(l, r);
        }
        return ans;
    }
};

ShitOfPiece shit;

VLL fast_sol(VI CR a, V<PII> CR Q) {
    V<pair<PII, int>> Q2(Q.size());
    for(int i = 0; i < Q.size(); ++i)
        Q2[i] = {Q[i], i};

    return shit.query(a, Q2);
}

VLL brute_sol(VI CR a, V<PII> CR Q) {
    int n = a.size();

    VVLL res(n, VLL(n));
    for(int l = 0; l < n; ++l) {
        int g = 0;
        ll sum = 0, t = 0;
        for(int r = l; r < n; ++r) {
            g = __gcd(g, a[r]);
            sum += a[r];
            cmax(t, g * sum);
            res[l][r] = t;
        }
    }

    for(int r = 0; r < n; ++r)
        for(int l = r - 1; l >= 0; --l)
            cmax(res[l][r], res[l + 1][r]);

    VLL ans(Q.size());
    for(int i = 0; i < Q.size(); ++i)
        ans[i] = res[Q[i].first][Q[i].second];
    return ans;
}

pair<VI, V<PII>> gen() {
    int n = rand(1, 1000);
    VI a(n);
    for(auto& i : a)
        i = rand(1, 20);

//    V<PII> Q(100);
//    for(auto &[l, r] : Q) {
//        l = rand(0, n - 1);
//        r = rand(l, n - 1);
//    }
    V<PII> Q;
    for(int l = 0; l < n; ++l)
        for(int r = l; r < n; ++r)
            Q.emplace_back(l, r);
    return {a, Q};
}

void test() {
//    OK
    auto [a, Q] = gen();
    VLL f = brute_sol(a, Q), s = fast_sol(a, Q);

    if(f != s) {
        print(f);
        print(s);

        for(int i = 0; i < Q.size(); ++i)
            if(f[i] != s[i]) {
                print(Q[i], "->", f[i], s[i]);
            }

        cout << a.size() << " " << Q.size() << "\n";
        for(auto i : a)
            cout << i << " ";
        cout << "\n";

        for(auto [l, r] : Q)
            cout << l + 1 << " " << r + 1 << "\n";

        exit(1);
    }
}

void solve(int test_id) {
//    while(1)
//        test();

    int n, q;
    cin >> n >> q;

    VI a(n);
    for(auto& i : a)
        cin >> i;

    V<PII> Q(q);
    for(auto& [l, r] : Q) {
        cin >> l >> r;
        --l;
        --r;
    }

    auto ans = fast_sol(a, Q);
    for(auto i : ans)
        cout << i << "\n";
}

int main() {
    auto seed = time(nullptr);
    //cerr << "seed: " << seed << "\n";
    srand(seed);
    fast
    init();
    int q = 1;
//    cin >> q;

    cout << setprecision(999);
    for (int id = 1; id <= q; ++id)
        solve(id);
}