UOJ Logo

NOI.AC

1S 512MB
Statistics

Description

给出一种生成随机数的方式

先给你三个数$P,C_1,C_2$,按照$x_{i+2}=(x_{i+1}+x_{i})\ mod\ P$生成,其中$x_0=C_1$,$x_1=C_2$

然后利用$\{x_i\}$生成$a_i$,其中$a_i=(\sum_{j=0}^i x_j^2)\ mod\ P$

然后给出$Q$次操作,每次给出两个数$x,y$,表示交换$a_x,a_y$

接着使用NOI2014验证随机数的方式,把$\{a_i\}$放进$n\times m$的矩阵里面,具体的,第一行按顺序放入$a_1,a_2,...,a_m$,第二行按顺序放入$a_{m+1},a_{m+2},...,a_{2m}$

然后从$(1,1)$走到$(n,m)$,每步要不横坐标加一要不纵坐标加一,把经过的数记录下来得到一个长度为$n+m-1$的数列,把字典序最小的方案输出来就可以了,其中为了方便,如果存在横坐标加一和纵坐标加一的位置数字相同,我们认为横坐标加一的位置更小

Input

第一行六个整数$n,m,Q,P,C_1,C_2$,如题所述

接下来$Q$行,每行两个整数$x,y$,如题所述

Output

一行$n+m-1$个数,表示答案

Sample Input

2 3 2 1000000 0 1

5 3

2 3

Sample Output

1 15 6 104

Tips

对于样例,生成的序列${ai}$为${1, 2, 6, 15, 40, 104}$,按输入顺序交换后变为${1, 40, 2, 15, 6, 104}$,将其放入2行3列的矩阵,不难看出能够得到的字典序最小的路径序列就是${1, 15, 6, 104}$。

Constraints

$Q\leq 100000$

$P,C1,C2\leq 1000000000$

本题使用Subtask测试

Subtask1(20pts): $n,m\leq 5000$

Subtask2(30pts): $n,m\leq 50000$

Subtask3(50pts): $n,m\leq 100000$