「Wdoi-1」完美冻结

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

琪露诺有 $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$。 子任务编号 | $\max(n,q)$ | 特殊限制 | 分值 :-: | :-: | :-: | :-: $1$ | $100$ | 无特殊限制 | $5$ $2$ | $500$ | 无特殊限制 | $5$ $3$ | $5000$ | 无特殊限制 | $10$ $4$ | $10^5$ | $q=1$ 且询问子矩阵为整个数表 | $20$ $5$ | $10^5$ | $k=1$ | $15$ $6$ | $10^5$ | $k=2$ | $15$ $7$ | $2*10^5$ | 无特殊限制 | $30$ **注意：本题采取捆绑测试**