At the moment, Barysh is watching channel š¯‘ˇ on TV but wants to switch to channel bĀ (b>a) because an interesting football match is showing there. The TV remote is broken, only two buttons work. When one of these buttons is pressed, the TV switches to a channel with a number 1 unit higher, and when the other button is pressed, the TV switches to a channel with a number 2 units higher. Barysh wants to quickly switch to channel b, pressing the minimum number of buttons, but there's a problem with channels whose numbers are exactly divisible by c. When Barysh switches the TV to such a channel, the TV breaks.
What is the minimum number of button presses for Barysh to switch from channel number a to channel number b?
The first line contains an integer a, the second line contains an integer bĀ (1ā‰¤a<bā‰¤109), and the third line contains an integer cĀ (2ā‰¤cā‰¤109). It is guaranteed that a and b are not divisible by c.
Print the minimum number of button presses for Barysh to switch from channel number a to channel number b.
In the first example, the transitions can be performed as follows: 2ā†’4ā†’5ā†’7.
In the second example, the transitions can be performed as follows: 4ā†’5ā†’7ā†’8ā†’10.
This problem consists of 4 subtasks. Points for a subtask are awarded only if all the tests associated with that subtask are passed successfully.
(20 points): b,cā‰¤15;
(30 points): b,cā‰¤105;
(15 points): c=2;
(35 points): noĀ additionalĀ constraints;