Безмежні Коробки
Чи пам'ятаєте ви художника Пера з фіналу 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" позначає кінець вводу; не обробляйте цей випадок. Вихід
Для кожного тестового випадку ваша програма повинна вивести одне ціле число в одному рядку: кількість різних відтінків, необхідних для описаної картини.