Description

Cirno has $n$ positive integers $a_1,a_2,\ldots,a_n$. She constructs a number table of size $n\times n$ in the following way:

• Define the bottom-left corner of the table as $(1,1)$ and the top-right corner as $(n,n)$. The position at column $x$ counted from left to right and row $y$ counted from bottom to top is $(x,y)$. Fill every position in the table with $0$ first, then fill $a_i$ at each $(i,i)$ for $(1\le i\le n)$.

• Enumerate every $2\times 2$ submatrix in the table. When the numbers at the bottom-left corner and the top-right corner of the submatrix are both non-zero, denote the numbers in this submatrix from left to right, top to bottom as $a,b,c,d$, and perform the following operation:

  • If $a=0$ and $d=0$, then fill $b+c$ into the positions of $a$ and $d$ in the table.
  • If $a=0$ and $d\neq 0$, then fill $b+c-d$ into the position of $a$ in the table.
  • If $a\neq 0$ and $d=0$, then fill $b+c-a$ into the position of $d$ in the table.

• Repeat the second step until every position in the table is filled with a positive integer.

• Finally, change every number $a_{ij}$ in the table to $\lfloor \frac{a_{ij}}{k} \rfloor$, where $k$ is a given constant, and $\lfloor x \rfloor$ denotes the greatest integer not exceeding $x$.

After constructing this huge $n\times n$ number table, Cirno will make $q$ queries. Each query asks for the sum of all numbers in the submatrix whose bottom-left corner is $(x_1,y_1)$ and top-right corner is $(x_2,y_2)$.

Simple-minded Cirno has been thinking day after day but still has no clue, so she comes to you for help.

Since the answer may be very large, you only need to output the result modulo $998244353$.

Input Format

The first line contains three integers $n,q,k$.

The second line contains $n$ positive integers, denoting $a_i$.

The next $q$ lines each contain four positive integers $x_1,y_1,x_2,y_2$, denoting the coordinates of the bottom-left and top-right corners of the queried submatrix.

Output Format

Output $q$ lines. Each line contains one integer, denoting the answer to the corresponding query modulo $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

Hint

Sample 1 Explanation

The table after the first step:

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

The table after performing the second step once:

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

The table after performing the second step twice:

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

The table after the third step (floor division by $k=2$):

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

The answer to the query 1 2 2 3 is $1+1+3+2=7$.

The answer to the query 1 1 3 3 is $0+1+3+1+1+2+3+2+1=14$.

Constraints

For $100\%$ of the testdata, $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$, and $1 \le y_1 \le y_2 \le n$.

Note: This problem uses bundled tests.

Translated by ChatGPT 5