题目描述

你需要为某个国家制定汽车和零件的生产计划。这个国家有 $n$ 个城市，每个城市都有一个参与生产的工厂。在第 $i$ 个城市的工厂，可以安排 $l_{i}$ 到 $r_{i}$ 个人工作。一些城市之间有双向的道路相连，而且道路网络的形状是一棵树：从任何一个城市出发，不会经过同一个城市两次的情况下，只有一种方法可以到达另一个城市。

我们把一个整数序列 $\left[a_{1}, a_{2}, \ldots, a_{n}\right]$ 称为一个生产计划，其中 $a_{i}\ (l_{i} \leq a_{i} \leq r_{i})$ 表示在第 $i$ 个工厂工作的人数。在制定了生产计划后，一些工厂会被选为装配厂，它们会生产汽车，而其他的工厂会生产零件。一个选择被认为是合理的，当且仅当没有两个装配厂直接通过一条道路相连。在所有可能的合理选择中，我们会选择那个装配厂的工人总数最大的一个。这个数被称为计划 $\left[a_{1}, a_{2}, \ldots, a_{n}\right]$ 的效率。

在这个题目中，对于一些给定的值 $v_{1}, v_{2}, \ldots, v_{q}$，对于每个 $i$ 你需要找出是否存在一个效率为 $v_{i}$ 的计划。如果存在这样的计划，你可能需要给出一个这样的计划。

我们已经确定了一些整数参数 $x, y, m$。考虑一个计划 $\left[a_{1}, a_{2}, \ldots, a_{n}\right]$。我们令 $k=\bigoplus_{j=1}^{n}\left(\left(x \cdot j+y \cdot a_{j}^{2}\right) \bmod m\right)$ 为这个计划的证书，其中 $\bigoplus$ 是「按位异或」运算。

制定计划的过程分为两个阶段：

• 在第一个阶段，你会得到 $q$ 个整数 $v_{1}, v_{2}, \ldots, v_{q}$。对于每一个 $i\ (1\leq i \leq q)$，你需要判断是否存在一个效率为 $v_{i}$ 的计划，如果存在则输出一个非负整数 $k_{i}$，否则输出 $-1$。
• 在第二个阶段，你会收到 $c$ 个检验请求 $i$。如果不存在效率为 $v_{i}$ 的计划，你需要输出 $-1$，否则你需要给出一个计划 $\left[a_{1}, a_{2}, \ldots, a_{n}\right]$，它的证书等于 $k_{i}$，效率等于 $v_{i}$。

提供计划的证书和后续的检验都是以交互题的形式进行的。在你提供证书之前，你不会知道哪些计划会被检验。所以在那些 $c>0$ 的子任务中，你需要在第一个阶段就准备好检验。对于那些存在相应计划的效率值 $v_{i}$，输出你在第二个阶段能够给出一个证书与之相对应的计划的 $k_{i}$。

交互方式

这是一道交互题。你的程序将使用标准输入输出与交互器进行交互。输入包含多组数据。

首先，你的程序应该读取一个整数 $t\ (1 \leq t \leq 10^{4})$，表示测试数据的数量。

对于每组测试数据，你的程序应该先读取以下格式的数据。

第一行包含两个整数 $n, q\ (2 \leq n \leq 2 \cdot 10^{5}, 1 \leq q \leq 2 \cdot 10^{5})$，分别表示城市的数量和需要制定的计划的数量。

第二行包含三个整数 $x, y, m\ (11 \leq m \leq 2^{30}, 0 \leq x, y<m)$，表示计算计划的证书的参数。

接下来的 $n-1$ 行描述了城市之间的道路网络树。第 $i$ 行包含两个整数 $s_{i}, f_{i}\ (1 \leq s_{i}, f_{i} \leq n , s_{i} \neq f_{i})$，表示城市 $s_{i}$ 和 $f_{i}$ 之间存在一条双向道路。保证这些道路构成了一棵树。

接下来的 $n$ 行中的第 $i$ 行包含两个整数 $l_{i}, r_{i}\ (0 \leq l_{i} \leq r_{i} \leq 10^{9})$，表示第 $i$ 个城市的工人数量的限制。

接下来的一行包含 $q$ 个整数 $v_{1}, v_{2}, \ldots, v_{q}\ (0 \leq v_{i} \leq \sum_{i=1}^{n} r_{i})$，表示需要制定的计划的效率值。保证所有的 $v_{i}$ 都不相同。

在你读取了以上数据后，你应该输出 $q$ 个整数 $k_{1}, k_{2}, \ldots, k_{q}\ (-1 \leq k_{i}<2^{30})$，如果无法制定一个效率为 $v_{i}$ 的计划 $k_{i}=-1$，否则 $0 \leq k_{i}<2^{30}$。

接下来可能会对一些制定的计划进行检验。检验是以交互的方式进行的，具体如下：

交互器会输出一行一个整数 $i\ (1 \leq i \leq q)$，表示要检验的计划的编号。保证所有请求检验的计划的编号都不相同。如果 $i$ 号计划无法实现，你需要输出 $-1$。在这种情况下，你之前应该输出过 $k_{i}=-1$。否则，你需要输出 $n$ 个整数 $a_{1}, a_{2}, \ldots, a_{n}\ (l_{i} \leq a_{i} \leq r_{i})$，表示制定的计划。这个计划的证书应该等于 $k_{i}$，效率应该等于 $v_{i}$。在 $c \geq 0$ 次检验之后，交互器输出一个数 $i=0$，表示这组测试数据已经结束。

令 $t$ 组测试数据中的 $n,q$ 之和分别为 $N,Q$。保证 $N, Q \leq 2 \cdot 10^{5}$。$t$ 组测试数据中 $c$ 的值的和不超过 $10^{4}$，$n \cdot c$ 的值的和不超过 $10^{6}$。

由于这是一道交互题，在你的程序每次输出一行之后，你需要输出一个换行符并刷新输出缓冲区。

注意： 在样例中，参赛者的程序和交互器的信息用空行分隔。这样做是为了方便理解，让人知道哪个信息是对哪个信息的回应。在真实的交互中，测试系统中不会有空行。

1
9 3
4 7 15
1 2
2 4
2 5
1 3
3 6
3 7
6 8
6 9
4 4
2 2
5 5
3 3
2 2
6 6
3 3
4 4
3 3
18 19 20

1

2

3

0

-1 10 -1

-1

4 2 5 3 2 6 3 4 3

-1

3
3 4
3 4 11
1 2
2 3
0 1
0 1
0 1
0 1 2 3

2

0
4 6
1 2 11
1 2
2 3
3 4
0 2
1 1
1 1
1 2
0 1 2 3 4 5

5

2

3

0
5 7
11 31 101
1 2
2 3
2 4
3 5
1 2
1 5
0 4
1 4
4 6
13 12 11 10 9 8 6

3

5

7

0

12 8 3 -1

1 0 0











-1 -1 4 14 9 -1

2 1 1 2

-1

1 1 1 1













-1 127 23 58 13 90 91

2 5 4 1 6

2 4 4 3 4

1 1 0 1 4

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。