唐时月夜

题目背景

Oh, how beautiful it used to be

Just you and me far beyond the sea,

The waters' scarce in motion

Quivering still.

题目描述

小X是一名X国的附魔师。

静谧的月夜，水域中倒映着明亮的夜空，这正是水域中魔力最旺盛的时候。小X面前的水域可以被分成$N$行$M$列的子水域，每一片子水域存在「魔力值」$A_{i,j}$。根据「水域之书」的记载，存在线性递推序列$f_0=c,f_i=a\times f_{i-1}+b\ (i\geq 1)$，初始时，「魔力值」矩阵满足$$A_{i,j}=f_{(i-1)\times M+j}$$

小X需要根据「预言」的指示按顺序对这片水域施展$Q$次魔法，具体来说，「预言」的指示分为以下几种：

$1$、选定一个矩形的子水域$A[x_1...x_2,y_1...y_2]$，对其进行「左右倒置」操作，即对于这个子水域的每一行，翻转「魔力值」序列。

$2$、选定一个矩形的子水域$A[x_1...x_2,y_1...y_2]$，对其进行「上下倒置」操作，即对于这个子水域的每一列，翻转「魔力值」序列。

$3$、选定一个正方形 的子水域$A[x_1...x_2,y_1...y_2]$，对其进行「行列倒置」操作，即沿着这个子水域的主对角线，翻转「魔力值」矩阵。

同时，为了保证施法的连续性，「预言」的指示保证如果一片子水域曾经被操作过，那么在之后的施法中，这片子水域也一定会被操作。

在完成全部的施法后，小X需要根据「魔力值」矩阵，计算出「魔力神谕」，即$$\sum_{i=1}^{N}\sum_{j=1}^{M}A_{i,j}\times f_{(i-1)\times M+j}$$

由于「魔力神谕」可能很大，小X只需要知道「魔力神谕」在模$2^{32}$意义下的数值就可以了。

输入格式

第一行一个整数$Num$，表示测试点编号，以便选手方便地获得部分分，你可能不需要用到这则信息，样例中$Num$的含义为数据范围与某个测试点相同。

接下来一行3个整数$N,M,Q$，分别表示水域的大小，以及「预言」指示的次数。

接下来一行3个整数$a,b,c$，表示「水域之书」中记载的线性递推序列。

接下来$Q$行，每行5个整数$opt,x_1,y_1,x_2,y_2$，表示「预言」的一次指示。

输出格式

输出一行一个整数$Ans$，表示「魔力神谕」在模$2^{32}$意义下的数值。

样例1输入

2
3 4 3
1 1 0
1 2 2 3 3
2 2 2 3 4
3 1 2 3 4

样例1输出

576

样例1解释

初始时，「魔力值」矩阵如下： $$\begin{pmatrix} 1 & 2 & 3 & 4 \\ 5 & 6 & 7 & 8 \\ 9 & 10 & 11 & 12 \end{pmatrix}$$

在第1次「预言」的指示后，「魔力值」矩阵如下： $$\begin{pmatrix} 1 & 2 & 3 & 4 \\ 5 & 7 & 6 & 8 \\ 9 & 11 & 10 & 12 \end{pmatrix}$$

在第2次「预言」的指示后，「魔力值」矩阵如下： $$\begin{pmatrix} 1 & 2 & 3 & 4 \\ 5 & 11 & 10 & 12 \\ 9 & 7 & 6 & 8 \end{pmatrix}$$

在第3次「预言」的指示后，「魔力值」矩阵如下： $$\begin{pmatrix} 1 & 2 & 11 & 7 \\ 5 & 3 & 10 & 6 \\ 9 & 4 & 12 & 8 \end{pmatrix}$$

可以计算得到「魔力神谕」在模$2^{32}$意义下的数值为$576$。

样例2

见下发文件ex_evernight2.in，ex_evernight2.out

点此下载

数据范围与约定

对于所有测试数据，保证$1\leq N,M\leq 4\times10^3$，$0\leq Q\leq 2\times10^5$，$0\leq a,b,c \lt 2^{32}$，$opt\in\{1,2,3\}$，$1\leq x_1\leq x_2\leq N$，$1\leq y_1\leq y_2\leq M$。

对于$opt=3$的指示，保证$x_2-x_1=y_2-y_1$。

保证如果一片子水域曾经被操作过，那么在之后的施法中，这片子水域也一定会被操作。

详细的数据范围见下表。