Description

Hacker is studying randomized algorithms recently. Randomized algorithms usually achieve randomness by calling random number generating (RNG) functions (such as random in Pascal or rand in C/C++). RNG functions are actually pseudo-random, with numbers created by certain algorithms.

For example, the quadratic congruential generator as stated below is a common algorithm:

Given non-negative integers $x_0,a,b,c,d$, this algorithm calculates the recurrence as follows:

$$\forall i \geq 1, x_i = ( ax_{i-1}^2+bx_{i-1}+c ) \bmod d $$

Therefore a sequence $\{x_i\}_{i \geq 1}$ of non-negative integers of arbitrary length could be generated. In general, we regard this sequence as random.

Using a random sequence $\{x_i\}_{i \geq 1}$, we could also produce a random permutation $\{T_i\}_{i \geq 1}^K$ from $1$ to $K$ according to the algorithm as follows:

1. Initially set T as the increasing sequence of $1 \sim K$;
2. Perform $K$ swaps on $T$, with the $i$th one exchanging the value of $T_i$ and $T_{(x_i \bmod i)+1}$.

Hacker performs $Q$ swaps in addition to the $K$ swaps. For the $i$th additional swap, Hacker chooses two additional indices $u_i$ and $v_i$ and swaps the value of $T_{u_i}$ and $T_{v_i}$.

To put the usefulness of the RNG algorithm to test, Hacker designs a problem:

Hacker begins with a chessboard of $N$ rows and $M$ columns. She starts with the process above, generating a random permutation $\{T_i\}_{i \geq 1}^{N \times M}$ of $1 \sim N \times M$ by $N \times M + Q$ swaps. Then the chessboard is filled by the $N \times M$ numbers rowwise: that is, the number in the $i$th row and $j$th column is $T_{(i-1)M+j}$.

Then Hacker starts from the top-left corner of the board, namely the square in the first row and first column, and move right or down once at a time, without leaving the board, until reaching the bottom-right corner, or the square in the $N$th row and $M$th column.

Hacker records all numbers in passed squares and sorts them into increasing order. Therefore, for any valid route, Hacker could get a increasing sequence of length $N+M-1$ called sequence of route.

Hacker wants to know, what is the sequence of route with the smallest lexicographical order?

Input Format

The first line contains five integers, $x_0,a,b,c,d$ in order, describing the random seed of Hacker's RNG algorithm.

The second line contains three integers $N,M,Q$, indicating Hacker wants to generate a permutation of $1 \sim N \times M$ to fill in her chessboard with $N$ rows and $M$ columns and after the initial $N \times M$ swaps, Hacker performs an additional $Q$ swaps.

The $i$th line in the next $Q$ lines contains two integers $u_i,v_i$, indicating the $i$th additional swap exchanges the value of $T_{u_i}$ and $T_{v_i}$.

Output Format

The output consists of one line of $N+M-1$ integers separated by spaces, representing the sequence of route with the smallest lexicographical order.

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

1 2 6 8 9 12

Constraints and Hint

The memory limit of this problem is $256\ MB$, so please make sure the total memory use of submitted code does not exceed this limit. A $32$-bit integer (such as int in C/C++ or Longint in Pascal) uses $4$ Bytes, so declaring a $1024$ by $1024$ array of $32$-bit integers in the program will consume $4\ MB$ of memory.

For all the data, $2 \leq N,M \leq 5000$, $0 \leq Q \leq 50000$, $0 \leq a \leq 300$, $0 \leq b,c \leq 10^8$, $0 \leq x_0 < d \leq 10^8$, $1 \leq u_i,v_i \leq N \times M$.