Description:


小H最近在研究随机算法。随机算法往往需要通过调用随机数生成函数(例如Pascal中的random和C/C++中的rand)来获得随机性。事实上,随机数生成函数也并不是真正的“随机”,其一般都是利用某个算法计算得来的。
比如,下面这个二次多项式递推算法就是一个常用算法:
算法选定非负整数x0,a,b,c,d作为随机种子,并采用如下递推公式进行计算。
对于任意 \(i \ge 1\) , \(x_i=(ax^2_{i-1}+bx_{i-1}+c)\mod d\) .
这样可以得到一个任意长度的非负整数数列 \({x_i}_{i\ge 1}\) ,一般来说,我们认为这个数列是随机的。
利用随机序列 \({x_i}_{i ? 1}\) ,我们还可以采用如下算法来产生一个1到K的随机排列 \({T_i}_{i=1}^K\)
初始设T为1到K的递增序列;
对T进行K次交换,第i次交换,交换 \(T_i\)\(T{(x_i\mod i)+1}\) 的值。
此外,小H在这K次交换的基础上,又额外进行了Q次交换操作,对于第ii次额外交换,小H会选定两个下标ui和vi,并交换 \(T_{u_i}\)\(T_{v_i}\) 的值。
为了检验这个随机排列生成算法的实用性,小H设计了如下问题:
小H有一个N行M列的棋盘,她首先按照上述过程,通过 \(N\times M+Q\) 次交换操作,生成了一个 \(1\)\(N\times M\) 的随机排列 \({T_i }_{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想知道,她可能得到的字典序最小的路径序列应该是怎样的呢?

Input:


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

Output:


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

Sample Input:


Sample Output:


题解:


第一次碰到主要卡内存的题目。。。
啊这个题直接模拟,求得矩阵。。。
然后从小到大枚举,若能够经过该格子,则加入该格子,知道有N+M-1个格子。代码十分短小。
不敢相信这是NOI Day2 T2(O_O)
代码如下: