You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

琪露诺是一个喜欢研究数表的女孩子。

题目描述

琪露诺有 $n$ 个正整数 $a_1,a_2,...,a_n$，她会按照如下方式构造一个大小为 $n\times n$ 的数字表格：

• 定义数表的左下角为 $(1,1)$，右上角为 $(n,n)$，从左向右数第 $x$ 列，从下向上数第 $y$ 行的位置为 $(x,y)$。在数表的每个位置填入数字 $0$，然后在每个 $(i,i) (1\le i\le n)$ 处填入 $a_i$

• 枚举数表中的每一个 $2\times 2$ 大小的子矩阵，当子矩阵左下角和右上角的数字都不为 $0$ 时，记该子矩阵中从左到右，从上到下的数字分别为 $a,b,c,d$，进行以下操作：

  • 若 $a=0$，$d=0$，则在数表中 $a,d$ 所处的位置填入 $b+c$
  • 若 $a=0$，$d\neq 0$，则在数表中 $a$ 所处的位置填入 $b+c-d$
  • 若 $a\neq 0$，$d=0$，则在数表中 $d$ 所处的位置填入 $b+c-a$

• 重复第二步操作直至数表中的每一个位置都填有正整数 。

• 最后，将数表中的每个数 $a_{ij}$ 变为 $\lfloor \frac{a_{ij}}{k} \rfloor$，其中 $k$ 是一给定常数，$\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数。

构造完 $n\times n$ 的巨大数表后，琪露诺会进行 $q$ 次查询，每次询问数表中以 $(x_1,y_1)$ 为左下角，$(x_2,y_2)$ 为右上角的子矩阵中所有数字的和。

头脑简单的琪露诺想了一天又一天，却始终没有头绪，因此她找到了聪明的你帮她解决这个问题。

当然，由于答案可能很大，你只需要输出答案对 $998244353$ 取模后的结果即可。

输入格式

第一行三个整数 $n,q,k$。

第二行 $n$ 个正整数，表示 $a_i$。

之后 $q$ 行，每行四个正整数 $x_1,y_1,x_2,y_2$，表示询问子矩阵的左下角和右上角坐标。

输出格式

共 $q$ 行，每行一个整数，表示每一个询问的答案对 $998244353$ 取模后的结果。

3 2 2
1 2 3
1 2 2 3
1 1 3 3

7
14

6 3 3
1 1 4 5 1 4
1 1 6 6
1 2 3 4
2 2 5 5

87
14
32

提示

样例 1 解释

第一步操作后的数表：

$ \begin{bmatrix} 0 & 0 & 3 \cr %\cr是换行功能 0 & 2 & 0 \cr 1 & 0 & 0 \end{bmatrix} $

进行一次第二步操作后的数表：

$ \begin{bmatrix} 0 & 5 & 3 \cr %\cr是换行功能 3 & 2 & 5 \cr 1 & 3 & 0 \end{bmatrix} $

进行两次第二步操作后的数表：

$ \begin{bmatrix} 6 & 5 & 3 \cr %\cr是换行功能 3 & 2 & 5 \cr 1 & 3 & 6 \end{bmatrix} $

进行第三步操作(对 $k=2$ 向下取整)后的数表：

$ \begin{bmatrix} 3 & 2 & 1 \cr %\cr是换行功能 1 & 1 & 2 \cr 0 & 1 & 3 \end{bmatrix} $

询问 1 2 2 3 的答案为 $1+1+3+2=7$
询问 1 1 3 3 的答案为 $0+1+3+1+1+2+3+2+1=14$

数据范围：

对于 $100\%$ 的数据，$1 \le n,q \le 2\times 10^5$ ，$0 < a_i ,k \le 10^9$ ，$1 \le x_1 \le x_2 \le n$，$1 \le y_1 \le y_2 \le n$。

注意：本题采取捆绑测试