Баланс#3195

Баланс

5 секунд

64 мегабайти

Складна

Пані Ійо Кіффа-Австраліс має терези й лише два типи гир, щоб зважувати дозу ліків. Наприклад, щоб відміряти $200$ мг аспірину, використовуючи гирі по $300$ мг і $700$ мг, вона може покласти одну гирю по $700$ мг на сторону з ліками та три гирі по $300$ мг на протилежний бік (Рисунок 1). Хоча вона може покласти чотири гирі по $300$ мг на бік з ліками й дві гирі по $700$ мг на інший бік (Рисунок 2), вона не вибере це рішення, оскільки використання більшої кількості гир є менш зручним.

Вам необхідно визначити, скільки гир потрібно використати.

Рисунок 1. Вимірювання $200$ мг аспірину за допомогою трьох гир по $300$ мг і однієї гирі по $700$ мг

Рисунок 2. Вимірювання $200$ мг аспірину за допомогою чотирьох гир по $300$ мг і двох гир по $700$ мг

Вхідні дані

Вхід складається з послідовності наборів даних. Кожен набір даних — це рядок, що містить три додатних цілих числа $a$ , $b$ і $d$ , розділених пробілом. Виконуються умови: $a \neq = b$ a \neq b, $a \leq 10000$ a \leq 10000, $b \leq 10000$ b \leq 10000, та $d \leq 50000$ d \leq 50000. Вважається, що можливо відміряти $d$ мг за допомогою комбінації гир по $a$ мг і $b$ мг. Іншими словами, випадки, коли немає рішення, розглядати не потрібно.

Кінець вхідних даних позначається рядком із трьох нулів, розділених пробілами. Цей рядок не є набором даних.

Вихідні дані

Вивести рядки, кожен з яких відповідає відповідному набору даних $(a, b, d)$ (a, b, d). Кожен рядок відповіді повинен містити два невід'ємних цілих числа $x$ і $y$ , розділених пробілом. Вони мають задовольняти таким трьом умовам:

Можна відміряти $d$ мг, використовуючи $x$ гир по $a$ мг і $y$ гир по $b$ мг.
Загальна кількість гир $x + y$ x + y є мінімальною серед усіх пар невід'ємних цілих чисел, що задовольняють попередню умову.
Загальна маса гир $a x + b y$ a x + b y є мінімальною серед усіх пар, що задовольняють дві попередні умови.

У відповіді не повинно бути жодних зайвих символів (наприклад, додаткових пробілів).

Приклади

Приклад 1