RT………………

真的要死了，换了114514种写法调了半天了……叫了几个机房的人帮忙调调了20多分钟还是出不来……

#include<bits/stdc++.h>
#define lowbit(x) x&-x
#define int long long
using namespace std;
int n,m,k;
int cnt=0;
vector<int> sta[600005];
int p[600005];
struct node{
	int x,y,z;
}update[600005];
int ans[600005];
struct point{
	int id,x;
}q[600005],q1[600005],q2[600005];
int c[600005];
int ask(int x){
	int sum=0;
	while(x){
		sum+=c[x];
		x-=lowbit(x);
	}
	return sum;
}
void add(int x,int y){
	while(x<=m){
		c[x]+=y;
		x+=lowbit(x);
//		printf("%d\n",x);
	}
	return;
}
void upd(int lt,int rt,int k){
	add(lt,k);
	add(rt+1,-k);
	return;
}
void solve(int lt,int rt,int qx,int qy){
//	printf("%d %d %d %d\n",lt,rt,qx,qy);
	if(qx>qy){
		return;
	}
	if(lt==rt){
		for(int i=qx;i<=qy;i++){
			ans[q[i].id]=lt;
		}
		return;
	}
	int mid=lt+rt>>1;
	int cnt1=0,cnt2=0;
	for(int i=(lt);i<=mid;i++){
		int x=update[i].x;
		int y=update[i].y;
		int z=update[i].z;
		if(x<=y){
			upd(x,y,z);
		}
		else{
			upd(x,m,z);
			upd(1,y,z);
		}
	}
	for(int i=qx;i<=qy;i++){
		int sum=0;
		for(int j=0;j<sta[i].size();j++){
			sum+=ask(sta[i][j])/*+ask(sta[i][j]+m)*/;
			if(sum>=q[i].x) break;
		} 
		if(sum>=q[i].x){
			q1[++cnt1]=q[i];
		}
		else{
			q[i].x-=sum;
			q2[++cnt2]=q[i];
		}
	}
	for(int i=(lt);i<=mid;i++){
		int x=update[i].x;
		int y=update[i].y;
		int z=update[i].z;
		if(x<=y){
			upd(x,y,-z);
		}
		else{
			upd(x,m,-z);
			upd(1,y,-z);
		}
	}
	for(int i=qx;i<=qx+cnt1-1;i++)q[i]=q1[i-qx+1];
	for(int i=qx+cnt1;i<=qy;i++)q[i]=q2[i-qx-cnt1+1];
	solve(lt,mid,qx,qx+cnt1-1);
	solve(mid+1,rt,qx+cnt1,qy);
	return;
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++){
		int x;
		scanf("%lld",&x);
		sta[x].push_back(i);
//		sta[x].push_back(i+m);
	}
	for(int i=1;i<=n;i++){
		scanf("%lld",&q[i].x);
		q[i].id=i;
	}
	scanf("%lld",&k);
	for(int i=1;i<=k;i++){
		int x,y,z;
		scanf("%lld%lld%lld",&x,&y,&z);
		update[i]=node{x,y,z};
	}
	solve(1,k+1,1,n);
	for(int i=1;i<=n;i++){
		if(ans[i]==k+1)puts("NIE");
		else printf("%lld\n",ans[i]);
	}
	return 0;
}
/*
3 5
1 3 2 1 3
10 5 7
3
4 2 4
1 3 1
3 5 2
*/