Remote Training on Programming

Великая треугольная область (ВТО) представляет собой прямоугольный треугольник. Его катеты имеют целые длины m и n и лежат на осях координат. Нужно покрыть как можно большую часть территории ВТО квадратными плитами размером 1×1. Плиты должны плотно прилегать одна к другой и к катетам ВТО, не выходя за пределы области. Резать плиты нельзя.

Плиты поставляются только контейнерами по p штук; используется необходимый минимум контейнеров.

Требуется написать программу, которая вычислит, сколько плит из последнего контейнера останется после покрытия ВТО.

Технические требования:

Ограничение по времени тестирования: по 1 секунде на один тест.

Формат входных данных:

Входной текстовый файл содержит три целых числа: m, n (2 ≤ m, n ≤ 2000000000) и p (100 ≤ p ≤ 10000).

Формат выходных данных:

Выходной текстовый файл должен содержать одно число – количество оставшихся плит (целое неотрицательное число меньшее p).

Пример файлов входных и выходных данных:

STDIN	STDOUT
4 3 100	97