随机数生成器Ⅱ加强版
时间限制：20s 空间限制：512MB
题目描述
继NOI2014后，小H又发现了一种新的生成随机数的方法。
首先，给定三个随机种子P,C1,C2(C1≤C2)生成一个序列{xi}，{xi}满足
对于任意的i≥0，满足以下递推式Xi+2=(Xi+1+Xi) mod P
其中x0=C1, x1=C2。
接着，利用序列{xi}，可以生成一个序列{ai}。序列{ai}的生成方式如下
对于任意的i≥1，ai=∑xj^2(0≤j≤i) mod P
然后，给定一个正整数Q，小H会进行Q次下述操作：每次选定两个正整数x, y，将ax和ay互换。
小H希望检验一下序列{ai}是否是随机的。他还是希望使用NOI2014那道题的方法，生成一个N×M的矩阵，其中N表示行，M表示列。我们记这个矩阵为D，在D的第1行依次放入a1~aM，第2行放入aM+1~a2M，以此类推，那么矩阵D的第i行第j列的数Di,j就应该为a(i-1)*M+j。然后，类似方格取数，从矩阵的左上角(1,1)走到右下角(N,M)，途中只能向右走或者向下走，这样他经过的方格数就应该是(N+M-1)。然后按照经过的顺序将每个方格的数字提取出来，组成一个序列叫做路径序列。他想知道，自己能得到的字典序最小的路径序列是什么。注意：为了方便，如果当前格向下和向右的方格的数字相同，那么我们认为向下的方格的数字小于向右的方格的数字。
输入格式
输入的第一行为六个正整数N,M,Q,P,C1,C2。意义见题目描述。
接下来的Q行，每行一个操作：包含两个正整数x, y
本题共3个测试点，每个测试点的数据规模大致如下：
N,M≤{200,000, 500,000, 500,000}；
Q=50,000；
P,C1,C2≤1,000,000,000。
另外，为了方便，输入数据中不会出现交换a1或aNM的情况。
请注意I/O优化，以免TLE。
输出格式
设这个路径序列为{si|1≤i≤N+M-1}，你只要输出∑(i×si) mod P的值就可以
样例输入
2 3 2 1000000 0 1 5 3 2 3
样例输出
465
提示
没有写明提示
题目来源
没有写明来源