19902번 - Неисправный марсоход 서브태스크다국어

Марсоход, осуществляющий международную миссию на Марсе, неисправен.

Для восстановления его работоспособности необходимо повысить мощность его батареи. Мощность батареи марсохода задаётся целым положительным числом. Текущая мощность батареи равна a, для восстановления работоспособности марсохода необходимо повысить её мощность до значения b. Для изменения мощности батареи на марсоход с Земли можно передавать специальные сигналы двух типов: X и Y. Сигнал типа X увеличивает текущую мощность батареи на 1, а сигнал типа Y увеличивает текущую мощность батареи на 2.

Организаторы миссии хотели бы изменить мощность батареи до необходимой, передав минимальное количество сигналов. К сожалению, из-за особенности устройства марсохода, если мощность батареи оказывается кратна целому числу c, он окончательно выходит из строя и перестаёт реагировать на сигналы.

Требуется написать программу, которая по заданным начальной мощности батареи a, необходимой мощности батареи b и целому числу c определяет минимальное количество сигналов, которое необходимо передать на марсоход, чтобы восстановить его работоспособность.

Входные данные содержит три целых числа: a, b и c, по одному на строке (1 ⩽ a < b ⩽ 10⁹, 2 ⩽ c ⩽ 10⁹, a не кратно c, b не кратно c).

Требуется вывести одно целое число: минимальное количество сигналов, которые необходимо передать на марсоход.

В первом примере можно действовать следующим образом: отправить на марсоход сигналы Y, X, Y. Мощность батареи меняется следующим образом: 2 → 4 → 5 → 7. Во втором примере можно действовать следующим образом: отправить на марсоход сигналы X, Y, X, Y. Мощность батареи меняется следующим образом: 4 → 5 → 7 → 8 → 10.