Лимак — белый медвежонок, который очень любит играть. Недавно он получил прямоугольную таблицу, состоящую из h рядов и w столбцов. Каждая клетка этой таблицы либо пустая (обозначается '.'), либо занятая (обозначается '#'). Ряды нумеруются от 1 до h сверху вниз. Столбцы нумеруются от 1 до w слева направо.
Также у Лимака есть одна доминошка, которую он хочет поместить куда-нибудь в табличку. Доминошка займёт две соседние по стороне клетки, расположенные в одной строке или в одном столбце. Обе эти клетки должны быть пустыми и находиться внутри таблицы.
Лимаку нужно больше играть и веселиться, поэтому он рассмотрит некоторые запросы. В каждом запросе он выбирает некоторый прямоугольник и задаётся вопросом: а сколькими способами можно полностью поместить имеющуюся доминошку в выбранный прямоугольник?
Выходные данные
Выведите q чисел, i-е из которых соответствует количеству способов полностью расположить доминошку внутри i-го прямоугольника.
Примечание
Красная рамочка на рисунке ниже соответствует первому запросу в первом примере. Существует 4 способа расположить доминошку.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 8
....#..#
.#......
##.#....
##..#.##
........
4
1 1 2 3
4 1 4 1
1 2 4 5
2 5 5 8
|
4
0
10
15
|
|
2
|
7 39
.......................................
.###..###..#..###.....###..###..#..###.
...#..#.#..#..#.........#..#.#..#..#...
.###..#.#..#..###.....###..#.#..#..###.
.#....#.#..#....#.....#....#.#..#..#.#.
.###..###..#..###.....###..###..#..###.
.......................................
6
1 1 3 20
2 10 6 30
2 10 7 30
2 2 7 7
1 7 7 7
1 8 7 8
|
53
89
120
23
0
2
|