代码

#include<bits/stdc++.h>
#define int __int128
#define lowbit(x) ((x)&(-x))
using namespace std ;
int n , m , ans[312345] , temp[312345] , somek[312345] , tr[6123456] , k , cnt=0 ;
vector<int> o[312345] ;
struct node{
	int l , r , opt , k , i ;
}a[6123415],q1[3112345],q2[3121345],somea[3112345];
void change(int l,int r,int w){
	while(l<=n*10){
		tr[l] += w ;
		l += lowbit(l) ;
	}
	r++ ;
	while(r<=n*10){
		tr[r] -= w ;
		r += lowbit(r) ;
	}
}
int ask(int x){
	int sum=0;
	while(x>0){
		sum += tr[x];
		x -= lowbit(x);
	}
	return sum ;
}
inline void read(int &x){
    bool f=1;x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=!f;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=(f?x:-x);return;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');return;
}
void solve(int l,int r,int L,int R){
	if(L>R) return ;
	if(l==r){
		for(int i=L;i<=R;i++)
			if(a[i].opt==2) ans[a[i].i] = l ;
		return ;
	}
	int mid=(l+r)>>1 , tot1=0 , tot2=0 ;
	for(int i=L;i<=R;i++){
		if(a[i].opt==1){
			if(a[i].i<=mid){
				if(a[i].l>a[i].r){
					change(a[i].l,m,a[i].k) ;
					change(1,a[i].r,a[i].k) ;
				}else
					change(a[i].l,a[i].r,a[i].k) ;
				q1[++tot1] = a[i] ;
			}else
				q2[++tot2] = a[i] ;
		}else{
			int sum=0 ;
			for(auto x:o[a[i].i])
				sum += ask(x) ;
			if(a[i].k<=sum){
				q1[++tot1] = a[i] ;
			}else
				a[i].k -= sum , q2[++tot2] = a[i] ;
		}
	}
	for(int i=1;i<=tot1;i++){
		a[L+i-1] = q1[i] ;
		if(q1[i].opt==1){
			if(q1[i].l>q1[i].r){
				change(q1[i].l,m,-q1[i].k) ;
				change(1,q1[i].r,-q1[i].k) ;
			}else{
				change(q1[i].l,q1[i].r,-q1[i].k) ;
			}
		}
	}
	for(int i=1;i<=tot2;i++)
		a[tot1+L+i-1] = q2[i] ;
	solve(l,mid,L,L+tot1-1) ;
	solve(mid+1,r,L+tot1,R) ;
}
int find(int num){
	int sum=0 ;
	for(auto x:o[num])
		sum += ask(x) ;
	return sum ;
}
signed main(){
	read(n) ;
	read(m) ;
	for(int i=1;i<=m;i++){
		int temp ;
		read(temp) ;
		o[temp].push_back(i) ;
	}
	for(int i=1;i<=n;i++)
		read(temp[i]) ;
	read(k) ;
	for(int i=1;i<=k;i++){
		read(a[i].l) ;
		read(a[i].r) ;
		read(a[i].k) ;
		a[i].opt = 1 ;
		a[i].i = i ;
		somea[i] = a[i] ;
	}
	cnt = k ;
	for(int i=1;i<=n;i++){
		cnt++ ;
		somek[i] = temp[i] ;
		a[cnt].i = i ;
		a[cnt].k = temp[i] ;
		a[cnt].opt = 2 ;
	}
	solve(1,k,1,cnt) ;
	for(int i=1;i<=k;i++)
		if(somea[i].l>somea[i].r){
			change(somea[i].l,m,somea[i].k) ;
			change(1,somea[i].r,somea[i].k) ;
		}else
			change(somea[i].l,somea[i].r,somea[i].k) ;
	for(int i=1;i<=n;i++,putchar('\n'))
		if(find(i)>=somek[i]) write(ans[i]) ;
		else printf("NIE") ;
	return 0 ;
}