题目描述

给定模质数 $p$ 域上的 $k$ 阶非奇异矩阵列 $a$，给定 $q$ 次询问，每次给出 $l, r$，求 $\prod \limits_{i = l}^r a_i$。$p = 1145141$。

注：模 $p$ 域上的非奇异矩阵指：矩阵乘法加法均在模 $p$ 下进行，矩阵（在实数域下）的行列式值对 $p$ 取余不为 $0$。

输入格式

输入第一行有三个数，依次表示矩阵列长度 $n$、矩阵阶数 $k$ 以及询问数 $q$。

接下来 $n \times k$ 行，每行 $k$ 个整数，依次表示 $n$ 个 $k$ 阶矩阵，详见样例。

接下来 $q$ 行，每行两个整数 $l, r$，表示一次询问。

输出格式

为了避免输出过大，请输出一行一个整数，表示所有询问的答案的所有矩阵元素的按位异或和。

3 3 3
2 2 3
4 5 6
7 8 9
2 2 3
4 5 6
7 8 9
20 20 21
22 23 24
25 26 27
1 2
2 3
1 3

14921

提示

样例 1 解释

$a_1 = \begin{pmatrix} 2 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9\end{pmatrix}$，$a_2 = \begin{pmatrix} 2 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9\end{pmatrix}$，$a_3 = \begin{pmatrix} 20 & 20 & 21 \\ 22 & 23 & 24 \\ 25 & 26 & 27\end{pmatrix}$。

$a_1 \times a_2 = \begin{pmatrix} 33 & 38 & 45 \\ 70 & 81 & 96 \\ 109 & 126 &150 \end{pmatrix}$，$a_2 \times a_3 = \begin{pmatrix}159 & 164 & 171 \\ 340 & 351 & 366 \\ 541 & 558& 582 \end{pmatrix}$，$a_1 \times a_2 \times a_3 = \begin{pmatrix}2621 &2704& 2820 \\ 5582 & 5759 & 6006 \\ 8702 & 8978 & 9363 \end{pmatrix}$。

所有数字的按位异或和为 $14921$。

数据规模与约定

对于全部的测试点，保证 $1 \leq n, q \leq 10^6$，$2 \leq k \leq 3$，$1 \leq l \leq r \leq n$，矩阵元素均为小于 $p$ 的正整数。