问题 B: Mon2tr

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

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

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

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

对于第 $i$（$1\le i\le q$）次询问，求满足 j−vj≤yi≤j≤j+vj≤zij−vj≤yi≤j≤j+vj≤zi 的整数 $j$（$1\le j\le n$）中，j+vjj+vj 的最大值。如果 yi>ziyi>zi 或者不存在符合条件的整数，答案为 $0$。

本题包含多组测试数据。

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

https://www.luogu.me/paste/y4lm88ha

首先在第一行输入一个整数 $T$（1≤T≤3.5×1051≤T≤3.5×105）表示测试数据组数。

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

第一行包含两个整数 $n,q$（1≤n≤8×104,1≤q≤1051≤n≤8×104,1≤q≤105，1≤∑n≤3.5×105,1≤∑q≤5×1051≤∑n≤3.5×105,1≤∑q≤5×105），分别表示树上点的数量和询问的次数。

第二行包含 $n$ 个整数 fa1,fa2,fa3,⋯,fanfa1,fa2,fa3,⋯,fan（0≤fa1,fa2,fa3,⋯,fan≤n0≤fa1,fa2,fa3,⋯,fan≤n）表示每个点的父亲编号。若 fai=0fai=0（$1\le i\le n$）则表示编号为 $i$ 的点为树根。

接下来 $q$ 行，第 $i+2$（$1\le i\le q$）行包含三个整数 xi′,yi′,zi′xi′,yi′,zi′（0≤xi′,yi′,zi′<1090≤xi′,yi′,zi′<109），表示与第 $i$ 次询问的参数有关的三个数。

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

1. 记 $lans$ 表示第 $i-1$ 次询问的答案。若 $i=1$，则令 $lans=0$。
2. xi=[(xi′+lans)modn]+1xi=[(xi′+lans)modn]+1，yi=[(yi′+lans)mod(2n−1)]−(n−1)yi=[(yi′+lans)mod(2n−1)]−(n−1)，zi=[(zi′+lans)mod(2n−1)]+1zi=[(zi′+lans)mod(2n−1)]+1，其中 $\mathrm{mod}$ 表示取模，例如 $3\mathrm{mod}2=1,(-7)\mathrm{mod}3=2$。

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

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

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