描述

小 H 最近在研究随机算法。随机算法往往需要通过调用随机数生成函数(例 如 Pascal 中的 random 和 C/C++中的 rand)来获得随机性。事实上,随机数生成 函数也并不是真正的“随机”,其一般都是利用某个算法计算得来的。
比如,下面这个二次多项式递推算法就是一个常用算法:
算法选定非负整数 𝑥0, 𝑎, 𝑏, 𝑐, 𝑑 作为随机种子,并采用如下递推公式进行计 算。
对于任意𝑖≥1, 𝑥 =(𝑎⋅𝑥^2 +𝑏⋅𝑥 +𝑐)mod 𝑑
这样可以得到一个任意长度的非负整数数列{𝑥𝑖}𝑖≥1,一般来说,我们认为这 个数列是随机的。
利用随机序列{𝑥𝑖}𝑖≥1,我们还可以采用如下算法来产生一个 1 到 K 的随机排 列{𝑇}𝐾 :
1、初始设 T 为 1 到 K 的递增序列;
2、对 T 进行 K 次交换,第 𝑖 次交换,交换 𝑇𝑖 和 𝑇(𝑥𝑖 mod 𝑖)+1 的值。
此外,小 H 在这 𝐾 次交换的基础上,又额外进行了 𝑄 次交换操作,对于第 𝑖 次额外交换,小 H 会选定两个下标 𝑢𝑖 和 𝑣𝑖 ,并交换 𝑇𝑢𝑖 和 𝑇𝑣𝑖 的值。
为了检验这个随机排列生成算法的实用性,小 H 设计了如下问题:
小 H 有一个 𝑁 行 𝑀 列的棋盘,她首先按照上述过程,通过 𝑁 × 𝑀 + 𝑄 次交
换操作,生成了一个 1~𝑁 × 𝑀 的随机排列 {𝑇 }𝑁×𝑀,然后将这 𝑁 × 𝑀 个数逐行逐 𝑖 𝑖=1
列依次填入这个棋盘:也就是第 𝑖 行第 𝑗 列的格子上所填入的数应为 𝑇(𝑖−1)⋅𝑀+𝑗 。
接着小 H 希望从棋盘的左上角,也就是第一行第一列的格子出发,每次向 右走或者向下走,在不走出棋盘的前提下,走到棋盘的右下角,也就是第 𝑁 行第
𝑀 列的格子。
小 H 把所经过格子上的数字都记录了下来,并从小到大排序,这样,对于任 何一条合法的移动路径,小 H 都可以得到一个长度为 𝑁 + 𝑀 − 1 的升序序列, 我们称之为路径序列。
小 H 想知道,她可能得到的字典序最小的路径序列应该是怎样的呢?

格式

输入格式

输入的第 1 行包含 5 个整数,依次为 𝑥0, 𝑎, 𝑏, 𝑐, 𝑑 ,描述小 H 采用的随
机数生成算法所需的随机种子。
第 2 行包含三个整数 𝑁, 𝑀, 𝑄 ,表示小 H 希望生成一个 1 到 𝑁 × 𝑀 的排列来 填入她 𝑁 行 𝑀 列的棋盘,并且小 H 在初始的 𝑁 × 𝑀 次交换操作后,又进行了 𝑄 次额外的交换操作。
接下来 𝑄 行,第 𝑖 行包含两个整数 𝑢𝑖 , 𝑣𝑖 ,表示第 𝑖 次额外交换操作将交换 𝑇𝑢𝑖和𝑇𝑣𝑖 的值。

输出格式

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

样例1

样例输入1

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

样例输出1

1 2 6 8 9 12

样例2

样例输入2

654321 209 111 23 70000001
10 10 0

样例输出2

1 3 7 10 14 15 16 21 23 30 44 52 55 70 72 88 94 95 97

样例3

样例输入3

123456 137 701 101 10000007
20 20 0

样例输出3

1 10 12 14 16 26 32 38 44 46 61 81 84 101 126 128 135 140 152 156 201 206 237 242 243 253 259 269 278 279 291 298 338 345 347 352 354 383 395

限制

2 ≤ 𝑁, 𝑀 ≤ 5000
0 ≤ 𝑄 ≤ 50000
0 ≤ 𝑎 ≤ 300
0 ≤ 𝑏, 𝑐 ≤ 10^8
0≤𝑥0 <𝑑≤10^8
1≤𝑢𝑖,𝑣𝑖 ≤𝑁×𝑀

来源

NOI 2014 Day 2