【题目描述】

给定两棵有 $n$ 个结点的树 $T_1, T_2$，其中编号为 $i$ 的点在 $T_1, T_2$ 上的权值分别为 $val_{1,i}, val_{2,i}$。给出 $l_2, r_2$，有 $q$ 次询问，每次询问给出 $l_1, r_1$，求

$$ \sum\limits_{1\leq x < y \leq n} [l_1 \leq val_{1,\operatorname{LCA_1}(x,y)} \leq r1 ] [l_2 \leq val_{2,\operatorname{LCA_2}(x,y)} \leq r2 ] val_{1,\operatorname{LCA_1}(x,y)} \times val_{2,\operatorname{LCA_2}(x,y)} $$

其中，$\operatorname{LCA_1}(x,y)$ 表示在 $T_1$ 上 $(x,y)$ 的最近公共祖先，$\operatorname{LCA_2}(x,y)$ 表示在 $T_2$ 上 $(x,y)$ 的最近公共祖先。

答案对 $2^{64}$ 取模。

【输入格式】

从文件 d.in 中读入数据。

本题有多组数据。

第一行输入两个整数 $sid$，$T$ 表示测试点编号和数据组数。样例的 $sid=0$。

对于每组数据：

第一行输入四个数 $n,q,l_2,r_2$。

第二行输入 $n-1$ 个数表示第一棵树的 $fa_{2\cdots n}$，第三行输入 $n$ 个数表示第一棵树的 $val_{1\cdots n}$。

第四行输入 $n-1$ 个数表示第二棵树的 $fa_{2\cdots n}$，第五行输入 $n$ 个数表示第二棵树的 $val_{1\cdots n}$。

接下来 $q$ 行，每行输入两个数 $l_1,r_1$。

【输出格式】

输出到文件 d.out 中。

为减小输出量，对于每组数据，请先输出前 $\min(q,10^4)$ 个询问的答案，每个答案一行。最后再用一行输出所有询问的异或和。

【数据范围与提示】

对于所有测试点：$1\le n,q\le 2\times 10^5$，$1\le val_{1,i},val_{2,i}\le 10^9$，$1\le l_1\le r_1\le 10^9$，$1\le l_2\le r_2\le 10^9$。

除最后一个测试点外，$\sum n,\sum q$ 均不超过该测试点 $n,q$ 最大值的三倍。

对于最后一个测试点，$\sum n,\sum q$ 均不超过该测试点 $n,q$ 最大值的六倍。

每个测试点的具体限制见下表：