Problem Description

Little H is currently studying random algorithms. Random algorithms often require calling random number generation functions (such as random in Pascal and rand in C/C++) to obtain randomness. In fact, random number generation functions are not truly "random"; they are usually calculated using some algorithm.

For example, the following quadratic polynomial recurrence algorithm is a commonly used algorithm:

The algorithm selects non-negative integers $x_0, a, b, c, d$ as random seeds and uses the following recurrence formula for calculation.

For any $i \geq 1, x_i = (a \times x_{i-1}^2 + b \times x_{i-1} + c) \mod d$. This way, an arbitrarily long sequence of non-negative integers $\{x_i\}, i \geq 1$ can be obtained. Generally, we consider this sequence to be random.

Using the random sequence $\{x_i\}, i \geq 1$, we can also generate a random permutation $\{T_i\}, i = 1 \ldots K$ of numbers from 1 to $K$ with the following algorithm:

1. Initialize $T$ as an increasing sequence from 1 to $K$;
2. Perform $K$ swaps on $T$, where the $i$-th swap exchanges the values of $T_i$ and $T_{(x_i \mod i) + 1}$.

Additionally, Little H performs $Q$ extra swap operations on top of these $K$ swaps. For the $i$-th extra swap, Little H selects two indices $u_i$ and $v_i$ and swaps the values of $T_{u_i}$ and $T_{v_i}$.

To test the practicality of this random permutation generation algorithm, Little H designs the following problem:

Little H has an $N$ by $M$ chessboard. She first generates a random permutation $\{T_i\}, i = 1 \ldots N \times M$ of numbers from 1 to $N \times M$ through $N \times M + Q$ swap operations as described above. Then, she fills this $N \times M$ chessboard row by row and column by column with these numbers: the number in the $i$-th row and $j$-th column should be $T_{(i-1) \times M + j}$.

Next, Little H wants to start from the top-left corner of the chessboard, i.e., the first row and first column, and move right or down without stepping out of the chessboard, until she reaches the bottom-right corner, i.e., the $N$-th row and $M$-th column.

Little H records the numbers on the squares she passes through and sorts them in ascending order. Thus, for any valid path, Little H can obtain an ascending sequence of length $N + M - 1$, which we call the path sequence.

Little H wants to know what the lexicographically smallest path sequence she can get is.

Input Format

The first line contains five integers, $x_0, a, b, c, d$, describing the random seeds required for Little H's random number generation algorithm.

The second line contains three integers, $N, M, Q$, indicating that Little H wants to generate a permutation of numbers from 1 to $N \times M$ to fill her $N$ by $M$ chessboard, and she performs $Q$ additional swap operations after the initial $N \times M$ swaps.

The next $Q$ lines, each containing two integers $u_i, v_i$, describe the $i$-th additional swap operation, which swaps the values of $T_{u_i}$ and $T_{v_i}$.

Output Format

Output one line containing $N + M - 1$ positive integers separated by spaces, representing the lexicographically smallest path sequence that can be obtained.

Sample Input and Output

Input Sample #1

1 3 5 1 71 
3 4 3 
1 7 
9 9 
4 9 

Output Sample #1

1 2 6 8 9 12 

Input Sample #2

654321 209 111 23 70000001 
10 10 0 

Output Sample #2

1 3 7 10 14 15 16 21 23 30 44 52 55 70 72 88 94 95 97

Input Sample #3

123456 137 701 101 10000007 
20 20 0 

Output Sample #3

1 10 12 14 16 26 32 38 44 46 61 81 84 101 126 128 135 140 152 156 201 206 237 242 243 253 259 269 278 279 291 298 338 345 347 352 354 383 395 

Notes/Hints

For Sample 1, based on the input random seeds, the first 12 random numbers $x_i$ that Little H obtains are:

9 5 30 11 64 42 36 22 1 9 5 30

Based on these 12 random numbers, the permutation Little H gets after the initial 12 swap operations is:

6 9 1 4 5 11 12 2 7 10 3 8

After the additional 3 swap operations, the final random permutation Little H gets is:

12 9 1 7 5 11 6 2 4 10 3 8

12 9 1 7 
5 11 6 2 
4 10 3 8

The optimal path passes through the numbers: 12-9-1-6-2-8.

见题面 Input 部分

见题面 Output 部分