Задача №112091. Шустрая черепашка
Пафнутий и его друзья — большие любители разнообразных настольных игр. Особенно им нравятся игры, требующие как можно быстрее производить в уме непростые вычисления, поэтому абсолютным хитом их вечерних посиделок в аудиториях НУОП (Неизвестного университета олимпиадного программирования) стала игра «Шустрая черепашка». В комплект игры входят:
* Клетчатое поле из \(N\) рядов по \(M\) клеток. Каждая клетка поля либо свободна, либо блокирована для перемещения.
* Q игровых карточек. Каждая карточка содержит описание множества стартовых клеток A, множества дополнительно блокируемых клеток B и множества конечных клеток C. Множества A, B и C непусты, попарно не пересекаются и состоят из свободных клеток.
* Маленькая фишка в форме черепашки.
Правила игры очень просты. Игроки последовательно разыгрывают игровые карточки. Как только открывается очередная карточка, игрокам необходимо вычислить, сколько существует хороших троек клеток (\(a_i b_j c_k)\), где \(a_i \in A\), \(b_j \in B\), \(c_k \in C\). Тройка клеток называется хорошей, если можно провести черепашку из стартовой клетки ai в конечную клетку \(c_k\), не посещая при этом клетку \(b_j\). На перемещение черепашки наложено три условия:
1. Черепашка имеет право перемещаться только вниз и вправо в пределах поля.
2. Находиться на блокированных клетках запрещено
3. Клетка \(b_j\) также блокируется для перемещения
Так как таблицу с правильными ответами создатели не включили в комплект, в пылу игры постоянно возникают споры о правильности того или иного значения. Для установления истины ребята попросили вас посчитать ответы для данного комплекта.
Первая строка входного файла содержит два целых числа \(N\) и \(M\) (1 ≤ \(N\), \(M\) ≤ 150) — количество строк и столбцов игрового поля.
Следующие \(N\) строк по \(M\) символов описывают игровое поле в порядке следования сверху вниз, слева направо. Символ ‘.’ соответствует свободной клетке, а ‘#’ — занятой. Строки нумеруются от 1 до \(N\), столбцы — от 1 до \(M\)
Следующая строка содержит целое число \(Q\) (1 ≤ \(Q\) ≤ 100 000) — количество игровых карточек.
Далее следуют \(Q\) блоков, описывающих карточки. Каждый блок состоит из трех строк, описывающих множества \(A\), \(B\) и \(C\) соответственно. Первое число описания определяет размер соответствующего множества, после чего перечисляются его клетки. Каждая клетка задается двумя числами — номером строки и номером столбца. Все клетки в описании различны. Смотрите комментарии к примеру для лучшего понимания формата входных данных.
Гарантируется, что все множества непусты, все клетки всех множеств являются свободными и никакая клетка не принадлежит более чем одному множеству из какой-то карточки.
В выходной файл выведите ровно \(Q\) чисел по одному на строке — правильные ответы на карточки в порядке их следования во входном файле.
В приведенном примере игровой комплект содержит две карточки
Во всех тройках первой карточки черепашка стартует в верхнем левом углу и финиширует в правом нижнем. Несложно видеть, что это возможно сделать, только если из трех элементов множества \(B\) блокируется первая клетка второй строки, то есть хорошей тройкой является \((1, 1) - (2, 1) - (5, 6)\).
На второй карточке хорошими являются тройки: \((1, 2) - (3, 1) - (5, 6)\), \((2, 1) - (3, 1) - (5, 6)\), \((2, 1) - (3, 3) - (5, 1)\).
Тесты к этой задаче состоят из четырех групп
0. Тест 1. Тест из условия, оценивается в ноль баллов.
1. Тесты 2–18. В тестах этой группы \(N\) ≤ 100, \(Q\)total ≤ 1 000. Эта группа оценивается в 30 баллов. Баллы начисляются только при прохождении всех тестов группы.
2. Тесты 19–32. В тестах этой группы \(N\) ≤ 100, \(Q\)total ≤ 1 000 000. Эта группа оценивается в 30 баллов. Баллы начисляются только при прохождении всех тестов группы. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из первой группы.
3. В тестах этой группы дополнительные ограничения отсутствуют, однако гарантируется, что \(N\) и \(Q\)total будут равномерно возрастать с номером теста. Эта группа оценивается в 40 баллов. Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура, причем только в случае прохождения всех тестов из первой и второй групп. Тесты в этой группе оцениваются независимо.
5 6 ..##.. ....#. .#.#.. .#...# ..#... 2 1 1 1 3 2 1 2 3 4 3 1 5 6 2 1 2 2 1 2 3 1 3 3 2 5 1 5 6
1 3