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

Автор:А. Усманов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

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

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

Далее в Q строках содержится по четыре числа в каждой. xi, yi, ui, vi — описание i-й прямоугольной области карты. xi, yi — координаты левого верхнего угла прямоугольника, ui, vi — координаты правого нижнего угла прямоугольника.

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

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

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

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

Ограничения

1 ≤ H, W ≤ 109

1 ≤ N, M ≤ 103

1 ≤ Q ≤ 105

1 ≤ xi ≤ ui ≤ H, 1 ≤ yi ≤ vi ≤ W

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

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи
H, Wxi, yi, ui, viQ
1121 ≤ H, W ≤ 103xi = ui, yi = vi1 ≤ Q ≤ 105
281 ≤ H, W ≤ 1031 ≤ Q ≤ 102
3141 ≤ H, W ≤ 1031 ≤ Q ≤ 1051-2
4111 ≤ H, W ≤ 109xi = ui, yi = vi1 ≤ Q ≤ 1051
591 ≤ H, W ≤ 109(ui − xi + 1)(vi − yi + 1) ≤ 106Q = 1
6161 ≤ H, W ≤ 109(ui − xi + 1)(vi − yi + 1) ≤ 1061 ≤ Q ≤ 1022, 5
7171 ≤ H, W ≤ 1091 ≤ Q ≤ 1022, 5-6
8131 ≤ H, W ≤ 1091 ≤ Q ≤ 1051-7

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

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
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
2
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
3
640 896
5 7
.......
.......
..X....
.......
.......
2
543 782 543 782
543 783 543 783
1
0
4
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
5
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

Разбор

Подзадача Дополнительные ограничения Решение
H, Wxi, yi, ui, viQ
11 ≤ H, W ≤ 103xi = ui, yi = vi1 ≤ Q ≤ 105O(H W + Q) Сгенерировать исходную карту
21 ≤ H, W ≤ 1031 ≤ Q ≤ 102O(H W + Q dx dy) Сгенерировать исходную карту и пройтись по прямоугольникам
31 ≤ H, W ≤ 1031 ≤ Q ≤ 105O(H W + Q) Сгенерировать исходную карту + Частичные суммы
41 ≤ H, W ≤ 109xi = ui, yi = vi1 ≤ Q ≤ 105O(Q(log H + log W)) или O(Q) За логарифм или за единицу находить клетку
51 ≤ H, W ≤ 109(ui − xi + 1)(vi − yi + 1) ≤ 106Q = 1O(dx dy(log H + log W)) или O(dx dy) Каждую клетку прямоугольника по отдельности за единицу или за логарифм
61 ≤ H, W ≤ 109(ui − xi + 1)(vi − yi + 1) ≤ 1061 ≤ Q ≤ 102O(Q dx dy) Каждую клетку прямоугольников по отдельности за единицу
71 ≤ H, W ≤ 1091 ≤ Q ≤ 102O(Q log H log W) Двумерное дерево отрезков + Формулы
81 ≤ H, W ≤ 1091 ≤ Q ≤ 105O(Q) Формулы

0.101s 0.007s 13