시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
8 초 | 256 MB | 0 | 0 | 0 | 0.000% |
По прямоугольному клеточному полю, состоящему из n столбцов и m строк, путешествует робот. Он может начать свое путешествие в любой клетке первой строки. Далее он может совершить некоторое (возможно, нулевое) количество ходов. Пусть робот стоит в столбце x и строке y, тогда за один ход он может перейти либо в клетку (x + 1, y + 1), либо в клетку (x - 1, y + 1). Конечно, робот не может выходить за границы поля.
Путешествие робота осложняется тем, что на поле есть прямоугольные преграды, стороны которых параллельны сторонам поля. Робот не может пойти в клетку, которая покрывается преградой. Никакие две преграды не пересекаются, но могут касаться.
Вам необходимо посчитать количество клеток, в которые может попасть робот.
В первой строке задано число T — количество тестов. Далее следует описание T тестов.
В первой строке теста дано два целых числа n и m (1 ≤ n, m ≤ 109) — количество столбцов и строк на поле. В следующей строке задано одно целое число k (1 ≤ k ≤ 105) — количество преград на поле. В следующих k строках задано описание преград. Каждая такая строка состоит из четырех целых чисел x1, y1, x2, y2, обозначающих координаты противоположных углов преграды (1 ≤ x1 ≤ x2 ≤ n, 2 ≤ y1 ≤ y2 ≤ m). Гарантируется, что преграды не пересекаются.
Общее количество преград во входном файле не превышает 105.
Для каждого из T тестовых примеров выведите одно число — количество клеток, которые может посетить робот.
1 5 7 3 2 2 4 2 1 3 1 5 2 5 3 6
14
Contest > Russian Code Cup > 2014 > RCC 2014 Final Round F번