Matrix Sum Query Modulo

You are given a matrix \(a\) with \(n\) rows and \(m\) columns. You are then given \(q\) queries. Each query provides two pairs of indices \((u, v)\) and \((x, y)\) representing the top-left and bottom-right corners of a submatrix respectively.

Your task is to compute the following:

[ \left(\sum_{i=u}^{x} \sum_{j=v}^{y} a_{i,j}\right) \bmod 2^{64} ]

In other words, for each query, compute the sum of all elements inside the rectangle defined by the top-left corner \((u,v)\) and bottom-right corner \((x,y)\), and then take the result modulo \(2^{64}\).

inputFormat

The first line contains three integers \(n\), \(m\) and \(q\) where \(n\) and \(m\) denote the number of rows and columns of the matrix, and \(q\) is the number of queries.

The next \(n\) lines each contain \(m\) integers, representing the matrix \(a\). The \(j\)-th integer in the \(i\)-th line is \(a_{i,j}\).

Then \(q\) lines follow, each containing four integers \(u\), \(v\), \(x\) and \(y\), representing a query. It is guaranteed that \(1 \leq u \leq x \leq n\) and \(1 \leq v \leq y \leq m\).

outputFormat

For each query, output a single line containing the sum of the specified submatrix modulo \(2^{64}\).

sample

3 3 2
1 2 3
4 5 6
7 8 9
1 1 2 2
2 2 3 3

12
28