#B3646. 数列前缀和 3

数列前缀和 3

题目描述

给定模质数 pp 域上的 kk 阶非奇异矩阵列 aa,给定 qq 次询问,每次给出 l,rl, r,求 i=lrai\prod \limits_{i = l}^r a_ip=1145141p = 1145141

注:模 pp 域上的非奇异矩阵指:矩阵乘法加法均在模 pp 下进行,矩阵(在实数域下)的行列式值对 pp 取余不为 00

输入格式

输入第一行有三个数,依次表示矩阵列长度 nn、矩阵阶数 kk 以及询问数 qq

接下来 n×kn \times k 行,每行 kk 个整数,依次表示 nnkk 阶矩阵,详见样例。

接下来 qq 行,每行两个整数 l,rl, 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}$。

所有数字的按位异或和为 1492114921

数据规模与约定

对于全部的测试点,保证 1n,q1061 \leq n, q \leq 10^62k32 \leq k \leq 31lrn1 \leq l \leq r \leq n,矩阵元素均为小于 pp 的正整数。