请注意本题特殊的空间限制。

“生命野蛮蓬勃，大地千变万化。人造机器轰鸣运作，源石能的光辉照亮了暗影。人们挣扎在暗处，向往光明，在辉煌时轻视阴影，如是反复。”

给定一棵由编号为 $1,2,3,\cdots,n$ 的点构成的有根树。记 $d_i$ 表示编号为 $i$（$1\le i\le n$）的点到树根的唯一简单路径上的 点数（对于树根本身，这个值为 $1$）。

现在有 $q$ 次询问。第 $i$（$1\le i\le q$）次询问给定整数 $x_i,y_i,z_i$。对于整数 $j$（$1\le j\le n$），定义 $v_j=d_{\text{LCA}(j,x_i)}$，其中 $\text{LCA}(u,v)$ 表示编号分别为 $u,v$ 的点的最近公共祖先的编号。

对于第 $i$（$1\le i\le q$）次询问，求满足 $j-v_j\le y_i\le j\le j+v_j\le z_i$ 的整数 $j$（$1\le j\le n$）中，$j+v_j$ 的最大值。如果 $y_i>z_i$ 或者不存在符合条件的整数，答案为 $0$。

本题包含多组测试数据。

提示：本题输入输出量较大，请使用合适的输入输出方式。可以使用下面给出的输入输出模板。同时请选手注意代码的时间和空间常数消耗，常数过大，例如滥用 C++ STL 容器的代码不保证能够通过。

char buf[1<<22],*p1,*p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin),p1==p2)?EOF:*p1++)
inline int read(){
    int x=0;char ch=0;
    while((ch<'0'||ch>'9'))ch=getchar();
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch-'0'),ch=getchar();
    return x;
}
inline void write(int x,char tl=0){
    static int sta[10];
    int top=0;
    do{sta[top++]=x%10,x/=10;}while(x);
    while(top)putchar(sta[--top]+48);
    if(tl)putchar(tl);
}

首先在第一行输入一个整数 $T$（$1\le T\le3.5\times10^5$）表示测试数据组数。

对于每一组测试数据，输入包含 $q+2$ 行。

第一行包含两个整数 $n,q$（$1\le n\le 8\times10^4,1\le q\le 10^5$，$1\le\sum n\le3.5\times10^5,1\le \sum q\le 5\times 10^5$），分别表示树上点的数量和询问的次数。

第二行包含 $n$ 个整数 $fa_1,fa_2,fa_3,\cdots,fa_n$（$0\le fa_1,fa_2,fa_3,\cdots,fa_n\le n$）表示每个点的父亲编号。若 $fa_i=0$（$1\le i\le n$）则表示编号为 $i$ 的点为树根。

接下来 $q$ 行，第 $i+2$（$1\le i\le q$）行包含三个整数 $x'_i,y'_i,z'_i$（$0\le x'_i,y'_i,z'_i<10^9$），表示与第 $i$ 次询问的参数有关的三个数。

对于第 $i$（$1\le i\le q$）次询问，你需要通过以下操作得到 $x_i,y_i,z_i$：

1. 记 $lans$ 表示第 $i-1$ 次询问的答案。若 $i=1$，则令 $lans=0$。
2. $x_i=[(x'_i+lans)\bmod n]+1$，$y_i=[(y'_i+lans)\bmod(2n-1)]-(n-1)$，$z_i=[(z'_i+lans)\bmod(2n-1)]+1$，其中 $\bmod$ 表示取模，例如 $3\bmod 2=1,(-7)\bmod 3=2$。

保证输入的是一棵有根树。

对于每一组测试数据，输出包含 $q$ 行。

第 $i$（$1\le i\le q$）行包含一个整数表示第 $i$ 次询问的答案。

在样例的第一组测试数据中，树的结构如下图所示。

这组测试数据共有 $5$ 次询问。

在第 $1$ 次询问中，$x_1=4,y_1=-1,z_1=8$。

1. 若 $j=1$，则 $j-v_j=-1,j+v_j=3$，满足 $j-v_j\le y_1\le j\le j+v_j\le z_1$。
2. 若 $j=2$，则 $j-v_j=0,j+v_j=4$，不满足题意。
3. 若 $j=3$，则 $j-v_j=1,j+v_j=5$，不满足题意。
4. 若 $j=4$，则 $j-v_j=2,j+v_j=6$，不满足题意。
5. 若 $j=5$，则 $j-v_j=4,j+v_j=6$，不满足题意。

因此，答案为 $3$。

1. 在第 $2$ 次询问中，$x_2=2,y_2=2,z_2=7$。取 $j=2/3/4$，答案为 $6$。
2. 在第 $3$ 次询问中，$x_3=5,y_3=-3,z_3=4$。答案为 $0$。
3. 在第 $4$ 次询问中，$x_4=5,y_4=-3,z_4=9$。答案为 $0$。
4. 在第 $5$ 次询问中，$x_5=5,y_5=1,z_5=4$。取 $j=2$，答案为 $3$。

在样例的第五组测试数据中，树的结构如下图所示。

这组测试数据共有 $15$ 次询问。

1. 在第 $1$ 次询问中，$x_1=3,y_1=-3,z_1=20$。答案为 $0$。
2. 在第 $2$ 次询问中，$x_2=4,y_2=-13,z_2=9$。答案为 $0$。
3. 在第 $3$ 次询问中，$x_3=12,y_3=2,z_3=14$。取 $j=3$，答案为 $4$。
4. 在第 $4$ 次询问中，$x_4=6,y_4=-14,z_4=14$。答案为 $0$。
5. 在第 $5$ 次询问中，$x_5=9,y_5=1,z_5=4$。取 $j=2$，答案为 $3$。
6. 在第 $6$ 次询问中，$x_6=8,y_6=11,z_6=19$。取 $j=12$，答案为 $13$。
7. 在第 $7$ 次询问中，$x_7=4,y_7=3,z_7=12$。取 $j=5$，答案为 $7$。
8. 在第 $8$ 次询问中，$x_8=14,y_8=2,z_8=22$。取 $j=5$，答案为 $8$。
9. 在第 $9$ 次询问中，$x_9=2,y_9=11,z_9=6$。答案为 $0$。
10. 在第 $10$ 次询问中，$x_{10}=8,y_{10}=13,z_{10}=26$。取 $j=15$，答案为 $17$。
11. 在第 $11$ 次询问中，$x_{11}=1,y_{11}=-8,z_{11}=23$。答案为 $0$。
12. 在第 $12$ 次询问中，$x_{12}=8,y_{12}=2,z_{12}=9$。取 $j=3$，答案为 $4$。
13. 在第 $13$ 次询问中，$x_{13}=6,y_{13}=11,z_{13}=7$。答案为 $0$。
14. 在第 $14$ 次询问中，$x_{14}=7,y_{14}=4,z_{14}=2$。答案为 $0$。
15. 在第 $15$ 次询问中，$x_{15}=7,y_{15}=-5,z_{15}=16$。答案为 $0$。