题目描述

译自 ROI 2023 Day2 T4. Выполнить план, но не перевыполнить

你需要为某个国家制定汽车和零件的生产计划。这个国家有 $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

输入

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

第一个样例符合子任务 1 的限制。

在第一组测试数据中，只有一种制定计划的方法，即 $a=[4,2,5,3,2,6,3,4,3]$。它的效率等于 $19$，它的证书等于 $10$。

样例 2

输入

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$ 的计划，即 $a=[0,0,0]$。它的证书等于 $12$。 有一些效率为 $1$ 的计划，例如 $a=[1,0,0]$。它的证书等于 $8$。 有一些效率为 $2$ 的计划，例如 $a=[1,0,1]$。它的证书等于 $3$。 不存在效率为 $3$ 的计划。 在四个请求的计划中，检验了编号为 $i=2\ (v_{2}=1)$ 的计划。

在第二个测试数据中：

不存在效率为 $0$ 的计划。 不存在效率为 $1$ 的计划。 有一些效率为 $2$ 的计划，例如 $a=[1,1,1,1]$。它的证书等于 $4$。 有一些效率为 $3$ 的计划，例如 $a=[2,1,1,1]$。它的证书等于 $14$。 只有一种效率为 $4$ 的计划，即 $a=[2,1,1,2]$。它的证书等于 $9$。 不存在效率为 $5$ 的计划。 在六个请求的计划中，检验了编号为 $i=5\ (v_{5}=4), i=2\ (v_{2}=1), i=3\ (v_{3}=2)$ 的计划。

在第三个测试数据中，制定了以下计划（从第二个开始，因为不存在效率为 $v_{1}=13$ 的计划：$[2,5,4,4,6] ;[2,5,4,1,6] ;[2,4,4,4,4] ;[2,4,4,3,4]; [2,4,4,2,4] ;[1,1,0,1,4]$。

数据范围与提示

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

子任务编号	分值	$n, N$ 的限制	$Q$ 的限制	附加限制	子任务依赖
1	11	-		$l_{i}=r_{i}$	-
2	9			$c=0$
3	12			$l_{i}=0, r_{i} \leq 1$
4				$l_{i}=0$	3
5	8			$s_{i}=1, f_{i} = i + 1$	-
6	5	$n \leq 10, N \leq 1000$	$Q \leq 1000$	$c=q, r_{i} \leq 10, r_{i}-l_{i} \leq 2$
7	2	-	-	$c=q, r_{i} \leq 10$	6
8	13	$N \leq 1000$		$c=q,\sum\limits_{i=1}^{n} r_{i} - l_{i} \leq 10^4$	6~7
9	11	-		$c=q$	6~8
10	6			-	6~9
11	5	$N \leq 1000$			0, 6~9
12		$N \leq 8000$			0, 6~9, 11
13	9	-			0, 1~12