D.cpp

#include<iostream>
#include<fstream>
#include<memory.h>

using namespace std;
typedef long long ll;
const int N = 100000 + 10;
const int sq = 333;

int res[N], a[N], b[N], l[N], r[N];
ll x[N], y[N], xx[N], yy[N], need[N];

int main()
{
    ios_base::sync_with_stdio(true);
    freopen("jam.in", "r", stdin);
    freopen("jam.out", "w", stdout);
    int n;
    cin >> n;
    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++) res[i] = -1;
    for (int i = 1; i <= n; i++)
    {
        need[i] = b[i] - a[i];
        if (need[i] <= 0) res[i] = 0;
    }
    int m;
    cin >> m;
    for (int i = 1; i <= m; i++) cin >> l[i] >> r[i] >> x[i] >> y[i];
    for (int lf = 1; lf <= m; lf += sq)
    {
        int rh = std::min(lf + sq - 1, m);
        memset(xx, 0, sizeof(xx));
        memset(yy, 0, sizeof(yy));
        for (int i = lf; i <= rh; i++)
        {
            xx[l[i]] += x[i] - y[i];
            yy[l[i]] += y[i];
            xx[r[i] + 1] -= x[i] + y[i] * (r[i] - l[i]);
            yy[r[i] + 1] -= y[i];
        }
        ll sum = 0, coef = 0;
        for (int i = 1; i <= n; i++)
        {
            coef += yy[i];
            sum += xx[i] + coef;
            if (res[i] != -1) continue;
            if (need[i] <= sum)
            for (int j = lf; j <= rh; j++)
            {
                if (!(l[j] <= i && i <= r[j])) continue;
                need[i] -= x[j] + y[j] * (i - l[j]);
                if (need[i] <= 0) { res[i] = j; break; }
            }
            else need[i] -= sum;
        }
    }
    for (int i = 1; i <= n; i++) cout << res[i] << " ";
    return 0;
}