Mars Rover Battery Power Adjustment

The Mars rover performing an international mission has encountered a malfunction. In order to restore its normal operation, its battery power must be increased. The battery power is represented by a positive integer. Currently, the battery power is a, and it must be raised to b for the rover to function properly. You can send two types of special signals from Earth to the rover to adjust the battery power:

• An X signal increases the current battery power by \(1\).
• A Y signal increases the current battery power by \(2\).

However, due to certain technical constraints, during the process of increasing the power, the battery power must never be a multiple of \(c\) (i.e. it must never satisfy \(power\ \%\ c = 0\)). If the battery power becomes a multiple of \(c\) at any step, the battery will explode.

Your task is to determine the minimum number of signals required to increase the battery power from \(a\) to \(b\) without ever reaching a forbidden state. If it is impossible to do so without causing an explosion, output -1.

inputFormat

Input consists of a single line containing three positive integers: a, b, and c, where:

• a is the current battery power.
• b is the target battery power.
• c is the integer such that the battery power must never be a multiple of c during the signal transmission process.

outputFormat

Output a single integer representing the minimum number of signals required to increase the battery power from \(a\) to \(b\) while avoiding any intermediate battery power that is a multiple of \(c\). If it is not possible to reach \(b\) under these constraints, output -1.

sample

3 7 5

3