class BinaryArray {
private:
    // Returns the smallest index id in [lo, hi] such that
    // query(lo, id) >= k, or returns -1 if no such index exists.
    int binsearch(int lo, int hi, int k) {
        int start = lo; // remember original start for the query
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            int numOnes = query(start, mid);  // number of 1's in subarray [start, mid]
            if (numOnes >= k) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        // At this point lo == hi. Check if [start, lo] has at least k ones.
        if (query(start, lo) < k)
            return -1;
        return lo;
    }

public:
    // Returns a list of intervals (as pairs of indices) such that each interval contains exactly k ones.
    // It is assumed that the total number of 1's in the array is M (or at least M/k intervals exist).
    vector<pair<int, int>> getRanges(int M, int k) {
        vector<pair<int, int>> ans;
        int leftIndex = 1;  // assuming 1-indexed positions
        while (leftIndex <= M) {
            int L = binsearch(leftIndex, M, k);
            if (L == -1)
                break;
            ans.push_back({leftIndex, L});
            leftIndex = L + 1;
        }
        return ans;
    }

    // You must have an inbuilt query(L, R) function defined elsewhere.
    int query(int L, int R); // provided externally
};