Дана таблица размера 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 запросов: посчитать количество хороших прямоугольников, у которых все ячейки содержатся в данном прямоугольнике.
Выходные данные
Для каждого запроса выведите ответ — единственное целое число на отдельной строке.
Примечание
В первом примере дана квадратная таблицы размера 5 × 5, а первый, второй и третий запросы представлены в следующем рисунке.
- В первом запросе есть 10 хороших прямоугольников, пять размера 1 × 1, два — 2 × 1, два — 1 × 2 и один — 1 × 3.
- Во втором запросе есть всего один хороший прямоугольник размера 1 × 1.
- В третьем запросе есть 7 хороших прямоугольников, четыре размера 1 × 1, два размера 2 × 1 и один размера 3 × 1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
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
|