P11111 [ROI 2023] 生产计划 (Day 2)

翻译自 [ROI 2023 D2T4](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-roi-2023-day2.pdf)。 **这是一道 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

在样例中，程序与交互库的交互用空行分隔。这样做是为了便于理解，清楚地知道哪个消息是对哪个消息的回应。在实际测试中，不会有多余的空行（当然，会有换行）。 第一个样例只有一种制定计划的方法，即 $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$ | $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$ | $n\le10,\sum n\le1000$ | $Q\le1000$ | $c=q,r_i\le10$ | | $8$ | $13$ | $\sum n\le1000$ | $Q\le1000$ | $c=q,\sum\limits^{n}_{i=1}r_i-l_i\le10^4$ | | $9$ | $11$ | $\sum n\le1000$ | $Q\le1000$ | $c=q$ | | $10$ | $6$ | | | $c=q$ | | $11$ | $5$ | $\sum n\le1000$ | | | | $12$ | $5$ | $\sum n\le8000$ | | | | $13$ | $9$ | | | | 保证 $\sum n,\sum q\le2\times10^5$，且每组数据中检查计划次数 $c$ 的总和不超过 $10^4$，$\sum n\times c\le10^6$。