卡常

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;

int n,m,k;
int ans[300005];
ll t[300005];
struct node{int id;ll w;};
node q[300005];
node q1[300005];
node q2[300005];
bool mp[300005];
struct opt{int l,r;ll w;};
opt g[600005];
vector <int> gg[300005];

inline void in(int &n){
	n=0;
	char c=getchar();
	while(c<'0' || c>'9') c=getchar();
	while(c>='0'&&c<='9') n=n*10+c-'0',c=getchar();
	return ;
}

inline void inl(ll &n){
	n=0;
	char c=getchar();
	while(c<'0' || c>'9') c=getchar();
	while(c>='0'&&c<='9') n=n*10+c-'0',c=getchar();
	return ;
}

inline void add(int x,ll k){while(x<=m) t[x]+=k,x+=x&-x;return ;}
inline ll ask(int x){ll s=0;while(x) s+=t[x],x^=x&-x;return s;}

void ZTEF(int l,int r,int L,int R){
	if(l==r){
		add(g[l<<1].l,g[l<<1].w);
		add(g[l<<1].r+1,-g[l<<1].w);
		if(mp[l<<1]) add(g[l<<1|1].l,g[l<<1|1].w),add(g[l<<1|1].r+1,-g[l<<1|1].w);
		for(int i=L;i<=R;i++){
			int x=q[i].id;
			ll s=0;
			for(int j=0;j<gg[x].size();j++) s+=ask(gg[x][j]);
			if(s>=q[i].w) ans[q[i].id]=l;
			else ans[q[i].id]=-1;
		}
		add(g[l<<1].l,-g[l<<1].w);
		add(g[l<<1].r+1,g[l<<1].w);
		if(mp[l<<1]) add(g[l<<1|1].l,-g[l<<1|1].w),add(g[l<<1|1].r+1,g[l<<1|1].w);
		return ;
	}
	int mid=l+r>>1;
	for(int i=l;i<=mid;i++){
		add(g[i<<1].l,g[i<<1].w);
		add(g[i<<1].r+1,-g[i<<1].w);
		if(mp[i<<1]) add(g[i<<1|1].l,g[i<<1|1].w),add(g[i<<1|1].r+1,-g[i<<1|1].w);
	}
	int t1=0,t2=0;
	for(int i=L;i<=R;i++){
		int x=q[i].id;
		ll s=0;
		for(int j=0;j<gg[x].size();j++) s+=ask(gg[x][j]);
		if(s>=q[i].w) q1[++t1]=q[i];
		else q[i].w-=s,q2[++t2]=q[i];
	}
	for(int i=1;i<=t1;i++) q[i+L-1]=q1[i];
	for(int i=1;i<=t2;i++) q[i+L+t1-1]=q2[i];
	for(int i=l;i<=mid;i++){
		add(g[i<<1].l,-g[i<<1].w);
		add(g[i<<1].r+1,g[i<<1].w);
		if(mp[i<<1]) add(g[i<<1|1].l,-g[i<<1|1].w),add(g[i<<1|1].r+1,g[i<<1|1].w);
	}
	ZTEF(l,mid,L,L+t1-1);
	ZTEF(mid+1,r,L+t1,R);
}

int main(){
	in(n),in(m);
	int x;
	for(int i=1;i<=m;i++)
		in(x),gg[x].push_back(i);
	for(int i=1;i<=n;i++) inl(q[i].w),q[i].id=i;
	opt tmp,tt;
	in(k);
	for(int i=1;i<=k;i++){
		in(tmp.l),in(tmp.r),inl(tmp.w);
		if(tmp.l>tmp.r){
			tt=tmp;
			tt.r=m;
			g[i<<1]=tt;
			tt=tmp;
			tt.l=1;
			g[i<<1|1]=tt;
			mp[i<<1]=1;
		}
		else g[i<<1]=tmp;
	}
	ZTEF(1,k,1,n);
	for(int i=1;i<=n;i++){
		if(ans[i]==-1) printf("NIE\n");
		else printf("%d\n",ans[i]);
	}

	return 0;
}