// Use Mo's algorithm to solve "Queries for Decimal Values of Binary Subarrays" problem
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

ll find_highest_bit(ll val) {
    ll res = 0;
    while (val > 0) {
        res = val;
        val &= (val - 1);
    }
    return res;
}

ll remove_r (int index, ll oldVal, const vector<int>& arr) {
    return (oldVal >> 1);
}

ll add_r (int index, ll oldVal, const vector<int>& arr) {
    return (oldVal << 1) + arr[index];
}

ll remove_l (int index, ll oldVal, const vector<int>& arr) {
    return oldVal - (arr[index] == 1 ? find_highest_bit(oldVal) : 0);
}

ll add_l (int index, ll oldVal, const vector<int>& arr) {
    return oldVal + ( arr[index] == 1 ? (find_highest_bit(oldVal) << 1) : 0 );
}

int main() {

    int N, Q;
    cin >> N >> Q;
    vector<int> A(N, 0);
    for (int i = 0; i < N; i++) cin >> A[i];
    vector<pair<pii, int> > queries;       //< <L, R>, 'indexes of input' >
    for (int i = 0; i < Q; i++) {
        int l, r;
        cin >> l >> r;
        queries.emplace_back(make_pair(make_pair(l,r), i));
    }

    sort (queries.begin(), queries.end(), [&](const auto& a, const auto& b) {
        return a.first.first != b.first.first ? a.first.first < b.first.first : a.first.second < b.first.second;
    });

    vector<ll> res (queries.size(), 0);
    int mo_left = 0, mo_right = -1;
    ll curr_result = 0;
    for (auto & querie : queries) {
        int left = querie.first.first, right = querie.first.second;

        while (mo_right < right) {
            mo_right++;
            curr_result = add_r(mo_right, curr_result, A);
        }

        while (mo_right > right) {
            curr_result = remove_r(mo_right, curr_result, A);
            mo_right--;
        }

        while (mo_left < left) {
            curr_result = remove_l(mo_left, curr_result, A);
            mo_left++;
        }

        while (mo_left > left) {
            mo_left--;
            curr_result = add_l(mo_left, curr_result, A);
        }

        res[querie.second] = curr_result;
    }

    for (auto n : res) {
        cout << n << endl;
    }

    return 0;
}

// Use pre[BLOCK_NUM][BLOCK_SIZE=63] to solve "Queries for Decimal Values of Binary Subarrays" problem
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

typedef long long ll;

int main() {

    int N, Q;
    cin >> N >> Q;
    vector<int> A(N, 0);
    for (int i = 0; i < N; i++) cin >> A[i];

    //pre compute
    int BLOCK_SIZE = 63, BLOCK_NUM = (N - 1) / BLOCK_SIZE + 1;

    vector<int> block_left;
    for (int i = 0; i < N; i += BLOCK_SIZE) block_left.push_back(i);

    vector<vector<ll>> preSum (BLOCK_NUM, vector<ll>(BLOCK_SIZE, 0));
    for (int i = 0; i < block_left.size(); i++) {
        int l = block_left[i];
        for (ll r = min(l + BLOCK_SIZE - 1, N - 1), base = 1, prev = 0; r >= l; r--, base *= 2) {
            preSum[i][r-l] = prev + A[r]*base;
            prev = preSum[i][r-l];
        }
    }

    int L, R;
    while (cin >> L >> R) {
        auto it = upper_bound(block_left.begin(), block_left.end(), L) - 1;

        int left_margin_index = it - block_left.begin();
        ll res = 0;
        while (left_margin_index < block_left.size() && block_left[left_margin_index] <= R) {
            int left_margin = block_left[left_margin_index];
            int right_margin = min(left_margin_index + BLOCK_SIZE - 1, N - 1);
            int left = max(L, left_margin);
            int right = min(R, right_margin);

            res <<= (right - left + 1);
            ll to_minus = (right == right_margin ? 0 : preSum[left_margin_index][right - left_margin + 1]);
            res += ( (preSum[left_margin_index][left - left_margin] - to_minus) >> (right_margin - right) );
            left_margin_index++;
        }
        
        //if ( (res - 1)/2 == INT_MAX) res = INT_MIN;

        cout << res << endl;
    }

    return 0;
}