薇尔莉特

题目背景

### **本题已被sb做法草过。** ----- > 只要客人有意向,不论身在何处,都能上门服务。我是自动手记人偶服务。——薇尔莉特·伊芙加登。 ![](https://cdn.luogu.com.cn/upload/image_hosting/rbwyihgd.png) 薇尔莉特接到了一个奇怪的请求——成为艾米的家庭教师并照顾她的起居。 每当艾米写作业遇到难题时都会向薇尔莉特求助,但薇尔莉特并非无所不知,偶尔也会有不会的题目。这时候就需要大名鼎鼎的 IOI-AKer(没错,说的就是您)来帮忙了。

题目描述

给出一个 $n$ 行 $m$ 列的矩阵(最初全为 $0$),有 $T$ 个操作,每次操作选出一个子矩阵,将其中的所有元素都对 $x$ 进行一次 or,求最后的矩阵。

输入输出格式

输入格式


第一行读入 $4$ 个整数 $n,m,T,HYJ$,其中 $n,m,T$ 意义同上,$HYJ$ 见下方输出格式。 接下来 $T$ 行,每行 $5$ 个整数 $x_1,y_1,x_2,y_2,x$,表示将以点 $(x_1,y_1)$ 为左上角,点 $(x_2,y_2)$ 为右上角的子矩阵中的元素都对 $x$ 进行一次“或”运算。

输出格式


为减少输出,你只需要输出一行三个整数 $Ans1,Ans2$ 以及 $Ans1$ 与 $Ans2$ 的乘积,三者均对 $1000000007$ $(10^9+7)$ 取膜。 其中 $Ans1$ 为最终矩阵所有元素的和,$Ans2$ 为 $HYJ$ 与最终矩阵所有元素异或起来的结果。

输入输出样例

输入样例 #1

3 3 2 486
1 1 2 2 5
1 2 3 3 6

输出样例 #1

48 486 23328

输入样例 #2

4 5 5 10032
2 1 4 4 321
3 5 4 5 23
1 3 3 4 78
1 2 2 3 897
2 4 3 5 302

输出样例 #2

7846 10038 78758148

说明

[**【大样例】**](https://files-cdn.cnblogs.com/files/Xing-Ling/Violet_Bigdata.rar) **【样例解释】** 对于样例一:进行第一次操作的矩阵为 $\{\{5,5,0\},\{5,5,0\},\{0,0,0\}\}$,第二次操作后为 $\{\{5,7,6\},\{5,7,6\},\{0,6,6\}\}$,其和为 $48$,异或和为 $0$,因此 $Ans1$ 为 $48$,$Ans2$ 为 $486$。 **【数据范围】** $Subtask\ 1$ $(20 pt)$ $:$ $1 \leqslant n,m \leqslant 100,$ $1 \leqslant T \leqslant 10^3$ $Subtask\ 2$ $(40 pt)$ $:$ $1 \leqslant n,m \leqslant 500,$ $1 \leqslant T \leqslant 10^5$ $Subtask\ 3$ $(40 pt)$ $:$ $1 \leqslant n,m \leqslant 500,$ $1 \leqslant T \leqslant 10^6$ $100 \%:$ $1 \leqslant x_1 \leqslant x_2 \leqslant n,$ $1 \leqslant y_1 \leqslant y_2 \leqslant m,$ $1 \leqslant x \leqslant 10^9,$ $10$ 个测试点的 $HYJ$ 分别为:$\{2546,114514,364364,889464,1919810,19260817,14000605,998244353,1000000007,1000000009\}$