首先环可以变成链来处理，对于l>r的情况就是修改区间[1,r],[l,mx]
然后不难想到整体二分，二分答案k,然后算1~k场流星雨对国家的贡献
然后判定将国家划分变成子问题解决，没什么难的
终于不是tle，poi良心了一把
type way=record
po,next:longint;
end;
que=record
p,n:longint;
end;
an=record
l,r,v:longint;
end;
var a:array[..] of an;
qq,q:array[..] of que;
e:array[..] of way;
c:array[..] of int64;
p,ans,h:array[..] of longint;
v:array[..] of boolean;
tot,t,j,n,m,x,i:longint;
s:int64; function lowbit(x:longint):longint;
begin
exit(x and (-x));
end; procedure add(x,y:longint);
begin
e[i].po:=i;
e[i].next:=p[x];
p[x]:=i;
end; procedure ins(x:longint;w:int64);
begin
while x<=n do
begin
if not v[x] then //清理标记
begin
inc(tot);
h[tot]:=x;
v[x]:=true;
end;
c[x]:=c[x]+w;
x:=x+lowbit(x);
end;
end; function ask(x:longint):int64;
begin
ask:=;
while x> do
begin
ask:=ask+c[x];
x:=x-lowbit(x);
end;
end; procedure work(f,t,l,r:longint);
var mid,l1,l2:longint;
begin
if f>t then exit;
if l>r then exit;
mid:=(l+r) shr ;
tot:=;
for i:=l to mid do
if a[i].l<=a[i].r then
begin
ins(a[i].l,a[i].v);
ins(a[i].r+,-a[i].v);
end
else begin
ins(,a[i].v);
ins(a[i].r+,-a[i].v);
ins(a[i].l,a[i].v);
end; l1:=f;
l2:=t;
for i:=f to t do
begin
j:=p[q[i].p];
s:=;
while j<> do
begin
s:=s+ask(e[j].po);
if s>=q[i].n then
begin
qq[l1]:=q[i];
inc(l1);
ans[q[i].p]:=mid;
break;
end;
j:=e[j].next;
end;
if s<q[i].n then
begin
q[i].n:=q[i].n-s; //对于还不够的国家，直接把这部分贡献减去即可，下次直接处理mid之后的流星雨的贡献
qq[l2]:=q[i];
dec(l2);
end;
end;
for i:= to tot do
begin
c[h[i]]:=;
v[h[i]]:=false;
end;
for i:=f to t do
q[i]:=qq[i];
work(f,l1-,l,mid-);
work(l2+,t,mid+,r);
end; begin
readln(m,n);
for i:= to n do
begin
read(x);
add(x,i);
end;
for i:= to m do
begin
read(q[i].n);
q[i].p:=i;
end;
readln(t);
for i:= to t do
readln(a[i].l,a[i].r,a[i].v);
work(,m,,t);
for i:= to m do
if ans[i]= then writeln('NIE')
else writeln(ans[i]);
end.