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

* Клетчатое поле из \(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\) соответственно. Первое число описания определяет размер соответствующего множества, после чего перечисляются его клетки. Каждая клетка задается двумя числами — номером строки и номером столбца. Все клетки в описании различны. Смотрите комментарии к примеру для лучшего понимания формата входных данных.

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

Автоботы отважились на штурм базы десептиконов. Из-за эффекта внезапности множество десептиконов полегло на месте, а остальные начали судорожно прятаться в бункеры, которые начали закрываться. Оптимус Прайм хочет добить как можно больше десептиконов. Для этого он решил использовать новую разработку автоботов — бомбу «Антибункер».

Принцип работы бомбы заключается в том, что ее можно кинуть внутрь бункера, а когда тот закроется — взорвать, и тогда она убьет всех, кто был внутри. Единственное ее неудобство заключается в том, что взрывается она неавтоматически. То есть Оптимусу, после того, как он кинет бомбу, придется ждать закрытия бункера, чтобы взорвать всех внутри, и лишь потом он сможет поехать дальше.

Оптимус собирается проехать мимо каждого бункера ровно один раз, посетив их в порядке возрастания номеров. К счастью, он знает, на какой минуте закроется каждый из бункеров, а также количество десептиконов в каждом из бункеров. Между бункерами Оптимус перемещается очень быстро — перемещение между любой парой бункеров занимает у него ровно одну минуту. Если он проехал бункер, он уже не сможет вернуться обратно.

Оптимус Прайм просит вас помочь ему рассчитать, какое наибольшее количество врагов он сможет убить, и в какие бункеры нужно бросить бомбу для этого.