这是一个交互式问题。

你需要为某个国家的汽车和零部件生产制定生产计划。该国共有 $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_1, v_2, \dots, v_q$，你需要判断是否存在效率为 $v_i$ 的计划。如果存在，你可能需要提供该计划。

固定整数参数 $x, y$ 和 $m$。考虑计划 $[a_1, a_2, \dots, a_n]$。该计划的证书定义为数字 $k = \bigoplus_{j=1}^{n} ((x \cdot j + y \cdot a_j^2) \pmod m)$，其中 $\bigoplus$ 是按位异或运算。

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

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

在第二阶段，部分计划将被验证：你将收到 $c$ 次查询，每次给出一个整数 $i$ ($1 \le i \le q$)。对于该查询，如果效率为 $v_i$ 的计划不存在，则输出 $-1$；否则，提供一个计划 $[a_1, a_2, \dots, a_n]$，其证书等于 $k_i$，且效率等于 $v_i$。

输入格式

首先，你的程序必须读取一个整数 $t$ ($1 \le t \le 10^4$)，表示测试用例的数量。然后执行 $t$ 次交互。

对于每个测试用例： 第一行包含两个整数 $n, q$ ($2 \le n \le 2 \cdot 10^5, 1 \le q \le 2 \cdot 10^5$)，分别表示城市数量和需要制定的计划数量。 第二行包含三个整数 $x, y, m$ ($11 \le m \le 2^{30}; 0 \le x, y < m$)，用于计算计划证书的参数。 接下来的 $n-1$ 行描述了城市间的道路网络。第 $i$ 行包含两个整数 $s_i, f_i$ ($1 \le s_i, f_i \le n; s_i \neq f_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_{i=1}^n r_i$)，表示需要制定的计划效率。保证所有 $v_i$ 互不相同。

输出格式

读取输入后，你必须输出 $q$ 个整数 $k_1, k_2, \dots, k_q$ ($-1 \le k_i < 2^{30}$)，其中如果无法制定效率为 $v_i$ 的计划，则 $k_i = -1$，否则 $0 \le k_i < 2^{30}$。

之后，可能会对部分计划进行验证。 验证过程如下：评测程序输出一行，包含一个整数 $i$ ($1 \le i \le q$)，表示要验证的计划编号。保证所有请求的计划编号各不相同。 作为回应，如果无法制定第 $i$ 个计划，输出 $-1$（此时之前必须已输出 $k_i = -1$）。否则，输出 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($l_i \le a_i \le r_i$)，表示制定的计划。该计划的证书必须等于 $k_i$，效率必须等于 $v_i$。

在 $c \ge 0$ 次验证后，评测程序将向你的程序输入 $i = 0$，表示该测试用例结束，你的程序应开始处理下一个测试用例或终止。

说明

由于这是一个交互式问题，在输出每一行后，请务必输出换行符并刷新输出缓冲区。

样例

输入 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

-1 10 -1
-1
4 2 5 3 2 6 3 4 3
-1