题面描述

关于在另一条世界线由于你没有帮出题人打总力战于是出题人急死啦并穿越到了异世界然后努力回到现实世界继续凹总力战让你感到励志不已然后答应帮忙凹总力战这档事。

异世界的空间非常奇怪，大概可以看成一个 $(n+2)\times m$ 的网格，行标号为 $0\sim n+1$，列标号为 $1\sim m$ ，每次可以从某一行的任意位置传送到相邻行的任意位置，初始时出题人在第 $0$ 行，通往现实世界的传送门在第 $n+1$ 行，第 $i$ 行第 $j$ 列网格上有一个战斗力为 $a_{i,j}$ 的怪物，只有出题人战斗力高于 $a_{i,j}$ 时才能通过这个格子，第 $0$ 行和第 $n+1$ 行没有怪物，但是这个异世界极其不稳定，所以可能会坍塌成只有 $[x,y]$ 列。

在等出题人回来的这段时间里你非常无聊，所以你想 $Q$ 次询问 $[l,r]$ ，算出

$$\sum_{[x,y]\in [l,r],[x,y]\neq\empty} f(x,y)$$

其中 $f(x,y)$ 是异世界坍塌成只有 $[x,y]$ 列时出题人回到现实世界所需的最小战斗力。

但你发现你其实并不关心出题人能不能回到现实世界，于是你想求出

$$\sum_{[x,y]\in [l,r],[x,y]\neq\empty} t_1 \oplus (t_2f(x,y)+t_3) $$

其中 $\oplus$ 表示异或。

输入格式

第一行三个正整数 $n,m,q$；

接下来 $n$ 行，每行 $m$ 个正整数表示 $a$（左上角为 $a_{1,1}$）；

接下来一行三个整数 $t_1,t_2,t_3$；

接下来 $q$ 行，每行两个正整数 $l,r(1\leq l\leq r\leq n)$，表示一次询问。

输出格式

$q$ 行，第 $i$ 行输出第 $i$ 个询问的答案。

输入输出样例

Sample Input 1	Sample Output 1
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

$f(1,1)$：出题人只能走 $5\to7\to9$，则 $f(1,1)=9$；

$f(1,2)$：出题人可以走 $5\to2\to5$，则 $f(1,2)=5$；

$f(1,3)$：出题人可以走 $3\to2\to2$，则 $f(1,3)=3$；

$f(1,4)$：出题人可以走 $3\to1\to2$，则 $f(1,4)=3$；

$f(2,2)=8,f(2,3)=3,f(2,4)=3,f(3,3)=4,f(3,4)=3,f(4,4)=7$。

【数据规模及约定】

对于 $100\%$ 的数据，$1\leq n\leq20$，$1\leq m,q\leq5\times10^4$，$1\leq a_{i,j}\leq10^7$，$0\leq t_1\leq10^8$，$0\leq t_2,t_3\leq10$。

测试点编号	$n\leq$	$m,q\leq$	特殊性质
$1$	$10$	$200$	$t_1=t_2=0$
$2$			-
$3\sim7$		$2000$
$8\sim9$	$1$	$5\times10^4$	$a_{i,j}\leq2$
$10\sim12$			-
$13\sim15$	$20$		$a_{i,j}\leq2$
$16\sim20$