听闻远方有你，动身跋涉千里

K 听闻远方有你，动身跋涉千里

不难发现数组的前缀和表示当前的位移，考虑二分答案，对于每次查询的移动次数，只需判断左边的人的移动到的最右端的位置是否与右边的人的移动到的最左端的位置相交，需要一个 来维护区间最值。复杂度不超过 。

#pragma GCC optimize(2)
using namespace std;
using i64 = long long;
using ld = long double;
#define endl '\n'
#define lowbit(x) x & -x
constexpr i64 inf = 1e18;
constexpr i64 mod = 998244353;
constexpr ld PI = acos(-1.0);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
i64 n, m, k;

template <class Ty, const i64 logn>
struct RMQ {
    using i64 = long long;
    vector<array<Ty, logn>> info1;
    vector<array<Ty, logn>> info2;

    RMQ(const vector<Ty>& A) { init(A); }
    void init(const vector<Ty>& A) {
        i64 n = A.size() - 1;
        info1.assign(A.size(), array<Ty, logn>{});
        info2.assign(A.size(), array<Ty, logn>{});
        for (int i = 1; i <= n; ++i) {
            info1[i][0] = A[i];
            info2[i][0] = A[i];
        }
        for (int j = 1; j <= logn; ++j) {
            for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
                info1[i][j] = merge1(info1[i][j - 1], info1[i + (1 << j - 1)][j - 1]);
                info2[i][j] = merge2(info2[i][j - 1], info2[i + (1 << j - 1)][j - 1]);
            }
        }
    }
    Ty QueryMax(i64 l, i64 r) {
        if (l > r) swap(l, r);
        i64 j = __lg(r - l + 1);
        return merge1(info1[l][j], info1[r - (1 << j) + 1][j]);
    };
    Ty QueryMin(i64 l, i64 r) {
        if (l > r) swap(l, r);
        i64 j = __lg(r - l + 1);
        return merge2(info2[l][j], info2[r - (1 << j) + 1][j]);
    }
    constexpr Ty merge1(const Ty& a, const Ty& b) {
        return max(a, b);
    }
    constexpr Ty merge2(const Ty& a, const Ty& b) {
        return min(a, b);
    }
};

void solve() {  
    cin >> n >> m;
    vector<i64> a(n + 1), b(n + 1);
    vector<i64> c(n + 1, 0), d(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int i = 1; i <= n; i++) {
        c[i] = c[i - 1] + a[i];
    }
    for (int i = 1; i <= n; i++) {
        d[i] = d[i - 1] + b[i];
    }

    RMQ<i64, 17> rmq1(c);
    RMQ<i64, 17> rmq2(d);

    while (m--) {
        i64 x, y;
        cin >> x >> y;

        if (x < y) {
            i64 l = 0, r = n;
            while (l <= r) {
                i64 mid = l + (r - l) / 2;

                i64 mi = min(y, y + rmq2.QueryMin(1, mid));
                i64 mx = max(x, x + rmq1.QueryMax(1, mid));

                if (mx >= mi) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }

            i64 ans = (l <= n ? l : -1);

            cout << ans << endl;

        } else if(x > y) {
            i64 l = 0, r = n;
            while (l <= r) {
                i64 mid = l + (r - l) / 2;

                i64 mi = min(x, x + rmq1.QueryMin(1, mid));
                i64 mx = max(y, y + rmq2.QueryMax(1, mid));

                if (mx >= mi) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }

            i64 ans = (l <= n ? l : -1);

            cout << ans << endl;
            
        } else {
            cout << 0 << endl;
        }
    }

}
 
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int t;
    t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
 
    return 0;
}