Meteors

#include<bits/stdc++.h>
using namespace std;

typedef long double ld;
typedef long long int ll;
typedef pair<int,int> pi;
typedef pair<long long,long long> pll;

#define endl '\n'
#define ff first
#define ss second
#define pb push_back
#define int long long
#define sz(v) (int)v.size()
#define inf 2147483647
#define llinf 9223372036854775807
#define all(v) v.begin(),v.end()
#define bp(n) __builtin_popcountll(n)
#define f(i,l,r) for(long long i=l;i<=r;i++)
#define rf(i,r,l) for(long long i=r;i>=l;i--)
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)

template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream& operator<<(ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }


const int N=3e5+5,mod=1e9+7,bit=61;

template<typename T>
class fenwick
{
    public:
        vector<T> fen;
        int n;

        fenwick() {}

        fenwick(int _n,T val=T())
        {
            n=_n;
            fen=vector<T> (n+1,val);
        }

        void reset()
        {
            for(int i=0;i<(int)fen.size();i++)
            {
                fen[i]=(T)0;
            }
        }

        T merge(T a,T b)
        {
            return a+b;
        }

        void update(int idx,T val)
        {
            while(idx<=n)
            {
                fen[idx]=merge(fen[idx],val);
                idx+=(idx & -idx);
            }
        }

        T query(int idx)
        {
            T ans{};
            while(idx>0)
            {
                ans=merge(ans,fen[idx]);
                idx-=(idx & -idx);
            }
            return ans;
        }

        T from(int l,int r)
        {
            return query(r)-query(l-1);
        }
};

vector<int> mid[N],adj[N];
int req[N],l[N],r[N],s[N],e[N],add[N],n,m,q;
fenwick<int> obj;

void apply(int x)
{
    if(s[x]<=e[x])
    {
        obj.update(s[x],add[x]);
        obj.update(e[x]+1,-add[x]);
    }
    else
    {
        obj.update(1,add[x]);
        obj.update(e[x]+1,-add[x]);
        obj.update(s[x],add[x]);
    }
}

signed main()
{
    fast;

    cin>>n>>m;

    obj = fenwick<int> (m);

    for(int i=1;i<=m;i++)
    {
        int p;
        cin>>p;
        adj[p].push_back(i);
    }

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

    cin>>q;
    for(int i=1;i<=q;i++)
    {
        cin>>s[i]>>e[i]>>add[i];
    }

    for(int i=1;i<=n;i++)
    {
        l[i]=1;
        r[i]=q+1;
    }

    bool done=0;
    while(!done)
    {
        done=1;
        obj.reset();
        for(int i=1;i<=n;i++)
        {
            if(l[i]!=r[i])
            {
                done=0;
                mid[(l[i]+r[i])>>1].push_back(i);
            }
        }

        for(int i=1;i<=q;i++)
        {
            apply(i);
            while(!mid[i].empty())
            {
                int par=mid[i].back();
                int sum=0;
                bool sat=0;
                for(auto &v:adj[par])
                {
                    sum+=obj.query(v);
                    if(sum >= req[par])
                    {
                        sat=1;
                        break;
                    }
                }
                if(sat)
                {
                    r[par]=i;
                }
                else
                {
                    l[par]=i+1;
                }
                mid[i].pop_back();
            }
        }
    }

    for(int i=1;i<=n;i++)
    {
        assert(l[i] == r[i]);
        if(r[i] <= q)
        {
            cout<<r[i]<<endl;
        }
        else
        {
            cout<<"NIE"<<endl;
        }
    }
    return 0;
}