E. Казак Вус и поле
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Казака Вуса есть поле с размерами $$$n \times m$$$, которое состоит из «0» и «1». Он строит из этого поля бесконечное поле. Это он делает так:

  1. Берет текущее поле и находит для него новое инвертированное поле. Другими словами, в новом поле будет «1» там, где был «0», а «0» там, где был «1».
  2. К начальному полю приписывает справа инвертированное поле.
  3. К начальному полю приписывает снизу инвертированное поле.
  4. К начальному полю приписывает справа снизу начальное поле.
  5. Повторяет все это.

Например, если начальное поле было таким:

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

После первой итерации оно станет таким:

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

После второй итерации оно станет таким:

$$$\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}$$$

И так далее...

Пронумеруем строки сверху вниз от $$$1$$$ до бесконечности, а столбцы слева направо от $$$1$$$ до бесконечности. Назовем подматрицей $$$(x_1, y_1, x_2, y_2)$$$ все числа, которые имеют координаты $$$(x, y)$$$, такие что $$$x_1 \leq x \leq x_2$$$ и $$$y_1 \leq y \leq y_2$$$.

Казаку иногда нужно находить сумму всех чисел на подматрицах. Так как он очень занят сейчас, помогите ему найти ответы!

Входные данные

Первая строка содержит три целых числа $$$n$$$, $$$m$$$, $$$q$$$ ($$$1 \leq n, m \leq 1\,000$$$, $$$1 \leq q \leq 10^5$$$) — размеры начальной матрицы и количество запросов.

Каждая из следующих $$$n$$$ строк содержит $$$m$$$ символов $$$c_{ij}$$$ ($$$0 \leq c_{ij} \leq 1$$$) — символы в матрице.

Каждая из следующих $$$q$$$ строк содержит четыре числа $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$ ($$$1 \leq x_1 \leq x_2 \leq 10^9$$$, $$$1 \leq y_1 \leq y_2 \leq 10^9$$$) — координаты верхней левой крайней точки и нижней правой, между которыми нужно найти сумму всех чисел.

Выходные данные

Для каждого запроса выведите ответ.

Примеры
Входные данные
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
Выходные данные
32
5
25
14
4
Входные данные
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
Выходные данные
6
3
98
13
22
15
3
Примечание

Первый пример объяснен в легенде.