题目描述

对于两个权值序列 $A(0)_0,A(0)_1,\dots,A(0)_{20}$ 与 $A(1)_0,A(1)_1,\dots,A(1)_{20}$，记 $x=\sum_{i=0}^{20} b_i2^{i}$，其中 $b_i\in \{0,1\}$，定义 $f(x)=\prod_{i=0}^{20} A(b_i)_i$。

给定一颗树。有 $T$ 组数据，每组数据给定树的根结点编号 $r_i$，模数 $m$ 与权值序列 $A(0),A(1)$，你需要对每组数据都求出答案。

对于一颗根为 $r_i$ 的有根树，每个结点 $x$ 的深度 $d_x$ 定义为 $x$ 到 $r_i$ 的简单路径上的结点数量。记 $\operatorname{LCA*}(x,y)$ 为结点 $x,y$ 最近公共祖先的编号。对于每个树上的结点 $x$，你需要求出 $s_x=\sum_{i=1}^n f(i+d_{\operatorname{LCA*}(i,x)})$ 对 $m$ 取模后的结果。

输入格式

本题包含多组测试数据。

输入的第一行包含一个整数 $n$。

接下来 $n-1$ 行，每行两个整数 $u_i,v_i$ 表示树上一条连接结点 $u_i$ 与 $v_i$ 的边。

接下来一行一个整数 $T$，表示数据的组数。

接下来共 $3T$ 行。对于每组数据输入三行：

• 第一行包含两个整数 $r_i,m$。
• 第二行包含 $21$ 个整数 $A(0)_0,A(0)_1,\dots,A(0)_{20}$。
• 第三行包含 $21$ 个整数 $A(1)_0,A(1)_1,\dots,A(1)_{20}$。

输出格式

共输出 $T$ 行。对于每组数据，记 $s_x$ 表示结点 $x$ 的答案，你只需要输出一行包含一个整数，表示 $(1\times s_1) \oplus (2\times s_2) \oplus \dots \oplus (n\times s_n)$ 的结果。

5
1 2
1 3
2 4
2 5
3
1 100
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 100
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
4 998244353
3 8 6 9 8 1 3 9 6 3 6 9 5 4 5 3 1 6 1 2 3
8 7 6 6 8 5 1 8 9 2 6 8 7 3 4 7 5 7 9 9 2

13
47
101841048

提示

【样例 1 解释】

对于第一组数据，所有点的答案都是 $5$。于是 $(1\times s_1) \oplus (2\times s_2) \oplus \dots \oplus (n\times s_n)=(1\times 5) \oplus (2\times 5) \oplus (3\times 5) \oplus (4\times 5) \oplus (5\times 5)=13$。

对于第二组数据，$(s_1,s_2,s_3,s_4,s_5)=(9,7,8,6,8)$。

【样例 2】

见附件的 tree/tree2.in 与 tree/tree2.ans。

该样例满足测试点 $1\sim 2$ 的约束条件。

【样例 3】

见附件的 tree/tree3.in 与 tree/tree3.ans。

该样例满足测试点 $6$ 的约束条件。

【样例 4】

见附件的 tree/tree4.in 与 tree/tree4.ans。

该样例满足测试点 $7\sim 10$ 的约束条件。

【样例 5】

见附件的 tree/tree5.in 与 tree/tree5.ans。

该样例满足测试点 $17\sim 20$ 的约束条件。

【数据范围】

对于所有测试数据，保证 $1\le T\le 10$，$1\le r_i\le n\le 2\times 10^5$，$0\le A(0)_i,A(1)_i<m$，$2\le m\le 10^9$。

::cute-table{tuack}

测试点编号	$T=$	$n\le$	$m\le$	特殊性质
$1\sim 2$	$5$	$100$	$10^9$	无
$3\sim 4$	$10$	$2000$	^	^
$5$	^	$2\times 10^5$	$2$
$6$		^	$10^9$	AB
$7\sim 10$			^	B
$11$				C
$12\sim 13$	$2$	$10^5$		D
$14\sim 16$	^			无
$17\sim 20$	$10$	$2\times 10^5$		^

• 特殊性质 A：保证对于 $\forall 1\le i<n,u_i=i,v_i=i+1$。
• 特殊性质 B：保证存在一个 $1,2,\dots,n$ 的排列 $p_1,p_2,\dots,p_n$ 满足 $\forall 1\le i<n,u_i=p_i,v_i=p_{i+1}$。
• 特殊性质 C：保证存在一个整数 $0\le x<m$ 满足 $\forall 0\le i\le 20,A(0)_i=1,A(1)_i=x^{2^i}\bmod m$。
• 特殊性质 D：保证对于 $\forall 1\le i\le n,d_i\le 20$。