悬关，整体二分 WA，TLE 各两点

#include<bits/stdc++.h>
#define int long long

using namespace std;

struct date
{
	int id, val;
}q[300010], q1[300010], q2[300010];
struct node
{
	int l, r, a;
}up[300010];
int n, m, k;
int tree[1200010], lazy[1200010];
vector<int> p[300010];
int ans[300010];

void pushdown(int id, int l, int r)
{
	if(!lazy[id]) return;
	if(l == r)
	{
		lazy[id] = 0;
		return;
	}
	int mid = (l + r) >> 1;
	tree[id * 2] += lazy[id] * (mid - l + 1);
	tree[id * 2 + 1] += lazy[id] * (r - mid);
	lazy[id * 2] += lazy[id];
	lazy[id * 2 + 1] += lazy[id];
	lazy[id] = 0;
}

void updata(int id, int l, int r, int L, int R, int d)
{
	if(l > R || r < L) return;
	if(l >= L && r <= R)
	{
		tree[id] += d * (r - l + 1);
		lazy[id] += d;
		return;
	}
	pushdown(id, l, r);
	int mid = (l + r) >> 1;
	updata(id * 2, l, mid, L, R, d);
	updata(id * 2 + 1, mid + 1, r, L, R, d);
	tree[id] = tree[id * 2] + tree[id * 2 + 1];
}

int query(int id, int l, int r, int d)
{
	pushdown(id, l, r);
	if(l == r) return tree[id];
	int mid = (l + r) >> 1;
	if(mid >= d) return query(id * 2, l, mid, d);
	else return query(id * 2 + 1, mid + 1, r, d);
}

void fz(int l, int r, int L, int R)
{
//	cout << l << " " << r << " " << L << " " << R << "\n";
	if(l == r)
	{
		for(int i = L;i <= R;i ++) ans[q[i].id] = l;
		return;
	}
	if(l > r || L > R) return;
	int mid = (l + r) >> 1, c1 = 0, c2 = 0;
	for(int i = l;i <= mid;i ++)
	{
		if(up[i].l <= up[i].r) updata(1, 1, m, up[i].l, up[i].r, up[i].a);
		else updata(1, 1, m, up[i].l, m, up[i].a), updata(1, 1, m, 1, up[i].r, up[i].a);
	}
	for(int i = L;i <= R;i ++)
	{
		int sum = 0;
		for(auto j : p[q[i].id]) sum += query(1, 1, m, j);
//		cout << sum << " ";
		if(sum >= q[i].val) q1[++ c1] = q[i];
		else q[i].val -= sum, q2[++ c2] = q[i];
	}
//	cout << "\n";
	for(int i = 1;i <= c1;i ++) q[L + i - 1] = q1[i];
	for(int i = 1;i <= c2;i ++) q[L + c1 + i - 1] = q2[i];
	for(int i = l;i <= mid;i ++)
	{
		if(up[i].l <= up[i].r) updata(1, 1, m, up[i].l, up[i].r, -up[i].a);
		else updata(1, 1, m, up[i].l, m, -up[i].a), updata(1, 1, m, 1, up[i].r, -up[i].a);
	}
	fz(l, mid, L, L + c1 - 1);
	fz(mid + 1, r, L + c1, R);
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9'){ x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
    return x * f;
}

inline void write(int x)
{
    if(x < 0){ putchar('-'); x = -x; }
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

signed main()
{
	// ios::sync_with_stdio(0);
	// cin.tie(0);
	// cout.tie(0);
	n = read(), m = read();
	for(int i = 1;i <= m;i ++)
	{
		int x;
		x = read();
		p[x].push_back(i);
	}
	for(int i = 1;i <= n;i ++)
	{
		int x;
		x = read();
		q[i] = {i, x};
	}
	k = read();
	for(int i = 1;i <= k;i ++) up[i].l = read(), up[i].r = read(), up[i].a = read();
	fz(1, k + 1, 1, n);
	for(int i = 1;i <= n;i ++)
	{
		if(ans[i] > k) cout << "NIE";
		else write(ans[i]);
        puts("");
	}
	return 0;
}