Задача C. Карта сокровищ ≡

Условие

У Ильи имеется карта сокровищ размера H × W клеток.

Маленький брат Ильи — Никита, взял эту карту "поиграть". Игра заключалась в следующем: какое-то количество раз карта была сложена вдвое по вертикали или по горизонтали. Складывая карту по вертикали, Никита брал её за нижнюю сторону, по горизонтали — за правую сторону. После этого он соединял взятую сторону с противоположной стороной. При этом верхний левый угол карты всегда оставался неподвижным. Линия сгиба всегда проходила точно по границе между клетками. В итоге сложенная карта оказалось размером N × M клеток.

Но этого Никите было мало, он взял иглу и начал протыкать некоторые клетки насквозь, включая все слои, получившиеся в процессе складывания. Как только Илья увидел это, он немедленно остановил брата. Илья побоялся разворачивать карту, так как она может порваться.

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

Формат входного файла

Первая строка входного файла содержит два целых числа H и W — высоту и ширину исходной карты.

Вторая строка входного файла содержит два целых числа N и M — высоту и ширину сложенной карты.

Далее следует N строк по M символов в каждой — описание карты. Символом 'X' (ASCII 88) отмечается клетка, которую проткнул Никита, символом '.' (ASCII 46) отмечается нетронутая клетка.

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

Далее в Q строках содержится по четыре числа в каждой. x_i, y_i, u_i, v_i — описание i-й прямоугольной области карты. x_i, y_i — координаты левого верхнего угла прямоугольника, u_i, v_i — координаты правого нижнего угла прямоугольника.

Нумерация клеток по вертикали сверху вниз с 1 до H, нумерация клеток по горизонтали слева направо с 1 до W.

Гарантируется, что свёрнутая карта получена из исходной путём преобразований, описанных в задаче. То есть существую такие целые числа a и b, что N × 2^a = H и M × 2^b = W.

Формат выходного файла

Выходной файл должен содержать Q строк, каждая из которых содержит по одному целому числу. Число в строке номер i должно быть равно количеству отверстий, которые попали в i-ю прямоугольную область.

Ограничения

1 ≤ H, W ≤ 10⁹

1 ≤ N, M ≤ 10³

1 ≤ Q ≤ 10⁵

1 ≤ x_i ≤ u_i ≤ H, 1 ≤ y_i ≤ v_i ≤ W

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

Примеры тестов

6 6
3 3
...
.X.
...
5
2 2 2 2
5 2 5 2
2 5 2 5
5 5 5 5
6 6 6 6

1
1
1
1
0

4 3
2 3
X.X
.X.
12
1 1 1 1
1 2 1 2
1 3 1 3
2 1 2 1
2 2 2 2
2 3 2 3
3 1 3 1
3 2 3 2
3 3 3 3
4 1 4 1
4 2 4 2
4 3 4 3

1
0
1
0
1
0
0
1
0
1
0
1

640 896
5 7
.......
.......
..X....
.......
.......
2
543 782 543 782
543 783 543 783

1
0

10 10
5 5
XX...
.XXX.
...X.
.XX..
XX.X.
5
2 8 10 10
2 10 7 10
4 8 7 10
2 8 7 9
2 4 10 9

14
2
8
8
23

640 960
5 15
.XX..X..XXX..XX
X...X.X..X..X..
X...X.X..X...X.
X...XXX..X....X
.XX.X.X..X..XX.
2
1 1 640 960
333 121 634 932

253952
101336

Разбор