整体二分经典题.考虑单个询问如何二分:二分天数$mid$,前$mid$天区间加,最后询问单点.差分/树状数组 维护即可.

然后套上整体二分的板子就好了.(PS:整体二分中用差分时间复杂度就不对了,会退化到平方级别)
时间复杂度$\mathcal O(n\log n\log k)$

代码直接贴了之前在LOJ写的.

/**********/
#define MAXN 300011
struct one
{
    ll l,r,val;
}stone[MAXN];
std::vector<ll>g[MAXN];
ll need[MAXN],ans[MAXN],a[MAXN],la[MAXN],ra[MAXN];
ll n,m;
struct BIT
{
    ll t[MAXN];
    #define lowb (i&-i)
    void modify(ll i,ll k)
    {
        while(i<=m)
        {
            t[i]+=k;
            i+=lowb;
        }
    }
    ll Qsum(ll i)
    {
        ll res=0;
        while(i)
        {
            res+=t[i];
            i-=lowb;
        }
        return res;
    }
}t;

void solve(ll l,ll r,ll begin,ll end)
{
    if(begin>end)return;
    if(l==r)
    {
        for(ll i=begin;i<=end;++i)
            ans[a[i]]=l;
        return;
    }
    ll mid=(l+r)>>1;
    for(ll i=l;i<=mid;++i)
    {
        ll val=stone[i].val;
        if(stone[i].l<=stone[i].r)t.modify(stone[i].l,val),t.modify(stone[i].r+1,-val);
        else t.modify(stone[i].l,val),t.modify(1,val),t.modify(stone[i].r+1,-val);
    }
    ll itl=0,itr=0;
    for(ll i=begin;i<=end;++i)
    {
        ll cnt=0;
        for(std::vector<ll>::iterator it=g[a[i]].begin();it!=g[a[i]].end();++it)
        {
            cnt+=t.Qsum(*it);
            if(cnt>=need[a[i]])break;
        }   
        if(cnt<need[a[i]])need[a[i]]-=cnt,ra[++itr]=a[i];
        else la[++itl]=a[i];
    }
    for(ll i=l;i<=mid;++i)
    {
        ll val=stone[i].val;
        if(stone[i].l<=stone[i].r)t.modify(stone[i].l,-val),t.modify(stone[i].r+1,val);
        else t.modify(stone[i].l,-val),t.modify(1,-val),t.modify(stone[i].r+1,val);
    }
    for(ll i=1;i<=itl;++i)a[begin+i-1]=la[i];
    for(ll i=1;i<=itr;++i)a[begin+itl+i-1]=ra[i];
    solve(l,mid,begin,begin+itl-1),solve(mid+1,r,begin+itl,end);
}
int main()
{
    //freopen("data.in","r",stdin);
    n=read(),m=read();
    for(ll i=1;i<=m;++i)g[read()].push_back(i);
    for(ll i=1;i<=n;++i)need[i]=read(),a[i]=i;
    ll k=read();
    for(ll i=1;i<=k;++i)stone[i].l=read(),stone[i].r=read(),stone[i].val=read();
    stone[k+1].l=1,stone[k+1].r=m,stone[k+1].val=INF;
    solve(1,k+1,1,n);
    for(ll i=1;i<=n;++i)
        if(ans[i]>k)puts("NIE");
        else printf("%lld\n",ans[i]); 
    return 0;
}