Martingale sequence#2427

Martingale sequence

1 second
64 megabytes
Hard

You are playing a mathematical game that involves making a sequence of wagers using points. The rules of the game are as follows:

For each round, a successful move returns you times the number of points you wager (so you get back your wager plus q-1 times the wager as extra points). However, there are constraints: every wager must be between and points, inclusive.

Your task is to construct the optimal sequence of wagers under the following conditions:

Input

The input consists of a single line with three positive integers: , , and (1 \leq min \leq max \leq 10^{18}, 2 \leq q \leq 1000), where and are the minimum and maximum allowed wager in the game, and is the success multiplier.

Output

Output two lines. The first line should be the length of the optimal sequence of wagers. The second line should contain the wager amounts in sequence.

Examples

Example 1

Loading
Loading