Martingale system
The Martingale betting system is a popular strategy used in roulette. Here's how it works:
Bets are placed in a sequence. Each sequence begins with a minimum bet, which is placed on either "red" or "black."
If the bet wins, the sequence ends, and the player can start a new sequence with the minimum bet.
If the bet loses, the player doubles the bet on the same color to recover the loss and potentially previous losses.
The appeal of this system lies in the belief that since each color has an equal chance of appearing in a single spin, the occurrences of each color should balance out over time. Thus, a long streak of one color increases the likelihood that the opposite color will appear soon.
However, in reality, each spin is independent, and the probability of winning remains 1/2 (or slightly less due to the "zero" field). The chance of losing a series is (1/2)^k, where k is the series length. While this probability decreases with larger k, the risked amount grows exponentially, and a successful outcome only yields a profit equal to the initial bet.
Therefore, while the system may lead to frequent wins, a single loss can result in a significant financial setback, making it difficult to continue playing.
Casinos impose betting limits to prevent excessively long series.
Despite these warnings, Vasya, the protagonist, decided to try this system at a casino. After some successful series, he realized he could "improve" it. For instance, with betting limits from 10 to 235, the sequence of bets would be 10, 20, 40, 80, 160. However, since the upper limit isn't reached, not all possibilities are utilized. A sequence like 10, 25, 55, 115, 235 offers the same winning probability but increases potential winnings if the initial outcomes are unsuccessful.
Vasya also wants to apply a similar strategy to bets on fields with higher coefficients (for color fields, this coefficient is 2, meaning a winning bet returns double the amount wagered).
Your task is to help Vasya create a betting series with these characteristics:
Each bet should, if successful, cover all previous losses and yield a profit at least equal to the potential profit from the previous bet.
The series should be as long as possible to maximize the chance of winning.
If multiple series have the maximum length, choose the one that maximizes profit incrementally. Specifically, if w_i is the profit from the i-th bet (after deducting previous losses), the minimum value of w_{i+1} - w_i should be maximized.
If multiple series meet the above criteria, choose the one with the largest profit from the first bet. If there are still ties, maximize the profit from the second bet, then the third, and so on.
Input
The input consists of a single line with three natural numbers: min, max, and q (1 ≤ min ≤ max ≤ 10^18, 2 ≤ q ≤ 1000). Here, min and max are the minimum and maximum bet sizes, and q is the coefficient for the field being bet on.
Output
The output should contain two lines. The first line should display the length of the optimal betting series. The second line should list the consecutive bet sizes in the series.