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$，如题所述

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

2 3 2 1000000 0 1

5 3

2 3

1 15 6 104

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

$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$