Ваші Шляхи
Ви живете в невеликому, добре спланованому прямокутному місті на Пхукеті. Розмір центральної частини міста становить 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 рядків.