Background

Translated from ROI 2023 D2T4.

This is an IO interactive problem.

A country is going to create a car production plan.

There are $n$ cities in the country, and each city has a factory that participates in car production. The factory in the $i$-th city can hire between $l_i$ and $r_i$ workers.

Some pairs of cities are connected by two-way roads, and the road network forms a tree. Therefore, between any two cities there is exactly one path that does not repeat any city.

A production plan is defined as an integer sequence $[a_1, a_2, \dots , a_n]$, where $a_i$ is the number of workers in the $i$-th factory and $l_i\le a_i\le r_i$. After creating the plan, some factories will be chosen as assembly factories, which assemble the cars, while the other factories produce parts. If no two assembly factories are located in cities directly connected by a road, then the plan is valid. Among all possible valid plans, the one that maximizes the total number of workers in the assembly factories is chosen. This maximum is called the efficiency of the plan $[a_1, a_2, \dots , a_n]$.

Problem Description

You need to determine whether a plan with efficiency $v_i$ exists. If such a plan exists, you may need to output one.

The process of creating plans consists of two phases.

In the first phase, you are given the values $v_1,v_2,\dots,v_q$. You must determine whether there exists a plan whose efficiency is $v_i$. If it does not exist, output -1; if it exists, output a non-negative integer $k_i$.

The definition of $k$ is as follows: given three integers $x,y,m$, define the value $k$ of a plan $[a_1, a_2, \dots , a_n]$ as $k = \bigoplus\limits^n_{j=1} ( (x\times j + y\times a_j^2) \bmod m )$, where $\oplus$ is bitwise XOR.

Since there may be more than one plan that meets the requirement, there are also many possible values of $k_i$. You need to output any valid $k_i$.

In the second phase, the feasibility of some plans will be checked. In each query, your program is given an integer $i$ ($1\le i\le q$). For this query, if it is impossible to create a plan with efficiency $v_i$, you must output -1; otherwise, you must output $n$ integers $a_1,a_2,\dots,a_n$ ($l_i\le a_i\le r_i$), representing a plan. The value of $k$ computed from this plan must be equal to the previously output $k_i$, and its efficiency must be $v_i$.

Before printing each $k$, you do not know which plans will be checked. Therefore, you must ensure that the $k_i$ you output in the first phase are correct.

Input Format

This problem has multiple test cases. The first line contains an integer $t$ ($1\le t\le10^4$), the number of test cases.

In each test case:

The first line contains two integers $n,q$ ($2 \le n \le 2 \times 10^5$, $1 \le q \le 2 \times 10^5$), the number of cities and the number of requested efficiencies.

The second line contains three integers $x,y,m$ ($11 \le m \le 2^{30}$, $0 \le x,y < m$), the parameters used to compute $k$.

The next $n-1$ lines describe the road network between the cities. In these $n-1$ lines, the $i$-th line contains two integers $s_i,f_i$ ($1 \le s_i,f_i \le n$, $s_i \ne f_i$), meaning the $i$-th road connects cities $s_i$ and $f_i$ with a two-way road. It is guaranteed that these roads form a tree.

The next $n$ lines: the $i$-th line contains two integers $l_i,r_i$ ($0 \le l_i \le r_i \le 10^9$), the worker limits in the $i$-th city.

The next line contains $q$ integers $v_1,v_2,\dots,v_q$ ($0 \le v_i \le \sum\limits^n_{i=1}r_i$), the efficiencies to be queried. It is guaranteed that all $v_i$ are distinct.

Next, you need to output what is required in the first phase (see “Output Format” for details). Only after you finish outputting can you read the second phase input.

Then follow several lines, each containing one integer $i$ ($0\le i\le q$). When $i\ne0$, $i$ is the index of the plan to be checked. After you output according to the required format, the interactive library will give you the next $i$. When $i=0$, the second-phase checking ends, i.e. this test case is finished. If this is not the last test case, your program should immediately start reading the next one.

It is guaranteed that $\sum n,\sum q\le2\times10^5$. In each test case, the total number of checked plans $c$ is at most $10^4$, and $\sum n\times c\le10^6$.

Output Format

After reading the first phase input of each test case, you need to output $q$ integers $k_1,k_2,\dots,k_q$ ($-1 \le k_i < 2^{30}$). If $k_i = -1$, it means it is impossible to create a plan with efficiency $v_i$. After you output them, the interactive library will provide the second phase input.

After reading the plan index $i$ to be checked in the second phase (and $i\ne0$), if the $i$-th plan cannot be created, i.e. $k_i=-1$, output -1. Otherwise, output $n$ integers $a_1,a_2,\dots,a_n$ ($l_i \le a_i \le r_i$), representing the created plan. The $k$ of this plan must equal $k_i$, and its efficiency must equal $v_i$.

For IO interactive problems, you should flush the output buffer after printing.

If you use cout << ... << endl in C++, System.out.println in Java, print in Python, or writeln in Pascal, the output buffer is flushed automatically and no extra action is needed.

If you use other output methods, it is recommended to flush the output buffer manually. To flush the output buffer, you can use fflush(stdout) in C and C++, flush(output) in Pascal, System.out.flush() in Java, and sys.stdout.flush() in Python.

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

Hint

In the samples, the interaction between the program and the interactive library is separated by blank lines. This is only for easier understanding, so you can clearly see which message replies to which. In the actual test, there will be no extra blank lines (only newlines).

In the first sample, there is only one way to create a plan: $a = [4, 2, 5, 3, 2, 6, 3, 4, 3]$. Its efficiency is $19$, and the computed $k$ is $10$.

The second sample has three test cases.

• In the first test case:
  • There is a unique plan with efficiency $0$: $a = [0, 0, 0]$. Its $k$ is $12$.
  • A plan with efficiency $1$ exists, for example $a = [1, 0, 0]$. Its $k$ is $8$.
  • A plan with efficiency $2$ exists, for example $a = [1, 0, 1]$. Its $k$ is $3$.
  • No plan with efficiency $3$ exists.
  • Among these four requested plans, plan index $i = 2$ ($v_2 = 1$) was checked.
• In the second test case:
  • No plan with efficiency $0$ exists.
  • No plan with efficiency $1$ exists.
  • A plan with efficiency $2$ exists, for example $a = [1, 1, 1, 1]$. Its $k$ is $4$.
  • A plan with efficiency $3$ exists, for example $a = [2, 1, 1, 1]$. Its $k$ is $14$.
  • There is a unique plan with efficiency $4$: $a = [2, 1, 1, 2]$. Its $k$ is $9$.
  • No plan with efficiency $5$ exists.
  • Among these six requested plans, plan index $i = 5$ ($v_5 = 4$), $i = 2$ ($v_2 = 1$), and $i = 3$ ($v_3 = 2$) were checked.
• In the first phase of the third test case, the following plans were requested (starting from the second one, because a plan with efficiency $v_1 = 13$ does not exist): $[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]$.

It is guaranteed that $\sum n,\sum q\le2\times10^5$. In each test case, the total number of checked plans $c$ is at most $10^4$, and $\sum n\times c\le10^6$.

Translated by ChatGPT 5