| Codeforces Round 219 (Div. 1) |
|---|
| Закончено |
Дана таблица размера n × m, в каждой ячейке которой записано целое число: ноль или единица. Обозначим ячейку в i-ой строке и j-ом столбце как (i, j).
Определим «прямоугольник» четверкой целых чисел a, b, c, d (1 ≤ a ≤ c ≤ n; 1 ≤ b ≤ d ≤ m). Прямоугольник задает множество ячеек таблицы {(x, y) : a ≤ x ≤ c, b ≤ y ≤ d}. Определим «хороший прямоугольник» как прямоугольник, включающий только ячейки с нулями.
Вам надо ответить на следующие q запросов: посчитать количество хороших прямоугольников, у которых все ячейки содержатся в данном прямоугольнике.
В первой строке записано три целых числа: n, m и q (1 ≤ n, m ≤ 40, 1 ≤ q ≤ 3·105). Каждая из следующих n строк содержит m символов — таблицу. Мы можем считать, что строки таблицы пронумерованы сверху вниз, а столбцы — слева направо. И строки, и столбцы пронумерованы, начиная с единицы.
Каждая из следующих q строк содержит по запросу — четыре целых числа, описывающих текущий прямоугольник, a, b, c, d (1 ≤ a ≤ c ≤ n; 1 ≤ b ≤ d ≤ m).
Для каждого запроса выведите ответ — единственное целое число на отдельной строке.
5 5 5
00101
00000
00001
01000
00001
1 2 2 4
4 5 4 5
1 2 5 2
2 2 4 5
4 2 5 3
10
1
7
34
5
4 7 5
0000100
0000010
0011000
0000000
1 7 2 7
3 1 3 1
2 3 4 5
1 2 2 7
2 2 4 7
3
1
16
27
52
В первом примере дана квадратная таблицы размера 5 × 5, а первый, второй и третий запросы представлены в следующем рисунке.
- В первом запросе есть 10 хороших прямоугольников, пять размера 1 × 1, два — 2 × 1, два — 1 × 2 и один — 1 × 3.
- Во втором запросе есть всего один хороший прямоугольник размера 1 × 1.
- В третьем запросе есть 7 хороших прямоугольников, четыре размера 1 × 1, два размера 2 × 1 и один размера 3 × 1.
