This is an interactive problem.

You are required to develop production plans for automobiles and spare parts in a certain country. There are $n$ cities in the country, each containing a factory involved in production. In the $i$-th city, the factory can employ between $l_i$ and $r_i$ workers, inclusive.

Some cities are connected by two-way roads, and the road network forms a tree: there is a unique path between any two cities that does not visit any city twice.

A production plan is a sequence of integers $[a_1, a_2, \dots, a_n]$, where $a_i$ is the number of workers at the $i$-th factory ($l_i \le a_i \le r_i$). After forming a production plan, some factories are chosen as assembly plants to produce automobiles, while the rest produce spare parts. A selection is considered rational if no two assembly plants are directly connected by a road. Among all possible rational selections, the one that maximizes the total number of workers in the assembly plants is chosen. This number is called the efficiency of the plan $[a_1, a_2, \dots, a_n]$.

In this problem, for certain values $v_1, v_2, \dots, v_q$, you need to determine whether a plan with efficiency $v_i$ exists. If such a plan exists, you may be required to provide it.

Fixed integer parameters $x, y,$ and $m$ are given. Consider a plan $[a_1, a_2, \dots, a_n]$. The certificate of this plan is defined as the number $k = \bigoplus_{j=1}^{n} ((x \cdot j + y \cdot a_j^2) \pmod m)$, where $\oplus$ is the bitwise XOR operation.

The process of creating plans consists of two stages.

In the first stage, you are given the values $v_1, v_2, \dots, v_q$. For each of them, you must determine whether a plan with efficiency $v_i$ exists. If it does not exist, output $-1$ for that query; if it does exist, output a non-negative integer $k_i$.

In the second stage, some plans will be verified: you will be given an integer $i$ ($1 \le i \le q$) $c$ times. In response to such a query, you must either output $-1$ if a plan with efficiency $v_i$ does not exist (in which case $k_i = -1$ must have been output earlier), or provide the plan $[a_1, a_2, \dots, a_n]$ whose certificate is $k_i$ and whose efficiency is $v_i$.

The provision of certificates for the created plans and the subsequent verification are implemented in an interactive mode. Before you provide the certificates, you will not know which plans will be verified. Therefore, in subtasks where $c > 0$, you must prepare for verification during the first stage by outputting, for those efficiency values $v_i$ where a plan exists, values $k_i$ for which you will be able to present a plan with certificate $k_i$ during the second stage.

Interaction

This is an interactive problem. Your program will interact with the jury's program using standard input and output. Each interaction consists of solving the problem for several test cases.

First, your program must read an integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then, you must perform the interaction for each test case.

For each test case, your program must first read the data in the following format: The first line contains two integers $n, q$ ($2 \le n \le 2 \cdot 10^5, 1 \le q \le 2 \cdot 10^5$) — the number of cities and the number of plans to be created. The second line contains three integers $x, y, m$ ($11 \le m \le 2^{30}; 0 \le x, y < m$) — the parameters for calculating the plan certificates. The next $n-1$ lines contain the description of the tree. The $i$-th of these lines contains two integers $s_i, f_i$ ($1 \le s_i, f_i \le n; s_i \neq f_i$) — the description of a two-way road between cities $s_i$ and $f_i$. The next $n$ lines each contain two integers $l_i, r_i$ ($0 \le l_i \le r_i \le 10^9$) — the constraints on the number of workers in the $i$-th city. The next line contains $q$ integers $v_1, v_2, \dots, v_q$ ($0 \le v_i \le \sum_{i=1}^n r_i$) — the efficiency values of the plans to be created. It is guaranteed that all $v_i$ are distinct.

After reading the input for a test case, you must output $q$ integers $k_1, k_2, \dots, k_q$ ($-1 \le k_i < 2^{30}$), where $k_i = -1$ if a plan with efficiency $v_i$ cannot be created, otherwise $0 \le k_i < 2^{30}$.

After this, some plans may be verified. The verification is performed as follows: the jury's program outputs a single line containing an integer $i$ ($1 \le i \le q$) — the index of the plan to be verified. It is guaranteed that all requested plan indices are distinct.

In response, you must output $-1$ if the $i$-th plan cannot be created (in which case $k_i = -1$ must have been output earlier). Otherwise, you must output $n$ integers $a_1, a_2, \dots, a_n$ ($l_i \le a_i \le r_i$) — the created plan. The certificate of this plan must be equal to $k_i$, and its efficiency must be equal to $v_i$.

After $c \ge 0$ verifications, the jury's program will pass the integer $i = 0$ to your program, which means that work with this test case is finished, and your solution should start solving the next test case or terminate if this was the last one.

Let $N$ be the sum of $n$ over all test cases, and $Q$ be the sum of $q$ over all test cases. It is guaranteed that $N \le 2 \cdot 10^5$, $Q \le 2 \cdot 10^5$, the sum of $c$ over all test cases does not exceed $10^4$, and the sum of $n \cdot c$ over all test cases does not exceed $10^6$.

Since this is an interactive problem, after each line of output, you must output a newline character and flush the output buffer.

Note

In the examples, the messages from the participant's program and the jury's program are separated by empty lines. This is done for clarity; in the actual interaction, there will be no empty lines.

Examples

Input 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

Output 1

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

Input 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

Output 2

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