1186_E. Vus the Cossack and a Field_5154
Vus the Cossack has a field with dimensions n × m, which consists of "0" and "1". He is building an infinite field from this field. He is doing this in this way:

  1. He takes the current field and finds a new inverted field. In other words, the new field will contain "1" only there, where "0" was in the current field, and "0" there, where "1" was.
  2. To the current field, he adds the inverted field to the right. 
  3. To the current field, he adds the inverted field to the bottom. 
  4. To the current field, he adds the current field to the bottom right. 
  5. He repeats it.



For example, if the initial field was:

\begin{matrix} 1 & 0 & \\\ 1 & 1 & \\\ \end{matrix} 

After the first iteration, the field will be like this:

\begin{matrix} 1 & 0 & 0 & 1 \\\ 1 & 1 & 0 & 0 \\\ 0 & 1 & 1 & 0 \\\ 0 & 0 & 1 & 1 \\\ \end{matrix} 

After the second iteration, the field will be like this:

\begin{matrix} 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\\ 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\\ 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\\ 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\\ 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\\ 1 & 1 & 0& 0 & 0 & 0 & 1 & 1 \\\ \end{matrix} 

And so on...

Let's numerate lines from top to bottom from 1 to infinity, and columns from left to right from 1 to infinity. We call the submatrix (x_1, y_1, x_2, y_2) all numbers that have coordinates (x, y) such that x_1 ≤ x ≤ x_2 and y_1 ≤ y ≤ y_2.

The Cossack needs sometimes to find the sum of all the numbers in submatrices. Since he is pretty busy right now, he is asking you to find the answers!

Input

The first line contains three integers n, m, q (1 ≤ n, m ≤ 1 000, 1 ≤ q ≤ 10^5) — the dimensions of the initial matrix and the number of queries.

Each of the next n lines contains m characters c_{ij} (0 ≤ c_{ij} ≤ 1) — the characters in the matrix.

Each of the next q lines contains four integers x_1, y_1, x_2, y_2 (1 ≤ x_1 ≤ x_2 ≤ 10^9, 1 ≤ y_1 ≤ y_2 ≤ 10^9) — the coordinates of the upper left cell and bottom right cell, between which you need to find the sum of all numbers.

Output

For each query, print the answer.

Examples

Input


2 2 5
10
11
1 1 8 8
2 4 5 6
1 2 7 8
3 3 6 8
5 6 7 8


Output


32
5
25
14
4


Input


2 3 7
100
101
4 12 5 17
5 4 9 4
1 4 13 18
12 1 14 9
3 10 7 18
3 15 12 17
8 6 8 12


Output


6
3
98
13
22
15
3

Note

The first example is explained in the legend.
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author AnandOza
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        EVusTheCossackAndAField solver = new EVusTheCossackAndAField();
        solver.solve(1, in, out);
        out.close();
    }

    static class EVusTheCossackAndAField {
        int n;
        int m;
        int[][] sum;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            n = 2 * in.nextInt();
            m = 2 * in.nextInt();
            int q = in.nextInt();

            int[][] orig = new int[n][m];
            for (int i = 0; i < n / 2; i++) {
                char[] row = in.next().toCharArray();
                for (int j = 0; j < m / 2; j++) {
                    orig[i][j] = orig[i + n / 2][j + m / 2] = row[j] == '1' ? 1 : 0;
                    orig[i + n / 2][j] = orig[i][j + m / 2] = 1 - orig[i][j];
                }
            }

            sum = new int[n + 1][m + 1];
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + orig[i - 1][j - 1];
                }
            }

            for (int i = 0; i < q; i++) {
                int x1 = in.nextInt() - 1;
                int y1 = in.nextInt() - 1;
                int x2 = in.nextInt();
                int y2 = in.nextInt();

                long answer = f(x2, y2) - f(x1, y2) - f(x2, y1) + f(x1, y1);

                out.println(answer);
            }
        }

        private long f(int x, int y) {
            long a = x / n;
            long b = y / m;
            x -= a * n;
            y -= b * m;

            long simpleArea = a * b * n * m + a * n * y + b * m * x;
            long answer = simpleArea / 2;

            long small = sum[x][y];
            boolean inverted = p(a, b);
            answer += !inverted ? small : (long) x * y - small;

            return answer;
        }

        private static boolean p(long i, long j) {
            return p((int) i) ^ p((int) j);
        }

        private static boolean p(int i) {
            return Integer.bitCount(i) % 2 == 1;
        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}

