#2248. 「NOI2014」随机数生成器

内存限制:256 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

小 H 最近在研究随机算法。随机算法往往需要通过调用随机数生成函数(例如 Pascal 中的 random\texttt{random} 和 C/C++ 中的 rand\texttt{rand})来获得随机性。事实上,随机数生成函数也不是真正的「随机」,其一般都是按某个算法计算得来的。

比如,下面这个二次多项式递推算法就是一个常用算法:

算法选定非负整数 x0,a,b,c,dx_0,a,b,c,d,并采用如下公式递推进行计算。

i1, xi=(axi12+bxi1+c)modd\forall i \geq 1,\ x_i=(ax_{i-1}^2+bx_{i-1}+c)\bmod d

这样可以得到一个任意长度的非负整数数列 {xi}i1\{x_i\}_{i \geq 1}。一般说来,我们认为这个数列是随机的。

利用随机序列 {xi}i1\{x_i\}_{i \geq 1},我们还可以采用如下算法产生一个从 11KK随机排列 {Ti}i1K\{T_i\}^K_{i \geq 1}

  1. 初始设 TT1K1 \sim K 的递增序列;
  2. TT 进行 KK 次交换,第 ii 次交换,交换 TiT_iT(ximodi)+1T_{(x_i \bmod i)+1} 的值。

此外,小 H 在这 KK 次交换的基础上,又额外进行了 QQ 次交换工作,对于第 ii 次交换,小 H 会选定两个额外下标 uiu_iviv_i,并交换 TuiT_{u_i}TviT_{v_i} 的值。

为了检验这个随机生成算法的实用性,小 H 设计了如下问题:

小 H 有一个 NNMM 列的棋盘,她首先按照上述过程,通过 N×M+QN\times M+Q 次交换操作,生成一个 1N×M1 \sim N \times M 的随机排列 {Ti}i1N×M\{T_i\}^{N \times M}_{i \geq 1},然后将这 N×MN \times M 个数逐行逐列依次填入这个棋盘:也就是第 ii 行第 jj 列的格子上所填入的数应为 T(i1)M+jT_{(i-1)M+j}

接着小 H 希望从棋盘的左上角,也就是第一行第一列的格子出发,每次向右走或向下走,在不走出棋盘的前提下,走到棋盘的右下角,也就是第 NN 行第 MM 列的格子。

小 H 把所经过格子上的数字都记录了下来,并从小到大排序,这样,对于任何一条合法的移动路径,小 H 都可以得到一个长度为 N+M1N+M-1 的升序序列,我们称之为路径序列

小 H 想知道,她可能得到的字典序最小路径序列应该是怎样的呢?

输入格式

第一行包含五个整数,依次为 x0,a,b,c,dx_0,a,b,c,d ,描述小 H 采用的随机数生成算法所需的随机种子。
第二行包含三个整数 N,M,QN,M,Q,表示小 H 希望生成一个 11N×MN \times M 的排列来填入她 NNMM 列的棋盘,并且小 H 在初始的 N×MN \times M 次交换操作后,又进行了 QQ 次额外的交换操作。
接下来 QQ 行,第 ii 行包含两个整数 ui,viu_i,v_i,表示第 ii 次额外交换操作将交换 TuiT_{u_i}TviT_{v_i} 的值。

输出格式

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

样例

样例输入

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

样例输出

1 2 6 8 9 12

数据范围与提示

本题的空间限制是 256 MB\texttt{256 MB},请务必保证提交的代码运行时所使用的总内存空间不超过此限制。 一个 32\texttt{32} 位整数(例如 C/C++ 中的 int\texttt{int} 和 Pascal 中的 Longint\texttt{Longint})为 4\texttt{4} 字节,因而如果在程序中声明一个长度为 1024×1024\texttt{1024} \times \texttt{1024}32\texttt{32} 位整型变量的数组,将会占用 4 MB\texttt{4 MB} 的内存空间。

对所有的数据,2N,M5000, 0Q50000, 0a300, 0b,c108, 0x0<d108, 1ui,viN×M2 \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

时限已按照 LibreOJ 测评机速度调整。