P3527

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e5+5;
int n,m,o[N],p[N],l[N],r[N],a[N],k,ans[N];
vector<int>vec,num[N];
struct segtree{
	int l,r,sum,add,siz;
}seg[N*4];
void build(int u,int l,int r){
	seg[u].l=l,seg[u].r=r,seg[u].sum=seg[u].add=0,seg[u].siz=r-l+1;
	if(l==r){
		return;
	}
	int mid=(l+r)>>1;
	build(u*2,l,mid),build(u*2+1,mid+1,r);
}
void pushup(int u){
	seg[u].sum=seg[u*2].sum+seg[u*2+1].sum;
}
void add(int u,int x){
	seg[u].add+=x,seg[u].sum+=x*seg[u].siz;
}
void pushdown(int u){
	add(u*2,seg[u].add),add(u*2+1,seg[u].add),seg[u].add=0;
}
void update(int u,int l,int r,int x){
	if(seg[u].l>=l&&seg[u].r<=r){
		add(u,x);
		return;
	}
	pushdown(u);
	int mid=(seg[u].l+seg[u].r)>>1;
	if(l<=mid){
		update(u*2,l,r,x);
	}
	if(r>mid){
		update(u*2+1,l,r,x);
	}
	pushup(u);
}
int query(int u,int x){
	if(seg[u].l==seg[u].r){
		return seg[u].sum;
	}
	pushdown(u);
	int mid=(seg[u].l+seg[u].r)>>1;
	if(x<=mid){
		return query(u*2,x);
	}
	return query(u*2+1,x);
}
void solve(int x,int y){
	if(x==y){
		int num[N]={};
	    if(l[x]<=r[x]){
	    	for(int i=l[x];i<=r[x];i++){
	    	    num[o[i]]+=a[x];
		    }
		}
		else{
			for(int i=l[x];i<=m;i++){
				num[o[i]]+=a[x];
			}
			for(int i=1;i<=r[x];i++){
				num[o[i]]+=a[x];
			}
		}
		for(int i:vec){
			if(num[i]>=p[i]){
				ans[i]=x;
			}
		}
		return;
	}
	build(1,1,m); 
	int mid=(x+y)>>1;
	for(int i=x;i<=mid;i++){
		if(l[i]<=r[i]){
			update(1,l[i],r[i],a[i]);
		}
		else{
			update(1,l[i],m,a[i]),update(1,1,r[i],a[i]);
		}
	}
	vector<int>A,B;
	for(int i:vec){
		int tmp=0;
		for(int j:num[i]){
			tmp+=query(1,j);
		}
		if(tmp>=p[i]){
			A.push_back(i);
		}
		else{
			B.push_back(i),p[i]-=tmp;
		}
	}
	vec=A,solve(x,mid),vec=B,solve(mid+1,y);
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>o[i],num[o[i]].push_back(i);
	}
	for(int i=1;i<=n;i++){
		cin>>p[i],vec.push_back(i);
	}
	cin>>k;
	for(int i=1;i<=k;i++){
		cin>>l[i]>>r[i]>>a[i];
	}
	solve(1,k);
	for(int i=1;i<=n;i++){
		if(!ans[i]){
			cout<<"NIE\n";
		}
		else{
			cout<<ans[i]<<'\n';
		}
	}
}