Безмежні Коробки#301
Пам'ятаєте художника Піра з фіналу ACM ICPC 2008 року? (Крім художника Піра, ця задача насправді не має нічого спільного з задачею з фіналу, тому не переймайтеся, якщо ви там не були чи не читали цю задачу раніше. Насправді будь-які знання про згадану задачу не допоможуть вам у вирішенні цієї.) Пір був одним із винахідників монохромії, тобто кожна з його картин має один колір, але в різних відтінках. Він також вірив у використання простих геометричних форм. Кілька місяців тому Пір малював трикутники на полотні із зовні всередину. Зараз трикутники вийшли з моди, а квадрати увійшли, і його нові картини створюються з концентричних квадратів — зсередини назовні! Пір починає на прямокутному полотні, розділеному на ідеальну квадратну сітку. Він обирає декілька окремих клітинок як центральні зерна і фарбує їх найтемнішим відтінком. Для кожного початкового квадрата Пір малює більший квадрат світлішим відтінком, щоб його охопити, і повторює, доки все полотно не буде вкрите. Кожен квадрат рівно на одну клітинку більше й на один відтінок світліший за той, який охоплює. Коли квадрати перекриваються, клітинка завжди заповнюється більш темним відтінком. Коли місця початкових квадратів обрано, залишається визначити, скільки різних відтінків знадобиться. Допоможіть Піру: напишіть програму, яка, знаючи розміри полотна та розташування початкових клітинок, визначає кількість потрібних відтінків.
Вхід складається з декількох тестових випадків. Кожен випадок починається із рядка з трьома цілими числами , , через пробіл. Полотно має m \times n клітинок (1 \leq m, n \leq 1000), пронумерованих 1, \ldots, m вертикально та 1, \ldots, n горизонтально. Пір починає з початкових клітинок (1 \leq s \leq 1000), які задаються наступними рядками по два числа r_i, c_i (1 \leq r_i \leq m, 1 \leq c_i \leq n) — номер рядка і стовпця відповідної початкової клітинки. Всі початкові клітинки всередині полотна. Порожній рядок відокремлює тестові випадки, як показано у прикладі. Рядок "0 0 0" означає кінець вводу; цей випадок не розглядайте.
Для кожного тестового випадку програма повинна вивести одне ціле число у рядок — кількість потрібних відтінків описаної картини.
Приклад 1