Background

Meili bought a special piece of patterned paper. The pattern on the whole paper can be seen as being formed by infinitely repeating a smaller basic pattern horizontally and vertically. Also, this basic pattern is partially transparent and partially opaque.

So, if you place this paper over a book, some characters can be seen while others cannot.

Lianzi suddenly had an idea: if she makes a very, very large table of numbers and covers it with the patterned paper, many numbers will be blocked. What is the sum of the numbers that are not blocked?

Problem Description

In fact, their problem can be converted into the following.

You are given a normal matrix $A$ with $n$ rows and $m$ columns, and a $01$ matrix $B$ with $r$ rows and $c$ columns. In $B$, cells with value $1$ are black and opaque, and cells with value $0$ are transparent.

Using matrix $B$, generate an infinite matrix $M$ by repeating $B$ cyclically:

Now there are $q$ queries. For each query, align the top-left corner of matrix $M$ with $(x_1,y_1)$. At this time, some elements in $A$ will be blocked, and others will be visible.

You need to find, in the submatrix of $A$ with top-left corner $(x_1,y_1)$ and bottom-right corner $(x_2,y_2)$, the sum of the elements that are visible. Take the result modulo $998{,}244{,}353$.

In the example above, $(x_1,y_1)=(2,3)$ and $(x_2,y_2)=(4,7)$. The sum of visible elements is $a_{2,3}+a_{2,5}+a_{2,6}+a_{3,5}+a_{4,3}+a_{4,5}+a_{4,6}$.

Formal Statement

You are given a normal matrix $A$ with $n$ rows and $m$ columns, and a $01$ matrix $B$ with $r$ rows and $c$ columns. Using matrix $B$, generate an infinite matrix $M$:

$$M= \begin{pmatrix} B & B & B &\cdots \\ B & B & B &\cdots \\ B & B & B &\cdots \\ \vdots &\vdots &\vdots & \end{pmatrix} =\begin{pmatrix} b_{1,1} & b_{1,2} & \cdots & b_{1,c} & b_{1,1} & b_{1,2} & \cdots & b_{1,c} & b_{1,1} & \cdots \\ b_{2,1} & b_{2,2} & \cdots & b_{2,c} & b_{2,1} & b_{2,2} & \cdots & b_{2,c} & b_{2,1} & \cdots \\ \vdots & \vdots & & \vdots & \vdots & \vdots & & \vdots & \vdots & \\ b_{r,1} & b_{r,2} & \cdots & b_{r,c} & b_{r,1} & b_{r,2} & \cdots & b_{r,c} & b_{r,1} & \cdots \\ b_{1,1} & b_{1,2} & \cdots & b_{1,c} & b_{1,1} & b_{1,2} & \cdots & b_{1,c} & b_{1,1} & \cdots \\ b_{2,1} & b_{2,2} & \cdots & b_{2,c} & b_{2,1} & b_{2,2} & \cdots & b_{2,c} & b_{2,1} & \cdots \\ \vdots & \vdots & & \vdots & \vdots & \vdots & & \vdots & \vdots & \\ b_{r,1} & b_{r,2} & \cdots & b_{r,c} & b_{r,1} & b_{r,2} & \cdots & b_{r,c} & b_{r,1} & \cdots \\ \vdots & \vdots & & \vdots & \vdots & \vdots & & \vdots & \vdots & \\ \end{pmatrix}$$

Now there are $q$ queries. Each query gives the top-left coordinate $(x_1,y_1)$ and the bottom-right coordinate $(x_2,y_2)$ of a submatrix. You need to compute:

$$S=\left(\sum_{i=x_1}^{x_2}\sum_{j=y_1}^{y_2}a_{i,j}\times [M_{i-x_1+1,j-y_1+1}=0] \right)\bmod 998{,}244{,}353$$

Here $[P]$ denotes the Iverson bracket. If $P$ is true, then $[P]=1$, otherwise $[P]=0$.

Input Format

• The first line contains two positive integers $n,m$, describing the size of matrix $A$.
• The next $n$ lines each contain $m$ non-negative integers, describing the elements $a_{i,j}$ in $A$.
• The next line contains two positive integers $r,c$, describing the size of matrix $B$.
• The next $r$ lines each contain $c$ non-negative integers, describing the elements $b_{i,j}$ in $B$.
• The next line contains a positive integer $q$, the number of queries.
• The next $q$ lines each contain four positive integers $x_1,y_1,x_2,y_2$, describing a query. It is guaranteed that $x_1\le x_2$ and $y_1\le y_2$.

Output Format

• Output $q$ lines in total. Each line prints the answer for that query.

3 4
1 2 3 4
5 6 7 8
9 10 11 12
2 2
1 0
0 1
2
1 1 3 4
1 2 3 3

40
20

4 4
1 3 2 4
5 4 2 3
4 1 2 3
3 4 4 3
1 3
1 0 0
3
1 1 3 4
2 2 4 4
1 2 3 2

14
17
0

Hint

Explanation for Sample 1

• For the first query, the result is $2+4+5+7+10+12=40$.
• For the second query, the result is $3+6+11=20$.

Constraints and Notes

For all data, it is guaranteed that $1\le n,m\le 10^3$, $1\le q\le 10^4$, $1\le r,c\le 50$, $0\le a_{i,j}<998{,}244{,}353$, and $b_{i,j}\in\{0,1\}$.

Translated by ChatGPT 5