问题 D: 美好的梦境（二）
题目描述
本题与 美好的梦境（一）的区别将使用【全角中括号】标注。
又是空虚的一天，老师已经不知道这是第几次了。看着眼前作为值日生的 Serika，他始终无法忘记她上一次的遭遇。千千万万不要重蹈上一位的覆辙，老师自思道。Serika 注意到了老师的心思，她决定通过美好的梦境来帮助他重整旗鼓。
老师有 nn 个关于学生的梦境，编号为 1,2,3,⋯,n1,2,3,⋯,n。它们作为节点构成了一棵有根树。编号为 ii（1≤i≤n1≤i≤n）的梦境拥有 kiki 个儿子梦境，编号分别为 pi,1,pi,2,pi,3,⋯,pi,kipi,1,pi,2,pi,3,⋯,pi,ki。
【现在，对于每个编号为 ii（1≤i≤n1≤i≤n）的梦境以及整数 jj（1≤j≤ki1≤j≤ki），记 ai,j=jai,j=j。】
老师认为：
- 编号为 pi,ai,jpi,ai,j（1≤i≤n1≤i≤n，1≤j≤ki1≤j≤ki）的非根梦境的 左梦境 为编号为 pi,ai,max(j−1,1)pi,ai,max(j−1,1) 的梦境，右梦境 为编号为 pi,ai,min(j+1,ki)pi,ai,min(j+1,ki) 的梦境。（根据定义，一个非根梦境的左梦境或右梦境均可以是它本身）
- 编号为 ii（1≤i≤n1≤i≤n）的非叶子梦境的 真儿子梦境 为编号为 pi,ai,1pi,ai,1 的梦境。
为了帮助老师重新品味这些梦境，Serika 从 Koyuki 手里购买了三种 Millennium Science School 监制的梦境转移器，分别记作 ←、→ 和 ↓。通过阅读说明书，老师得知了执行这三种梦境转移器所产生的效果：
- 转移器 ← 的效果是：若当前所处梦境是根梦境，不移动，否则移动至它的左梦境。【老师有 ll 个这样的转移器。】
- 转移器 → 的效果是：若当前所处梦境是根梦境，不移动，否则移动至它的右梦境。【老师有 rr 个这样的转移器。】
- 转移器 ↓ 的效果是：若当前所处梦境是叶子梦境，不移动，否则移动至它的真儿子梦境。【老师有 dd 个这样的转移器。】
【老师现在处于梦境 ss，他想要依照某种顺序执行这些转移器，使得最终移动到的梦境编号最大。老师不喜欢浪费，故 所有转移器都需要被执行，不能有剩余。老师会进行 qq 次模拟，其中每次他会钦定 l,r,dl,r,d 的值，并找来了你帮忙计算对于每一次模拟，通过他的要求最终可以移动到的梦境编号的最大值。出于一些考虑，他只需要你提供与模拟的答案有关的两个值 xor,sumxor,sum。】
输入格式
本题包含多组测试数据。
来自 Serika 的温馨提示：本题输入输出量较大，对于使用 C++ 语言参加竞赛的选手，强烈建议使用关闭同步流的 cin 和 cout 完成输入输出。
首先在第一行输入一个整数 TT（1≤T≤121≤T≤12）表示测试数据组数。
对于每一组测试数据，输入包含 n+q+1n+q+1 行。
第一行包含三个整数 n,q,sn,q,s（1≤n,q≤4×1041≤n,q≤4×104，1≤s≤n1≤s≤n），分别表示梦境的数量，模拟的次数和梦境的起点。
接下来 nn 行，第 i+1i+1（1≤i≤n1≤i≤n）行首先包含一个整数 kiki（0≤ki<n0≤ki<n）表示梦境 ii 的儿子梦境个数。接下来包含 kiki 个整数 pi,1,pi,2,pi,3,⋯,pi,kipi,1,pi,2,pi,3,⋯,pi,ki（1≤pi,1,pi,2,pi,3,⋯,pi,ki≤n1≤pi,1,pi,2,pi,3,⋯,pi,ki≤n），表示梦境 ii 的儿子梦境。
接下来 qq 行，每行包含三个整数 l,r,dl,r,d（0≤l,r,d≤l+r+d≤4.5×1040≤l,r,d≤l+r+d≤4.5×104），分别表示三种转移器的数量。
保证输入的梦境构成一棵有根树。
输出格式
对于每一组测试数据，输出包含一行两个整数 xor,sumxor,sum，表示特殊的输出方式所需要的两个值。
具体地，xor,sumxor,sum 满足以下条件：xor=⊕i=1qansi×ixor=⊕i=1qansi×isum=∑i=1qansi×isum=i=1∑qansi×i其中 ansiansi 是第 ii 次模拟的答案，⊕⊕ 表示二进制按位异或。
输入样例 复制
2
3 3 2
2 3 2
0
0
0 1 0
1 0 1
1 1 1
11 4 4
0
0
0
4 6 5 10 7
1 11
1 1
2 9 8
0
0
2 3 2
0
0 0 2
0 721 3
0 1 1
0 721 1输出样例 复制
13 17
45 81数据范围与提示
以下参考图中，紫色圆圈标记的梦境表示起点梦境，红色箭头表示每次移动（箭头旁的标号表示这次移动对应着第几个被执行的转移器），蓝色四角星标记的梦境表示最终到达的梦境。
这个样例共有两组测试数据。
在第一组测试数据中，梦境共有 33 个，共有 33 次模拟。起点梦境的编号为 22。
-
第 11 次模拟钦定 l=0,r=1,d=0l=0,r=1,d=0。执行 →。答案为 22。
-
第 22 次模拟钦定 l=1,r=0,d=1l=1,r=0,d=1。执行 ←↓。答案为 33。（只列出一种达到最大值的方案）
-
第 33 次模拟钦定 l=1,r=1,d=1l=1,r=1,d=1。执行 →←↓。答案为 33。（只列出一种达到最大值的方案）
在第二组测试数据中，梦境共有 1111 个，共有 44 次模拟。起点梦境的编号为 44。
-
第 11 次模拟钦定 l=0,r=0,d=2l=0,r=0,d=2。执行 ↓↓。答案为 11。
-
第 22 次模拟钦定 l=0,r=721,d=3l=0,r=721,d=3。执行 ↓→↓↓，再执行 720720 个 →。答案为 1111。（只列出一种达到最大值的方案）
-
第 33 次模拟钦定 l=0,r=1,d=1l=0,r=1,d=1。执行 →↓。答案为 66。
-
第 44 次模拟钦定 l=0,r=721,d=1l=0,r=721,d=1。执行 719719 个 →，再执行 ↓→→。答案为 1010。
