Constructing and Querying the Number Table

In this problem, you are given an integer ( n ) and ( n ) positive integers ( a_1,a_2,\dots,a_n ) along with a constant ( k ). A gigantic ( n\times n ) table is constructed as follows:

1. Label the table coordinates as ( (x,y) ) where the bottom‐left cell is ( (1,1) ) and the top–right cell is ( (n,n) ). The column index increases from left to right and the row index increases from bottom to top. Initially, every cell is set to 0, and then the main diagonal ( (i,i) ) for ( 1\le i\le n ) is filled with ( a_i ) respectively.

2. Repeatedly, for every ( 2\times 2 ) submatrix (with cells labeled in reading order, i.e., top–left, top–right, bottom–left, bottom–right as ( a,b,c,d )) whose top–right and bottom–left entries (i.e. ( b ) and ( c )) are nonzero, perform the following update:

   [ \begin{array}{ll} \text{If } a=0 \text{ and } d=0, & \quad \text{set } a=d=b+c. \[8pt] \text{If } a=0 \text{ and } d\neq 0, & \quad \text{set } a=b+c-d. \[8pt] \text{If } a\neq 0 \text{ and } d=0, & \quad \text{set } d=b+c-a. \end{array} ]

   These operations are applied in some order until every cell in the table is filled with a positive integer.

3. Finally, every number ( a_{ij} ) in the table is replaced by ( \lfloor a_{ij}/k \rfloor ), where ( \lfloor x \rfloor ) denotes the greatest integer not exceeding ( x ).

After constructing the table, you are given ( q ) queries. For each query you are given two coordinates ( (x_1,y_1) ) and ( (x_2,y_2) ) (with ( (x_1,y_1) ) being the bottom–left and ( (x_2,y_2) ) the top–right of a submatrix), and you need to output the sum of all numbers in that submatrix modulo ( 998244353 ).

It can be proven that the final table is uniquely determined by the initial diagonal. In fact, one may show that for every cell ( (i,j) ) the final value is given by

[ F(i,j)= \sum_{r=\min(i,j)}^{\max(i,j)} a_r, ]

and hence after the final step, the value becomes

[ G(i,j)= \left\lfloor \frac{1}{k} \sum_{r=\min(i,j)}^{\max(i,j)} a_r \right\rfloor. ]

Your task is to answer the ( q ) queries efficiently.

inputFormat

The first line contains two positive integers ( n ) and ( k ) (the size of the sequence and the divisor).
The second line contains ( n ) positive integers ( a_1,a_2,\dots,a_n ).
The third line contains a positive integer ( q ), the number of queries.
Each of the next ( q ) lines contains four integers ( x_1,y_1,x_2,y_2 ) representing a query, where ( (x_1,y_1) ) is the bottom–left and ( (x_2,y_2) ) is the top–right coordinate of the submatrix.

outputFormat

For each query, output one integer—the sum of all values in the corresponding submatrix (after taking floor division by ( k )) modulo ( 998244353 ).

sample

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

34
16
15