problem

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const int N = 100000;

struct Query {
    ll x, y;
    int l, r;
};

Query queries[N];

vector<int> queriesByL[N + 1];
vector<int> queriesByR[N + 1];

int a[N];

pll tree[1 << 18];

#define root 0, m, 0
#define lx 2*x+1
#define rx 2*x+2
#define lc l, m, lx
#define rc m, r, rx

void treeAdd(int dest, ll first, ll second, int l, int r, int x) {
    tree[x].first += first;
    tree[x].second += second;
    if (l + 1 != r) {
        int m = (l + r) / 2;
        if (dest < m) {
            treeAdd(dest, first, second, lc);
        } else {
            treeAdd(dest, first, second, rc);
        }
    }
}

int treeFind(ll goal, ll mult, int l, int r, int x) {
    if (l + 1 == r) {
        return l;
    }
    int m = (l + r) / 2;
    if (tree[lx].first + tree[lx].second * mult >= goal) {
        return treeFind(goal, mult, lc);
    } else {
        return treeFind(goal - tree[lx].first - tree[lx].second * mult, mult, rc);
    }
}

int main() {
    // freopen("in.txt", "r", stdin);

    int n;
    cin >> n;

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    int m;
    cin >> m;

    for (int i = 0; i < m; ++i) {
        Query& q = queries[i];
        cin >> q.l >> q.r >> q.x >> q.y;
        q.l -= 1;
        q.x -= (q.l - 1) * q.y;
        queriesByL[q.l].push_back(i);
        queriesByR[q.r].push_back(i);
    }

    for (int i = 0; i < n; ++i) {
        for (int index : queriesByR[i]) {
            treeAdd(index, -queries[index].x, -queries[index].y, root);
        }
        for (int index : queriesByL[i]) {
            treeAdd(index, +queries[index].x, +queries[index].y, root);
        }

        if (a[i] >= 0) {
            cout << 0 << ' ';
            continue;
        }
        if (a[i] + tree[0].first + tree[0].second * i < 0) {
            cout << -1 << ' ';
            continue;
        }
        cout << treeFind(-a[i], i, root) + 1 << ' ';
    }
    cout << endl;


    return 0;
}