Sakurako's Not Favorite Toy#363

Sakurako's Not Favorite Toy

1 seconde
256 mégaoctets
Medium

Sakurako is tired of her favorite toy, so now she wants to play with another one, which is meters from her in the corridor of infinite length.

In one step, she can go from to meters forward (if the toy is closer than meters, then she can step over it), but the toy doesn't want to play with Sakurako, so it goes meters forward from Sakurako simultaneously with her.

Sakurako is in a hurry, so she asks you what is the minimum number of steps required to reach the toy if it is possible, and if she starts at position in the corridor.

Input

The first line contains three integers , , (1\le m, k, q\le 10^{18}) — distance of the toy from Sakurako, the maximum size of Sakurako's step, and size of the toy's step.

Note that it is recommended to use 64-bit integers (for example, long long in C++).

Output

Print a single number — the minimum number of steps Sakurako needs to make, or if it is impossible to reach the toy.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

In the first example, the timeline is the following:

  1. Sakurako moves from to , while the toy moves from to ;

  2. Sakurako moves from to (note that she took not the maximum size), while the toy moves from to .

In the second example, the timeline is the following:

  1. Sakurako moves from to , while the toy moves from to ;

  2. Sakurako moves from to , while the toy moves from to ;

  3. Sakurako moves from to , while the toy moves from to .

Scoring

In this problem, there are conditional blocks. If your solution works correctly for certain constraints, it will receive a certain number of points. Note that testing is going test by test, but not by blocks.

  1. ( points): m\le 10^5;

  2. ( points): without additional constraints.