Картограф звёздного неба работает с прямоугольной картой, разбитой на n строк и m столбцов. Для каждой клетки известно, есть ли в соответствующем участке неба светило: 1 означает, что светило есть, 0 — что участок пуст.

Необходимо обработать q запросов. Каждый запрос задаёт прямоугольный сектор карты четырьмя числами r1, c1, r2, c2, где:

• (r1, c1) — верхняя левая клетка сектора,
• (r2, c2) — нижняя правая клетка сектора.

Для каждого запроса требуется определить, сколько светил находится внутри указанного прямоугольного сектора, включая его границы.

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

Первая строка содержит три целых числа n, m, q — количество строк, количество столбцов и число запросов.

Следующие n строк содержат описание карты звёздного неба. Каждая из них состоит ровно из m символов 0 и 1 без пробелов.

Следующие q строк содержат по четыре целых числа r1, c1, r2, c2 — описание очередного прямоугольного сектора.

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

Для каждого запроса выведите в отдельной строке одно целое число — количество светил в соответствующем прямоугольном секторе карты.

Ограничения

• 1 <= n, m <= 1000
• 1 <= q <= 2 * 10^5
• 1 <= r1 <= r2 <= n
• 1 <= c1 <= c2 <= m

Примеры

Пример 1

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

1 1 5
0
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

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

0
0
0
0
0

Пример 2

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

2 3 8
101
010
1 1 1 1
1 2 1 3
2 1 2 3
1 1 2 3
1 2 2 2
1 3 2 3
2 2 2 2
1 1 2 1

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

1
1
1
3
1
1
1
1