P2354 [NOI2014] 随机数生成器
题目描述
小 H 最近在研究随机算法。随机算法往往需要通过调用随机数生成函数（例如 Pascal 中的 random 和 C/C++中的 rand）来获得随机性。事实上，随机数生成函数也并不是真正的“随机”，其一般都是利用某个算法计算得来的。
比如，下面这个二次多项式递推算法就是一个常用算法：
算法选定非负整数 $x_0,a,b,c,d$ 作为随机种子，并采用如下递推公式进行计算。
对于任意 $i ≥ 1,x_i=(a \times x_{i-1}^2+b \times x_{i-1}+c)\mod d$ 这样可以得到一个任意长度的非负整数数列$\{x_i\},i \ge 1$，一般来说，我们认为这个数列是随机的。
利用随机序列 ${xi},i≥1$，我们还可以采用如下算法来产生一个 $1$ 到 $K$ 的随机排列$ \{ Ti \},i=1 ... k$：
1. 初始设 $T$ 为 $1$ 到 $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$ 的随机排列 $\{Ti\},i=1 ... N \times M$，然后将这 $N \times M$ 个数逐行逐列依次填入这个棋盘：也就是第 $i$ 行第 $j$ 列的格子上所填入的数应为 $ T_{(i-1) \times M+j} $。
接着小 H 希望从棋盘的左上角，也就是第一行第一列的格子出发，每次向右走或者向下走，在不走出棋盘的前提下，走到棋盘的右下角，也就是第 $N$ 行第 $M$ 列的格子。
小 H 把所经过格子上的数字都记录了下来，并从小到大排序，这样，对于任何一条合法的移动路径，小 H 都可以得到一个长度为 $N + M - 1$ 的升序序列，我们称之为路径序列。
小 H 想知道，她可能得到的字典序最小的路径序列应该是怎样的呢？
输入格式
无
输出格式
无
说明/提示
对于样例 1，根据输入的随机种子，小 H 所得到的前 12 个随机数xi为：
9 5 30 11 64 42 36 22 1 9 5 30
根据这 12 个随机数，小 H 在进行初始的 12 次交换操作后得到的排列为：
6 9 1 4 5 11 12 2 7 10 3 8
在进行额外的 3 次交换操作之后，小 H 得到的最终的随机排列为：
12 9 1 7 5 11 6 2 4 10 3 8
```cpp
12 9 1 7
5 11 6 2
4 10 3 8
```
最优路径依次经过的数字为 ：12-9-1-6-28。
