记录编号	573184	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAATAAAAATAA
题目名称	[POI 2011]流星	最终得分	94
用户昵称	湖岸与夜与咸鱼	是否通过	未通过
代码语言	C++	运行时间	17.097 s
提交时间	2022-07-20 19:56:53	内存使用	44.38 MiB

// 河南省实验中学 21届 关天泽

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long

using namespace std;

inline int read()
{
	register int x=0;bool flag=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')flag=0;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	if(flag) return x;
	return ~(x-1);
} 

struct Segmenttree{
	ll add , w; // w 当前区间陨石数 
	int l , r;
	int ls , rs;
};

struct Meteors{ //陨石雨数据 
	int k; // 陨石数量 
	int l , r; //陨石雨区间 
	bool opt; // 0 为 l - r , 1 为 r - m - 1 - l 
};

Segmenttree t[1200050];
int need[300050]; // 国家需要陨石数量 
Meteors que[300050];
vector<ll> belong[300050]; // 各国空间站 
ll n , m , ans[300050] , ys; // ys : 陨石雨数量 
int now; 

void build(){
	now = 1;
	t[1].l = 1;
	t[1].r = m;
}

void change(register int p , register int l , register int r , register int d){
	if(l <= t[p].l && r >= t[p].r){
		t[p].w += d * (t[p].r - t[p].l + 1);
		t[p].add += d;
		return;
	}
	register int mid = (t[p].r + t[p].l) / 2;
	if(l <= mid){
		if(t[p].ls == 0){
			now++;
			t[p].ls = now;
			t[t[p].ls].l = t[p].l;
			t[t[p].ls].r = mid;
		}
		change(t[p].ls , l , r , d);
	}
	if(r > mid){
		if(t[p].rs == 0){
			now++;
			t[p].rs = now;
			t[t[p].rs].l = mid + 1;
			t[t[p].rs].r = t[p].r;
		} 
		change(t[p].rs, l , r , d);
	}
	t[p].w = t[t[p].rs].w + t[t[p].ls].w + t[p].add * (t[p].r - t[p].l + 1);
}

ll ask(register int p , register int l , register int r , register ll tags){
	if(l <= t[p].l && r >= t[p].r){
		return t[p].w + tags * (t[p].r - t[p].l + 1);
	}
	register int mid = (t[p].l + t[p].r) / 2;
	register ll val = 0;
	if(l <= mid){
		if(t[p].ls == 0){
			now++;
			t[p].ls = now;
			t[t[p].ls].l = t[p].l;
			t[t[p].ls].r = mid;
		}
		val += ask(t[p].ls , l , r , tags + t[p].add);
	}
	if(r > mid){
		if(t[p].rs == 0){
			now++;
			t[p].rs = now;
			t[t[p].rs].l = mid + 1;
			t[t[p].rs].r = t[p].r;
		} 
		val += ask(t[p].rs , l , r , tags + t[p].add);
	}
	return val;
}

void solve(register int l , register int r , queue<ll>country){ // l , r 为答案范围 , country : 当前范围中国家 
	if(country.empty()){
		return;
	}
	if(l == r){
		while(!country.empty()){
			ans[country.front()] = l;
			country.pop();
		}
		return;
	}
	register int mid = (l + r) / 2;
	for(register int i = l;i <= mid;i++){
		if(!que[i].opt){
			change(1 , que[i].l , que[i].r , que[i].k);
		}
		if(que[i].opt){
			change(1 , que[i].l , m , que[i].k);
			change(1 , 1 , que[i].r , que[i].k);
		}
	}
	queue<ll> q_l , q_r;
	while(!country.empty()){
		register int now = country.front();
		country.pop();
		register ll tot = 0;
		for(register ll i = 0;i < belong[now].size() && tot < need[now];i++){
			tot += ask(1 , belong[now][i] , belong[now][i] , 0);
		}
		if(tot >= need[now]){
			q_l.push(now);
		}
		else{
			need[now] -= tot;
			q_r.push(now);
		}
	}
	for(register int i = l;i <= mid;i++){
		if(!que[i].opt){
			change(1 , que[i].l , que[i].r , -que[i].k);
		}
		if(que[i].opt){
			change(1 , que[i].l , m , -que[i].k);
			change(1 , 1 , que[i].r , -que[i].k);
		}
	}
	if(!q_l.empty()){
		solve(l , mid , q_l);
	}
	if(!q_r.empty()){
		solve(mid + 1 , r , q_r);
	}
	return;
}

int main(){
	freopen("meteors.in" , "r" , stdin);
	freopen("meteors.out" , "w" , stdout);
	n = read();
	m = read();
	build();
	for(register int i = 1;i <= m;i++){
		ll x;
		x = read();
		belong[x].push_back(i);
	}
	for(register int i = 1;i <= n;i++){
		ll x;
		x = read();
		need[i] = x;
	}
	ys = read();
	for(register int i = 1;i <= ys;i++){
		ll x , y , z;
		x = read();
		y = read();
		z = read();
		que[i].k = z;
		que[i].l = x;
		que[i].r = y;
		if(y >= x){
			que[i].opt = 0;
		}
		else{
			que[i].opt = 1;
		}
	}
	queue<ll> country;
	for(register int i = 1;i <= n;i++){
		country.push(i);
	}
	solve(1 , ys + 1 , country);
	for(register int i = 1;i <= n;i++){
		if(ans[i] <= ys){
			printf("%d\n",ans[i]);
		}
		else{
			printf("NIE\n");
		}
	}
	return 0;
}