#6913. 树莓立方体

题目描述

Minato 有一块 $k$ 行 $n$ 列的农田，每个位置有一株莓果，每株莓果上都结了许多大小相同的果实。具体来说，第 $i$ 行第 $j$ 列的莓果的果实大小为一个正整数 $a_{i,j}$ $(1\le i\le k, 1\le j\le n)$，果实的数量足够多，是摘不完的。

Minato 定制了一个自动摘莓果机器人。具体来说，这个机器人需要输入两个参数 $x,y$ $(x\le y)$，之后它会扫描农田的第 $x$ 列到第 $y$ 列，找到每一行在 $x$ 到 $y$ 列中大小最小的莓果，在每一行的最小莓果中取最大的摘下一个，将其榨成汁。果实大小为 $M$ 的莓果榨成汁之后，口味的奇妙值为 $F(M)=A\oplus (BM+C)$，其中 $A,B,C$ 是三个非负整数的常数，$\oplus$ 表示二进制按位异或。

Minato 在 $q$ 天中的每一天都会用这个机器人采收莓果。每天，Minato 会选定一个范围 $[l,r]$，对于每一对在这个范围内的不同的 $x,y$ $(l\le x\le y\le r)$，Minato 都会以 $x,y$ 参数调用一次机器人。当天混合果汁的风味值为每次调用机器人榨出的果汁的奇妙值的总和。

Minato 想知道每天混合果汁的风味值是多少。

形式化地说，给定 $k$ 行 $n$ 列的正整数矩阵：

$$(a_{i, j})_{1 \leq i \leq k, \, 1 \leq j \leq n}$$

有 $q$ 个询问任务，对于每个询问任务 $[l, r]$，需要计算以下公式：

$$\sum_{l \leq x \leq y \leq r} F\left(\max_{i=1}^k \left( \min_{j=x}^y a_{i,j} \right)\right) $$

其中 $F(M) = A \oplus ( BM + C )$，$A,B,C$ 是三个非负整数的常数，$\oplus$ 表示二进制按位异或。

---

输入格式

请注意这道题需要使用文件输入输出，例如 freopen。文件名见题目标题下方的评测信息。

第一行输入三个整数 $k$、$n$ 和 $q$，分别表示农田的行数、列数和询问任务的个数。

接下来的 $k$ 行，每行输入 $n$ 个整数，表示每株莓果果实的大小。

接下来一行输入三个整数 $A$、$B$ 和 $C$，表示榨果汁的奇妙值 $F(M)$ 的参数。

接下来 $q$ 行，每行输入两个整数 $l$ 和 $r$，表示 Minato 每天选择的范围 $[l, r]$。

---

输出格式

请注意这道题需要使用文件输入输出，例如 freopen。文件名见题目标题下方的评测信息。

输出 $q$ 个整数，其中第 $i$ 个整数表示第 $i$ 天的混合果汁风味值。

---

样例

输入

3 4 10
5 8 3 6
7 2 4 1
9 5 2 7
3 2 1
1 1
1 2
1 3
1 4
2 2
2 3
2 4
3 3
3 4
4 4

输出

16
42
60
84
18
32
52
10
26
12

样例解释 1

农田的布局和植物的健康值：

列1	列2	列3	列4
行1	5	8	3
行2	7	2	4
行3	9	5	2

在这个表格中，第 $i$ 行第 $j$ 列的数字 $a_{i, j}$ 表示种植在第 $i$ 行第 $j$ 列的果实大小。例如，$a_{2, 3} = 4$ 表示第 $2$ 行第 $3$ 列的果实大小为 $4$。

举例说明 $M,F$：用 $M(x,y)$ 表示机器人参数为 $x,y$ 时采摘的果实大小。则，$M(1,3)=\max(\min(5,8,3),\min(7,2,4),\min(9,5,2))=\max(3,2,2)=3$，而对应的奇妙值 $F(M(1,3))=F(3)=3 \oplus (2\times 3+1)=4$。（这组数据中 $A=3,B=2,C=1$）

类似地，可以算出 $M(1,2)=\max(\min(5,8),\min(7,2),\min(9,5))=5$, $M(2,3)=3$, $M(1,1)=9$, $M(2,2)=8$, $M(3,3)=4$。对应的奇妙值 $F$ 分别为 $F(M(1,2))=F(5)=8$, $F(M(2,3))=4$, $F(M(1,1))=16$, $F(M(2,2))=18$, $F(M(3,3))=10$。

所以，询问 $[1,3]$ 的风味值为 $4+8+4+16+18+10=60$。

样例 2、3、4、5 见附加文件。

---

数据范围与提示

对于 $100\%$ 的数据，$1\leq k \leq 20$，$1\leq n \leq 50000$，$1\leq q \leq 50000$，$1 \leq a_{i, j} \leq 10^7$，$0 \leq A \leq 10^8$, $0\leq B, C \leq 10$

一共有 $20$ 个测试点。部分测试点满足的性质如下：

• 1 号：$A=B=0$；
• 1,2 号：$k \leq 10$，$n \leq 200$，$q \leq 200$；
• 1,2,3,4,5,6,7 号：$k \leq 10$，$n \leq 2000$，$q \leq 2000$；
• 8,9,10,11,12 号：$k = 1$；
• 8,9,13,14,15 号：$a_{i,j} \leq 2$；