ZPATRIOT

#include <iostream>
#include <tuple>
#include <random>

using namespace std;
using int64 = int64_t;


class SegmentTree {
public:
    int64 log_size;
    vector<int64> nodes = std::vector<int64>((2 << log_size) - 1);

    static int64 IntLog(int64 n) {
        int64 temp = 1;
        int64 ans = 0;
        while (temp < n) {
            temp *= 2;
            ++ans;
        }
        return ans;
    }

    static int64 Pow2(int64 n) {
        return 1 << n;
    }

    explicit SegmentTree(const vector<int64> &vec) : log_size(IntLog(vec.size())) {
        std::copy(vec.begin(), vec.end(), nodes.begin() + (1 << log_size) - 1);
        for (int64 i = Pow2(log_size) - 2; i >= 0; --i) {
            nodes[i] = nodes[2 * i + 1] + nodes[2 * i + 2];
        }
    }

    void Modify(int64 ind, int64 value) {
        int64 temp = Pow2(log_size) + ind - 1;
        nodes[temp] = value;
        while (temp != 0) {
            temp = (temp - 1) / 2;
            nodes[temp] = nodes[temp * 2 + 1] + nodes[temp * 2 + 2];
        }
    }

    int64 GetSum(int64 l, int64 r) {
        return GetSum(l, r, 0, 0, Pow2(log_size) - 1);
    }
    int64 BinSec(int64 n, int64 ll, int64 s){
        int64 r = n;
        int64 l = ll;
        s -= GetSum(0, ll);
        if (GetSum(l, r - 1) < s){
            return 0;
        }
        while (l + 1 < r) {
            int64 mid = (l + r) / 2;
            int64 t = GetSum(l, mid);
            if (t <= s){
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }
private:
    int64 GetSum(int64 l, int64 r, int64 n, int64 nl, int64 nr) {
        if (l > r) {
            return 0;
        }
        if (l == nl && r == nr) {
            return nodes[n];
        }
        int64 mid = (nl + nr) / 2;
        return GetSum(l, min(r, mid), n * 2 + 1, nl, mid) +
               GetSum(max(l, mid + 1), r, n * 2 + 2, mid + 1, nr);
    }

};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<int64> vec(n);
    for (int i = 0; i < n; ++i){
        cin >> vec[i];
    }
    SegmentTree arr(vec);
    int t;
    cin >> t;
    int64 p = 0;
    for (int i = 0; i < t; ++i){
        int x, y;
        cin >> x >> y;
        int64 l = (x + p) % n ;
        int64 k = (y + p) % n ;
        int64 ans = arr.BinSec(n, l, k);
        p = ans + 1;
        cout << ans << '\n';
    }
    return 0;
}