Mosaic Coloring Queries

Salma wants to color a mosaic made up of $N \times N$ square tiles. There are a total of $N^2$ tiles, each with dimensions $1 \times 1$, and initially none of them are colored. The rows are numbered from $0$ to $N-1$ from top to bottom and the columns from $0$ to $N-1$ from left to right. The tile at row $i$ and column $j$ is denoted by $(i,j)$. Each tile is painted either white (denoted by $0$) or black (denoted by $1$).

Initially, Salma selects two binary arrays $X$ and $Y$, each of length $N$, with the condition that $X[0]=Y[0]$. She paints the top row (row $0$) according to the array $X$, setting the color of tile $(0,j)$ to $X[j]$ for $0\le j<N$. Similarly, she paints the leftmost column (column $0$) according to the array $Y$, so that the color of tile $(i,0)$ is $Y[i]$ for $0\le i<N$.

Then, she repeatedly colors an uncolored tile $(i,j)$ for which both the tile directly above $(i-1,j)$ and the tile directly to the left $(i,j-1)$ are already colored. The rule is as follows: [ \text{color}(i,j)=\begin{cases} 1, & \text{if } \text{color}(i-1,j)=0 \text{ and } \text{color}(i,j-1)=0,\ 0, & \text{otherwise.} \end{cases} ] It can be proven that the final coloring of the mosaic is independent of the order in which Salma colors the tiles.

Yasmin is curious about the final colors and asks $Q$ queries. In the $k$-th query ($0\le k<Q$), a subrectangle of the mosaic is specified by its top row $T[k]$, bottom row $B[k]$, left column $L[k]$, and right column $R[k]$, where $0\le T[k]\le B[k]<N$ and $0\le L[k]\le R[k]<N$. The answer to the query is the number of black tiles (tiles with color $1$) contained in the specified subrectangle.

Your task is to implement a function that efficiently answers these queries.

inputFormat

Input is given as follows:

• The first line contains two integers $N$ and $Q$, where $N$ is the size of the mosaic and $Q$ is the number of queries.
• The second line contains $N$ integers (each $0$ or $1$) representing the array $X$, which gives the colors for the top row.
• The third line contains $N$ integers (each $0$ or $1$) representing the array $Y$, which gives the colors for the left column ($X[0]=Y[0]$).
• Then $Q$ lines follow; each line contains four integers $T[k]$, $B[k]$, $L[k]$, and $R[k]$, defining a query.

outputFormat

For each query, output the number of black tiles in the specified subrectangle. Each answer should be printed on a separate line.

sample

3 3
0 1 0
0 0 1
0 1 0 1
1 2 1 2
0 2 0 2

1
1
3