S. 矩阵滑窗

区间统计是一类相当重要和应用广泛的算法问题。作为问题求解（一）的最后一道 OJ 题，本题希望一路过关斩将来到这里的你能综合运用所学知识解决一道区间统计问题：

现有一个长为 的 矩阵序列 和 个询问，每个询问给出一个区间 ，对于每个询问，你需要给出 。

保证给出的询问满足滑窗性质，即对于第 个询问，对于任意第 个询问（），有 且 。

第一行两个正整数 ，表示矩阵的个数、矩阵的大小和询问个数。

第二行 个非负整数，按矩阵-行-列的优先顺序给出了所有矩阵的数值。

（即先是第一个矩阵第一行各列数值，尔后是第二行，第三行...，然后是第二个矩阵，第三个矩阵...）

接下来 行，第 行两个数 ，表示询问。

输出 行，每行按照行优先的顺序输出每个询问的结果。

由于结果矩阵内的数值可能很大，输出的结果对 取模（这是一个质数）。

我们为模意义下的乘法、加法和除法提供了参考实现（提示：为矩阵求逆也可以使用这里的除法）：

const int mod = 919260817;
int mul(int a, int b) {
  return a * 1ll * b % mod;
}
int add(int a, int b) {
  return (a += b) >= mod ? (a - mod) : a;
}
int inv(int base) {
  int ans = 1;
  for (int k = mod - 2; k; k >>= 1, base = mul(base, base))
    if (k & 1) ans = mul(ans, base);
  return ans;
}
int divide(int a, int b) {
  return mul(a, inv(b));
}

样例输入 1

7 1 2
3 1 2 3 1 2 3
1 3
2 7

样例输出 1

6
36

样例输入 2

3 2 1
1 0 0 1 1 0 1 1 0 1 1 0
1 3

样例输出 2

0 1 1 1

对于前 的数据，有 。（提示：按照题意直接计算）

另有 的数据，有 （提示：线性 RMQ（诈骗版））。

另有 的数据，，所有值不为 （提示：前缀法；求取一个数的逆）。

另有 的数据，保证出现的每个矩阵有逆且 （提示：前缀法；求取矩阵的逆）。

对于全部数据，，矩阵中出现的数字不会大于 。

友情提示：

• 本题考察前缀法和栈。
• 求逆时注意负数。
• 单次操作的复杂度可能很高，但总的复杂度可能很小，你可以利用这种「均摊分析」的思想。