Безграничные Коробки
Помните художника Пира с финала ACM ICPC 2008 года? (Кроме художника Пира, эта задача на самом деле не имеет никакого отношения к задаче с финала, так что не беспокойтесь, если вы там не были или не читали ту задачу раньше. На самом деле, мы гарантируем, что знание упомянутой задачи никак не поможет вам решить эту.) Пир был одним из изобретателей монохромии, что означает, что каждая из его картин имеет один цвет, но в разных оттенках. Он также верил в использование простых геометрических форм. Несколько месяцев назад Пир рисовал треугольники на холсте снаружи внутрь. Теперь, когда треугольники вышли из моды, а квадраты вошли, его новые картины используют концентрические квадраты и создаются изнутри наружу! Пир начинает рисовать на прямоугольном холсте, разделенном на идеальную квадратную сетку. Он выбирает несколько отдельных ячеек сетки, чтобы они служили центральными семенами, и закрашивает их самым темным оттенком. Из каждой из семенных квадратов Пир рисует больший квадрат, используя более светлый оттенок, чтобы окружить его, и повторяет с большими квадратами, чтобы окружить те, пока весь холст не будет покрыт. Каждый квадрат ровно на одну ячейку сетки больше и на один оттенок светлее, чем тот, который он окружает. Когда квадраты перекрываются, ячейка сетки всегда заполняется более темным оттенком. После того как Пир решает, где разместить начальные квадраты, единственная сложная часть в создании этих картин — решить, сколько различных оттенков цвета ему понадобится. Чтобы помочь Пиру, вы должны написать программу, которая вычисляет количество оттенков, необходимых для такой картины, учитывая размер холста и расположение семенных квадратов.
Входные данные
Входной файл теста будет содержать несколько случаев. Каждый тестовый случай начинается с одной строки, содержащей три целых числа, m, n и s, разделенных пробелами. Холст содержит ровно m×n ячеек сетки (1 <= m, n <= 1000), пронумерованных 1, ..., m вертикально и 1, ..., n горизонтально. Пир начинает рисовать с s (1 <= s <= 1000) семенных ячеек, описанных в следующих s строках текста, каждая с двумя целыми числами, ri и ci (1 <= ri <= m, 1 <= ci <= n), описывающими соответствующую строку и столбец сетки каждого семенного квадрата. Все семенные квадраты находятся в пределах границ холста. Пустая строка разделяет входные тестовые случаи, как показано в примере входных данных ниже. Одна строка с числами "0 0 0" отмечает конец ввода; не обрабатывайте этот случай.
Выходные данные
Для каждого тестового случая ваша программа должна вывести одно целое число в одной строке: количество различных оттенков, необходимых для описанной картины.