题目背景

翻译自 ROI 2023 D2T4。

这是一道 IO 交互题。

某个国家准备制定汽车的生产计划。

该国总共有 $n$ 个城市，每个城市中有一个工厂，它们要参与汽车的生产。第 $i$ 个城市的工厂可以雇佣 $l_i$ 到 $r_i$ 个人。

一些城市之间通过双向道路相连，且道路网络呈树状结构。因此，如果要从一个城市到另一个城市，在不重复经过同一个城市的情况下，只有一种路径。

生产计划被定义为一个整数序列 $[a_1, a_2, \dots , a_n]$，其中 $a_i$ 表示在第 $i$ 个工厂工作的人数，满足 $l_i\le a_i\le r_i$。在制定生产计划后，一些工厂将被选为装配工厂，这些工厂负责装配汽车，而其它工厂则负责生产零部件。如果没有两个装配工厂所在的城市被一条道路直接连接，那么这个生产计划就是合理的。在所有可能的合理的计划中，会选择装配工厂的工人总数最大的一个计划。这个数就被称为计划 $[a_1, a_2, \dots , a_n]$ 的效率。

题目描述

你需要确定是否存在效率为 $v_i$ 的计划。如果存在这样的计划，则可能需要输出这样一个计划。

制定计划的过程包括两个阶段。

在第一阶段，你将获得 $v_1,v_2,\dots,v_q$ 的值。你需要确定是否存在效率为 $v_i$ 的计划，如果不存在，输出 -1；如果存在，输出一个非负整数 $k_i$。

对 $k$ 的定义如下：给定三个整数 $x,y,m$，定义计划 $[a_1, a_2, \dots , a_n]$ 的 $k = \bigoplus\limits^n_{j=1} ( (x\times j + y\times a_j^2) \bmod m )$，其中 $\oplus$ 为按位异或。

因为符合要求的计划可能不止一个，所以 $k_i$ 也有很多种可能，你需要输出其中一种可能的 $k_i$。

在第二阶段，某些计划的可行性将被检查。在每个查询中，你的程序会得到一个整数 $i$（$1\le i\le q$）。对于这个查询，如果不能制定效率为 $v_i$ 的计划，你需要输出 -1；否则，你需要输出 $n$ 个整数 $a_1,a_2,\dots,a_n$（$l_i\le a_i\le r_i$），表示一个制定的计划。这个计划计算出来的 $k$ 值应该等于你先前输出的 $k_i$，效率应该等于 $v_i$。

在程序输出每个 $k$ 之前，无法知道哪些计划会被检查。因此，你需要保证在第一阶段中输出的 $k_i$ 是正确的。

输入格式

本题多测，第一行输入一个整数 $t$（$1\le t\le10^4$），表示数据组数。

在每组数据中：

第一行包含两个整数 $n,q$（$2 \le n \le 2 \times 10^5$，$1 \le q \le 2 \times 10^5$），分别表示城市的数量和要制定的计划的数量。

第二行包含三个整数 $x,y,m$（$11 \le m \le 2^{30}$，$0 \le x,y < m$），即计算 $k$ 的参数。

接下来的 $n-1$ 行描述了城市之间的道路网络。在这 $n-1$ 行中，第 $i$ 行包含两个整数 $s_i,f_i$（$1 \le s_i,f_i \le n$，$s_i \ne f_i$），表示第 $i$ 条道路连接城市 $s_i$ 和 $f_i$ 的双向道路。保证这些道路能够构成一棵树。

接下来的 $n$ 行中的第 $i$ 行包含两个整数 $l_i,r_i$（$0 \le l_i \le r_i \le 10^9$），表示第 $i$ 个城市的工人数量限制。

接下来的一行包含 $q$ 个整数 $v_1,v_2,\dots,v_q$（$0 \le v_i \le \sum\limits^n_{i=1}r_i$），表示需要制定的计划的效率值。保证所有的 $v_i$ 都是不同的。

接下来，你需要输出第一部分中你需要输出的内容（具体方式见“输出格式”）。输出完成后，才可以读入第二部分的数据。

