#P6528. 「Wdoi-1」完美冻结

「Wdoi-1」完美冻结

题目背景

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

题目描述

琪露诺有 nn 个正整数 a1,a2,...,ana_1,a_2,...,a_n,她会按照如下方式构造一个大小为 n×nn\times n 的数字表格:

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

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

    • a=0a=0d=0d=0,则在数表中 a,da,d 所处的位置填入 b+cb+c
    • a=0a=0d0d\neq 0,则在数表中 aa 所处的位置填入 b+cdb+c-d
    • a0a\neq 0d=0d=0,则在数表中 dd 所处的位置填入 b+cab+c-a
  • 重复第二步操作直至数表中的每一个位置都填有正整数

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

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

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

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

输入格式

第一行三个整数 n,q,kn,q,k

第二行 nn 个正整数,表示 aia_i

之后 qq 行,每行四个正整数 x1,y1,x2,y2x_1,y_1,x_2,y_2,表示询问子矩阵的左下角和右上角坐标。

输出格式

qq 行,每行一个整数,表示每一个询问的答案对 998244353998244353 取模后的结果。

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=2k=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=71+1+3+2=7
询问 1 1 3 3 的答案为 0+1+3+1+1+2+3+2+1=140+1+3+1+1+2+3+2+1=14

数据范围:

对于 100%100\% 的数据,1n,q2×1051 \le n,q \le 2\times 10^50<ai,k1090 < a_i ,k \le 10^91x1x2n1 \le x_1 \le x_2 \le n1y1y2n1 \le y_1 \le y_2 \le n

子任务编号 max(n,q)\max(n,q) 特殊限制 分值
11 100100 无特殊限制 55
22 500500
33 50005000 1010
44 10510^5 q=1q=1 且询问子矩阵为整个数表 2020
55 k=1k=1 1515
66 k=2k=2
77 21052*10^5 无特殊限制 3030

注意:本题采取捆绑测试