Ваши Пути
Вы живете в небольшом, хорошо спланированном прямоугольном городе на Пхукете. Размер центральной части города составляет H километров × W километров. Эта центральная часть разделена на HW единичных блоков, каждый размером 1×1 км^2. В городе есть H+1 улиц, которые идут с запада на восток, и W+1 проспектов, которые идут с севера на юг. Центральная часть может быть представлена как прямоугольник на плоскости, как показано ниже.
Рисунок 1. Центральная часть города, где H = 3, и W = 6.
Каждое пересечение можно идентифицировать по его координатам на плоскости. Например, на рисунке выше нижний левый угол — это пересечение (0, 0), а верхний правый угол — это пересечение (6, 3).
Ваш дом находится в нижнем левом углу (т.е. пересечение (0, 0)), и вы хотите добраться до университета, который находится в верхнем правом углу (т.е. пересечение (W, H)). Более того, вы хотите добраться до университета, не тратя лишних усилий, поэтому вы хотите двигаться только с запада на восток и с юга на север. В приведенном выше примере существует 84 способа добраться до университета.
Вы планируете ходить в университет в течение K дней. Ситуация усложняется тем, что каждое утро город перекрывает части улиц и проспектов для уборки. Перекрытия организованы так, что невозможно добраться до перекрытых частей улиц или проспектов из других перекрытых частей, используя пути, содержащие только движения с запада на восток и с юга на север.
Тем не менее, вы хотите добраться до университета, используя ту же стратегию движения с запада на восток и с юга на север. Вам нужно узнать, сколько существует способов добраться до университета для каждого дня, следуя этой стратегии. Поскольку число может быть очень большим, результат необходимо представить по модулю 2552.
Входные данные
Первая строка содержит целое число T, количество тестов (1 ≤ T ≤ 5). Каждый тест представлен в следующем формате.
Первая строка каждого теста содержит 3 целых числа: W, H и K (1 ≤ W ≤ 1000, 1 ≤ H ≤ 1000, 1 ≤ K ≤ 10000). W и H определяют размер центральной части. K обозначает количество дней, в которые вы хотите ходить в университет.
Следующие K строк описывают информацию о перекрытых частях улиц и проспектов. Более конкретно, строка 1+i, для 1 ≤ i ≤ K, начинается с целого числа Q_i (1 ≤ Q_i ≤ 100), обозначающего количество перекрытых частей. Затем следуют Q_i наборов из 4 целых чисел, описывающих перекрытые части. Каждая часть описывается 4 целыми числами, A, B, C и D (0 ≤ A ≤ C ≤ W, 0 ≤ B ≤ D ≤ H), что означает, что часть, соединяющая пересечения (A, B) и (C, D), перекрыта. Гарантируется, что эта часть является допустимой частью улиц или проспектов, также C-A ≤ 1, и D-B ≤ 1, т.е. часть длиной 1 км.
Выходные данные
Для каждого теста, для каждого дня, ваша программа должна вывести количество способов добраться до университета по модулю 2552 в отдельной строке. То есть вывод для каждого теста должен содержать K строк.