CF1490G WA

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#define dbg(...) logger(#__VA_ARGS__, __VA_ARGS__)
template <typename... Args> void logger(string vars, Args &&... values)
{
    cerr << vars << " = ";
    string delim = "";
    (..., (cerr << delim << values, delim = ", "));
    cerr << endl;
}

template <class T> inline auto vv(int m) { return vector<vector<T>>(m, vector<T>(m)); }
template <class T> inline auto vv(int m, int n) { return vector<vector<T>>(m, vector<T>(n)); }
template <class T, T init> inline auto vv(int m) { return vector<vector<T>>(m, vector<T>(m, init)); }
template <class T, T init> inline auto vv(int m, int n) { return vector<vector<T>>(m, vector<T>(n, init)); }

template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;
using pii = pair<int, int>;
using vl = vector<ll>;
using vi = vector<int>;

int main(int argc, char **argv)
{
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<ll> a(n);
        ll acc = 0;
        vector<ll> pref;
        map<ll, int> cmap;

        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            acc += a[i];
            if (acc >= 0 && (pref.size() == 0 || acc > pref.back())) {
                pref.push_back(acc);
                cmap[acc] = i;
            }
        }

        ll x;
        auto calc = [&](ll idx, ll x) { return (x - pref[idx]) / acc + idx; };
        auto check = [&](ll idx, ll x) {
            if (idx == 0)
                return calc(idx, x) < calc(idx + 1, x);
            if (idx == n - 1)
                return calc(idx - 1, x) < calc(idx, x);
            return calc(idx - 1, x) < calc(idx, x) && calc(idx, x) < calc(idx + 1, x);
        };
        auto find = [&](ll x) {
            /*
            ll lb = 0, ub = pref.size(), cnt = ub - lb, it, step;
            while (cnt) {
                it = lb, step = cnt / 2, it += step;
                if (!check(it, x)) {
                    lb = it + 1;
                    cnt -= step + 1;
                } else
                    cnt = step;
            }
            return calc(lb, x);
            */
            int l = 0, r = pref.size(), mid = 0;
            while (l < r) {
                int mid = (l + r) / 2;
                if (mid == 0) {
                    if (calc(mid, x) <= calc(mid + 1, x)) {
                        l = mid;
                    } else {
                        r = mid + 1;
                    }
                    break;
                }
                if (mid == n - 1) {
                    if (calc(mid, x) <= calc(mid - 1, x)) {
                        l = mid;
                    } else {
                        r = mid - 1;
                    }
                    break;
                }
                ll mm1 = calc(mid - 1, x), mm = calc(mid, x), mp1 = calc(mid, x);
                if (mm1 >= mm && mm <= mp1) {
                    l = mid;
                    break;
                }
                if (mm1 < mm && mm < mp1) {
                    r = mid - 1;
                } else if (mm1 > mm && mm > mp1) {
                    l = mid + 1;
                }
            }
            return calc(l, x);
        };
        for (int i = 0; i < m; ++i) {
            cin >> x;
            int lb = lower_bound(pref.begin(), pref.end(), x) - pref.begin();
            if (lb != pref.size()) {
                dbg(x, lb, "case 1");
                cout << cmap[pref[lb]] << ' ';
            } else if (acc > 0) {
                cout << find(x) << ' ';
                dbg(x, lb, find(x), "case 2");
            } else {
                dbg(x, lb, "case 3");
                cout << -1 << ' ';
            }
        }
        cout << '\n';
    }
    return 0;
};