4273: 「NOI2014」随机数生成器

小 H 最近在研究随机算法。随机算法往往需要通过调用随机数生成函数（例如 Pascal 中的 $\texttt{random}$ 和 C/C++ 中的 $\texttt{rand}$）来获得随机性。事实上，随机数生成函数也不是真正的「随机」，其一般都是按某个算法计算得来的。 比如，下面这个二次多项式递推算法就是一个常用算法： 算法选定非负整数 $x_0,a,b,c,d$，并采用如下公式递推进行计算。 $$\forall i \geq 1,\ x_i=(ax_{i-1}^2+bx_{i-1}+c)\bmod d$$ 这样可以得到一个任意长度的非负整数**数列** $\{x_i\}_{i \geq 1}$。一般说来，我们认为这个**数列**是随机的。 利用随机序列 $\{x_i\}_{i \geq 1}$，我们还可以采用如下算法产生一个从 $1$ 到 $K$ 的**随机排列** $\{T_i\}^K_{i \geq 1}$： 1. 初始设 $T$ 为 $1 \sim K$ 的递增序列； 2. 对 $T$ 进行 $K$ 次交换，第 $i$ 次交换，交换 $T_i$ 和 $T_{(x_i \bmod i)+1}$ 的值。 此外，小 H 在这 $K$ 次交换的基础上，又**额外**进行了 $Q$ 次交换工作，对于第 $i$ 次交换，小 H 会选定两个额外下标 $u_i$ 和 $v_i$，并交换 $T_{u_i}$ 和 $T_{v_i}$ 的值。 为了检验这个随机生成算法的实用性，小 H 设计了如下问题： 小 H 有一个 $N$ 行 $M$ 列的棋盘，她首先按照上述过程，通过 $N\times M+Q$ 次交换操作，生成一个 $1 \sim N \times M$ 的随机排列 $\{T_i\}^{N \times M}_{i \geq 1}$，然后将这 $N \times M$ 个数逐行逐列依次填入这个棋盘：也就是第 $i$ 行第 $j$ 列的格子上所填入的数应为 $T_{(i-1)M+j}$。 接着小 H 希望从棋盘的左上角，也就是第一行第一列的格子出发，**每次向右走或向下走**，在不走出棋盘的前提下，走到棋盘的右下角，也就是第 $N$ 行第 $M$ 列的格子。 小 H 把所经过格子上的数字都记录了下来，并**从小到大排序**，这样，对于任何一条合法的移动路径，小 H 都可以得到一个长度为 $N+M-1$ 的升序序列，我们称之为**路径序列**。 小 H 想知道，她可能得到的**字典序最小**的**路径序列**应该是怎样的呢？

第一行包含五个整数，依次为 $x_0,a,b,c,d$ ，描述小 H 采用的随机数生成算法所需的随机种子。 第二行包含三个整数 $N,M,Q$，表示小 H 希望生成一个 $1$ 到 $N \times M$ 的排列来填入她 $N$ 行 $M$ 列的棋盘，并且小 H 在初始的 $N \times M $ 次交换操作后，又进行了 $Q$ 次额外的交换操作。 接下来 $Q$ 行，第 $i$ 行包含两个整数 $u_i,v_i$，表示第 $i$ 次额外交换操作将交换 $T_{u_i}$ 和 $T_{v_i}$ 的值。

输出一行，包含 $N+M-1$ 个由空格隔开的正整数，表示可以得到的字典序最小的路径序列。

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

1 2 6 8 9 12