Little H has recently been studying randomized algorithms. Randomized algorithms often require randomness obtained by calling a random number generator (such as random in Pascal or rand in C/C++). In fact, random number generators are not truly "random"; they are generally calculated using some algorithm.

For example, the following quadratic polynomial recurrence algorithm is a commonly used one: 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 \ge 1$, $x_i = (a \cdot x_{i-1}^2 + b \cdot x_{i-1} + c) \pmod d$.

This yields a sequence of non-negative integers $\{x_i\}_{i \ge 1}$ of any length. Generally, we consider this sequence to be random.

Using the random sequence $\{x_i\}_{i \ge 1}$, we can also use the following algorithm to generate a random permutation $\{T_i\}_{i=1}^K$ of $1$ to $K$:

1. Initially, set $T$ as an increasing sequence from $1$ to $K$.
2. Perform $K$ swaps on $T$. For the $i$-th swap, swap the values of $T_i$ and $T_{(x_i \pmod i) + 1}$.

In addition, based on these $K$ swaps, Little H performs $Q$ extra swap operations. 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 designed the following problem:

Little H has an $N \times M$ chessboard. She first generates a random permutation $\{T_i\}_{i=1}^{N \times M}$ of $1$ to $N \times M$ using the process described above (with $K = N \times M$), and then fills these $N \times M$ numbers into the chessboard row by row and column by column: that is, the number filled in the cell at row $r$ and column $c$ is $T_{(r-1) \cdot M + c}$.

Next, Little H wants to start from the top-left corner of the chessboard (the cell at row 1, column 1), and move to the bottom-right corner (the cell at row $N$, column $M$) by only moving right or down, without leaving the chessboard.

Little H records the numbers on the cells 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 is the lexicographically smallest path sequence she can obtain?

Input

The first line of the input file contains 5 integers: $x_0, a, b, c, d$, describing the random seeds required for the random number generation algorithm used by Little H. The second line contains three integers $N, M, Q$, representing that Little H wishes to generate a permutation of $1$ to $N \times M$ to fill her $N \times M$ chessboard, and that after the initial $N \times M$ swap operations, she performs $Q$ additional swap operations. The next $Q$ lines each contain two integers $u_i, v_i$, representing that the $i$-th additional swap operation swaps the values of $T_{u_i}$ and $T_{v_i}$.

Output

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

Examples

Input 1

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

Output 1

1 2 6 8 9 12

Input 2

654321 209 111 23 70000001
10 10 0

Output 2

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

Input 3

123456 137 701 101 10000007
20 20 0

Output 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

Note

For Example 1, based on the input random seeds, the first 12 random numbers $x_i$ obtained by Little H are: 9 5 30 11 64 42 36 22 1 9 5 30 Based on these 12 random numbers, the permutation obtained by Little H after the initial 12 swap operations is: 6 9 1 4 5 11 12 2 7 10 3 8 After performing the 3 additional swap operations, the final random permutation obtained by Little H is: 12 9 1 7 5 11 6 2 4 10 3 8 This random permutation results in the following chessboard:

The numbers passed through by the optimal path are: 12 $\to$ 9 $\to$ 1 $\to$ 6 $\to$ 2 $\to$ 8.

For Example 3, due to the limited width of the page, line breaks appear in the example output. Please note that these line breaks are for display purposes only; in fact, the example output consists of exactly one line, and all numbers should appear on the same line.

Input 4

See random/random.in and random/random.ans in the contestant directory.

Output 4

See random/random.in and random/random.ans in the contestant directory.

Constraints

The range and characteristics of all test data are shown in the table below:

Note

The memory limit for this problem is 256 MB. Please ensure that the total memory used by your submitted code does not exceed this limit. A 32-bit integer (such as int in C/C++ and Longint in Pascal) is 4 bytes. Therefore, declaring an array of 32-bit integer variables with a size of $1024 \times 1024$ will occupy 4 MB of memory.