百度空间马上要下架的说，赶快把最后一点题解补完，然后搬家
这是一道不错的题，首先注意询问是满足区间减法的，我们把他变成前缀和表示
设我们询问[1,r]中的点和z的LCA深度和，假设我们确定一个根，不难发现一个有趣的事情
点z和点i的LCA深度=z和i到根公共路径（LCA到根的路径）上点的个数！
也就是说，当我们查询时，我们只要知道，[1,r]上的点到根路径上的点在z到根上出现的次数和
所以不难想到离线的做法，按照编号的顺序，每次做到点i，就把点i到根路径上点权值+1
询问的时候我们只要查询z到根路径上点权值和即可，显然我们可以用树链剖分+线段树维护
const mo=;
type node=record
po,next:longint;
end;
que=record
x,y,p,op:longint;
end; var p,c,top,ans,fa,size:array[..] of longint;
tree,lazy:array[..*] of longint;
q:array[..] of que;
e:array[..] of node;
t,l,r,x,i,j,n,m:longint; procedure swap(var a,b:que);
var c:que;
begin
c:=a;
a:=b;
b:=c;
end; procedure add(x,y:longint);
begin
e[i].po:=y;
e[i].next:=p[x];
p[x]:=i;
end; procedure dfs1(x:longint);
var i,y:longint;
begin
size[x]:=;
i:=p[x];
while i<> do
begin
y:=e[i].po;
fa[y]:=x;
dfs1(y);
size[x]:=size[x]+size[y];
i:=e[i].next;
end;
end; procedure dfs2(x:longint);
var i,y,q:longint;
begin
inc(t);
c[x]:=t;
q:=n+;
i:=p[x];
while i<> do
begin
y:=e[i].po;
if size[y]>size[q] then q:=y;
i:=e[i].next;
end;
if q<>n+ then
begin
top[q]:=top[x];
dfs2(q);
end;
i:=p[x];
while i<> do
begin
y:=e[i].po;
if y<>q then
begin
top[y]:=y;
dfs2(y);
end;
i:=e[i].next;
end;
end; procedure sort(l,r:longint);
var i,j,y:longint;
begin
i:=l;
j:=r;
y:=q[(l+r) shr ].y;
repeat
while q[i].y<y do inc(i);
while y<q[j].y do dec(j);
if not(i>j) then
begin
swap(q[i],q[j]);
inc(i);
dec(j);
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end; procedure push(i,l,r:longint);
var m:longint;
begin
m:=(l+r) shr ;
tree[i*]:=tree[i*]+lazy[i]*(m+-l);
tree[i*+]:=tree[i*+]+lazy[i]*(r-m);
inc(lazy[i*],lazy[i]);
inc(lazy[i*+],lazy[i]);
lazy[i]:=;
end; procedure work(i,l,r,x,y:longint);
var m:longint;
begin
if (x<=l) and (y>=r) then
begin
tree[i]:=tree[i]+r-l+;
lazy[i]:=lazy[i]+;
end
else begin
if lazy[i]> then push(i,l,r);
m:=(l+r) shr ;
if x<=m then work(i*,l,m,x,y);
if y>m then work(i*+,m+,r,x,y);
tree[i]:=(tree[i*]+tree[i*+]) mod mo;
end;
end; function getans(i,l,r,x,y:longint):longint;
var m,s:longint;
begin
if (x<=l) and (y>=r) then exit(tree[i])
else begin
if lazy[i]> then push(i,l,r);
m:=(l+r) shr ;
s:=;
if x<=m then s:=s+getans(i*,l,m,x,y);
if y>m then s:=s+getans(i*+,m+,r,x,y);
exit(s);
end;
end; procedure ins(x:longint);
begin
while top[x]<>- do
begin
work(,,n,c[top[x]],c[x]);
x:=fa[top[x]];
end;
work(,,n,,c[x]);
end; function ask(x:longint):longint;
begin
ask:=;
while top[x]<>- do
begin
ask:=ask+getans(,,n,c[top[x]],c[x]);
x:=fa[top[x]];
end;
ask:=(ask+getans(,,n,,c[x])) mod mo;
end; begin
readln(n,m);
for i:= to n- do
begin
read(x);
add(x,i);
end;
dfs1();
top[]:=-;
dfs2();
t:=;
for i:= to m do
begin
readln(l,r,x);
inc(t);
q[t].x:=x; q[t].y:=l-;
q[t].p:=i; q[t].op:=-;
inc(t);
q[t].x:=x; q[t].y:=r;
q[t].p:=i; q[t].op:=;
end;
sort(,t);
j:=;
for i:= to t do
begin
while (j<n) and (j<=q[i].y) do
begin
ins(j);
inc(j);
end;
ans[q[i].p]:=(ans[q[i].p]+q[i].op*ask(q[i].x)+mo) mod mo;
end;
for i:= to m do
writeln(ans[i]);
end.