30835번 - Шустрая черепашка 다국어

문제

Пафнутий и его друзья — большие любители разнообразных настольных игр. Особенно им нравятся игры, требующие как можно быстрее производить в уме непростые вычисления, поэтому абсолютным хитом их вечерних посиделок в аудиториях НУОП (Неизвестного университета олимпиадного программирования) стала игра «Шустрая черепашка». В комплект игры входят:

• Клетчатое поле из N рядов по M клеток. Каждая клетка поля либо свободна, либо блокирована для перемещения.
• Q игровых карточек. Каждая карточка содержит описание множества стартовых клеток A, множества дополнительно блокируемых клеток B и множества конечных клеток C. Множества A, B и C непусты, попарно не пересекаются и состоят из свободных клеток.
• Маленькая фишка в форме черепашки.

Правила игры очень просты. Игроки последовательно разыгрывают игровые карточки. Как только открывается очередная карточка, игрокам необходимо вычислить, сколько существует хороших троек клеток (a_i, b_j, c_k), где a_i ∈ A, b_j ∈ B, c_k ∈ C. Тройка клеток называется хорошей, если можно провести черепашку из стартовой клетки a_i в конечную клетку 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 соответственно. Первое число описания определяет размер соответствующего множества, после чего перечисляются его клетки. Каждая клетка задается двумя числами — номером строки и номером столбца. Все клетки в описании различны. Смотрите комментарии к примеру для лучшего понимания формата входных данных.

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

Гарантируется, что суммарный размер всех множеств на всех игровых карточках не превосходит 300 000, а именно: Σ(|A_i| + |B_i| + |C_i|) ≤ 300 000.

Дополнительно гарантируется, что суммарное количество всех троек (и хороших, и нет) по всем карточкам не превосходит 2 · 10⁷: Σ(|A_i| · |B_i| · |C_i|) = Q_total ≤ 2 · 10⁷.

출력

В выходной файл выведите ровно Q чисел по одному на строке — правильные ответы на карточки в порядке их следования во входном файле.

제한

노트

В приведенном примере игровой комплект содержит две карточки.

Во всех тройках первой карточки черепашка стартует в верхнем левом углу и финиширует в правом нижнем. Несложно видеть, что это возможно сделать, только если из трех элементов множества B блокируется первая клетка второй строки, то есть хорошей тройкой является (1, 1) − (2, 1) − (5, 6).

На второй карточке хорошими являются тройки: (1, 2)−(3, 1)−(5, 6), (2, 1)−(3, 1)−(5, 6), (2, 1) − (3, 1) − (5, 1).