接下来若干行，每行输入一个数 $i$（$0\le i\le q$）。当 $i\ne0$ 时，$i$ 表示要检查的计划的编号。在按照输出格式的要求输出后，交互库才会继续给你下一个 $i$。当 $i=0$ 时，表示第二部分的检查结束，即这一组数据输入完成。如果这不是最后一组数据，你的程序应该立即开始读入下一组数据。

保证 $\sum n,\sum q\le2\times10^5$，且每组数据中检查计划次数 $c$ 的总和不超过 $10^4$，$\sum n\times c\le10^6$。

输出格式

读取完每组输入的第一部分后，需要输出 $q$ 个整数 $k_1,k_2,\dots,k_q$（$-1 \le k_i < 2^{30}$），如果 $k_i = -1$ 则表示无法制定效率值为 $v_i$ 的计划。输出后，交互库才会给你第二部分的数据。

在读入第二部分检查的计划编号 $i$（且 $i\ne0$）后，如果第 $i$ 个计划无法制定，即 $k_i=-1$ 时，则输出 -1。否则，需要输出 $n$ 个整数 $a_1,a_2,\dots,a_n$（$l_i \le a_i \le r_i$），表示所制定的计划。该计划的 $k$ 应等于 $k_i$，并且效率应等于 $v_i$。

IO 交互题在输出后应刷新缓冲区。

如果在 C++ 中使用了 cout << ... << endl，在 Java 中使用了 System.out.println，在 Python 中使用了 print，在 Pascal 中使用了 writeln，那么输出缓冲区会自动刷新，不需要额外操作。

如果使用了其他输出方法，建议手动刷新输出缓冲区。在刷新输出缓冲区时，可以使用 C 和 C++ 中的 fflush(stdout)，Pascal 中的 flush(output)，Java 中的 System.out.flush()，Python 中的 sys.stdout.flush()。

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

提示

在样例中，程序与交互库的交互用空行分隔。这样做是为了便于理解，清楚地知道哪个消息是对哪个消息的回应。在实际测试中，不会有多余的空行（当然，会有换行）。

第一个样例只有一种制定计划的方法，即 $a = [4, 2, 5, 3, 2, 6, 3, 4, 3]$。它的效率为 $19$，计算出来的 $k$ 为 $10$。

第二个样例有三组数据。

• 在第一组数据中：
  • 存在唯一一个效率为 $0$ 的计划，$a = [0, 0, 0]$。该计划的 $k$ 为 $12$。
  • 存在效率为 $1$ 的计划，例如 $a = [1, 0, 0]$。该计划的 $k$ 为 $8$。
  • 存在效率为 $2$ 的计划，例如 $a = [1, 0, 1]$。该计划的 $k$ 为 $3$。
  • 不存在效率为 $3$ 的计划。
  • 在这四个请求的计划中，检查了计划编号 $i = 2$（$v_2 = 1$）。
• 在第二组数据中：
  • 不存在效率为 $0$ 的计划。
  • 不存在效率为 $1$ 的计划。
  • 存在效率为 $2$ 的计划，例如 $a = [1, 1, 1, 1]$。该计划的 $k$ 为 $4$。
  • 存在效率为 $3$ 的计划，例如 $a = [2, 1, 1, 1]$。该计划的 $k$ 为 $14$。
  • 存在唯一的效率为 $4$ 的计划 $a = [2, 1, 1, 2]$。该计划的 $k$ 为 $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]$。

子任务	分值	$n,\sum n$	$\sum q$	其它特殊性质
$1$	$11$			$l_i=r_i$
$2$	$9$			$c=0$
$3$	$12$			$l_i=0,r_i\le1$
$4$				$l_i=0$
$5$	$8$			$s_i=1,f_i=i+1$
$6$	$5$	$n\le10,\sum n\le1000$	$Q\le1000$	$c=q,r_i\le10,r_i-l_i\le2$
$7$	$2$			$c=q,r_i\le10$
$8$	$13$	$\sum n\le1000$		$c=q,\sum\limits^{n}_{i=1}r_i-l_i\le10^4$
$9$	$11$			$c=q$
$10$	$6$
$11$	$5$	$\sum n\le1000$
$12$		$\sum n\le8000$
$13$	$9$

保证 $\sum n,\sum q\le2\times10^5$，且每组数据中检查计划次数 $c$ 的总和不超过 $10^4$，$\sum n\times c\le10^6$。