Великая треугольная область (ВТО) представляет
собой прямоугольный треугольник. Его катеты имеют целые длины m и n и лежат на
осях координат. Нужно покрыть как можно большую часть территории ВТО
квадратными плитами размером 1×1. Плиты должны плотно прилегать одна к
другой и к катетам ВТО, не выходя за пределы области. Резать плиты нельзя.
Плиты поставляются
только контейнерами по p штук;
используется необходимый минимум контейнеров.
Требуется написать программу, которая вычислит, сколько плит из
последнего контейнера останется после покрытия ВТО.
Технические требования:
Ограничение по времени тестирования: по 1 секунде на
один тест.
Формат входных данных:
Входной текстовый файл содержит три
целых числа: m, n (2 ≤ m, n ≤ 2000000000) и p (100 ≤ p ≤ 10000).
Формат выходных
данных:
Выходной текстовый файл должен
содержать одно число – количество оставшихся плит (целое неотрицательное число
меньшее p).
Пример файлов входных и выходных данных:
