Efficient Plan Verification

In this problem, you are required to design a plan in two phases based on given queries. A plan is defined as an array of n integers [a₁, a₂, …, aₙ] where each aᵢ satisfies lᵢ ≤ aᵢ ≤ rᵢ. For any plan, a value k is computed as

[ k = \bigoplus_{j=1}^{n} \Bigl((x \times j + y \times a_j^2) \bmod m\Bigr), ]

where (\oplus) denotes the bitwise XOR operation.

The problem proceeds in two phases:

Phase 1 (Plan Preprocessing):
You are first given integers n, q, x, y, m. Then, n lines follow, each containing two integers lᵢ and rᵢ representing the bounds for aᵢ. Next, you are given q integers v₁, v₂, …, v_q. For each efficiency value vᵢ, determine if there exists any plan whose efficiency equals vᵢ. In our simplified version, we define the efficiency of a plan as the computed k value. To guarantee a correct answer for every query, we use a trivial plan where we choose aᵢ = lᵢ for all i. Let

[ K_0 = \bigoplus_{j=1}^{n} \Bigl((x \times j + y \times l_j^2) \bmod m\Bigr). ]

A valid plan for efficiency vᵢ exists if and only if vᵢ = K₀. For each vᵢ, if vᵢ equals K₀, output K₀; otherwise, output -1. These answers form the phase 1 output (one answer per query in the order provided).

Phase 2 (Plan Construction Queries):
After phase 1, you are given an integer t representing the number of plan verification queries, followed by t queries. Each query is an integer i (1 ≤ i ≤ q). For each query, if a valid plan for vᵢ does not exist (i.e. if the phase 1 answer was -1), output -1; otherwise, output n integers: a valid plan [a₁, a₂, …, aₙ] (each satisfying lᵢ ≤ aᵢ ≤ rᵢ) such that its computed k is exactly the k value you output in phase1 (which will be K₀). Here, you may simply output the trivial plan where aᵢ = lᵢ for all i.

Input Format:

1. Line 1 contains five integers: n, q, x, y, m.
2. The next n lines each contain two integers: lᵢ and rᵢ (for 1 ≤ i ≤ n).
3. The next line contains q integers: v₁, v₂, …, v_q.
4. The next line contains an integer t, the number of queries in phase 2.
5. Then t lines follow, each with one integer i (1 ≤ i ≤ q).

Output Format:

1. First, output q lines corresponding to the phase 1 answers. For each efficiency value vᵢ, output:
   • k = K₀ if a plan exists (i.e. if vᵢ = K₀).
   • -1 if no plan exists (vᵢ ≠ K₀).
2. Then, for each of the t queries in phase 2, output on a new line either:
   • The plan as n space-separated integers (if a valid plan exists for that query), or
   • -1 (if no valid plan exists for the queried efficiency).

Note: Since we use the trivial plan aᵢ = lᵢ for all i, the computed K₀ is

[ K_0 = \bigoplus_{j=1}^{n} \Bigl((x \times j + y \times l_j^2) \bmod m\Bigr). ]

You must design your solution so that it computes K₀ and then, for each query, verifies if vᵢ = K₀. If so, use the trivial plan in phase 2; otherwise output -1.

inputFormat

The input begins with a line containing five integers: n, q, x, y, m.

Then follow n lines, each containing two integers, lᵢ and rᵢ (1 ≤ i ≤ n).

The next line contains q integers: v₁, v₂, …, v_q.

The next line contains an integer t, representing the number of queries in phase 2.

Then follow t lines, each with a single integer i (1 ≤ i ≤ q), representing a phase 2 query.

outputFormat

Output consists of two parts.

1. Phase 1: q lines, each line is either the integer k (if a valid plan exists for vᵢ) or -1.
2. Phase 2: For each query, output a line containing either -1 (if no valid plan exists) or n integers representing a valid plan (each aᵢ with lᵢ ≤ aᵢ ≤ rᵢ and the plan's computed k equal to the one printed in phase 1).

sample

3 2 1 1 100
1 5
2 6
3 7
10 15
2
1
2

-1
-1
-1
-1

</p>