Система мартингейл
Одной из "выигрышных" схем управления ставками при игре в рулетку является система мартингейл. Суть ее заключается в следующем:
Ставки выполняются сериями. Серия начинается с некоторой минимальной ставки, которая делается на "красное" или "черное".
Если ставка сыграла, то серия заканчивается и игрок может начинать новую с минимальной ставки.
Если же игрок проиграл, то для того, чтобы окупить этот (и возможно предыдущие проигрыши) игрок снова ставит на тот же цвет, удваивая ставку.
Мнимую выигрышность такой схемы обосновывают кажущимся естественным аргументом, что поскольку оба цвета при одном броске имеют равные шансы выпадения, то количество выпадений каждого цвета должно быть примерно одинаковым, а значит длинная серия выпадения одного цвета повышает вероятность того, что очень скоро должен выпасть противоположный цвет.
На самом же деле, шарик не обладает памятью, и потому события выпадения чисел при различных бросках независимы друг от друга. Потому независимо от того, какие цвета и ставки были при предыдущих бросках, вероятность выигрыша при очередном броске будет по прежнему равна 1/2 (и даже меньше за счет поля "зеро").
Тем не менее, вероятность проигрыша в серии составит (1/2)^k, где k - ее длина. Разумеется, что при больших k эта вероятность становится чрезвычайно малой, однако и сумма, которой рискует игрок возрастает экспоненциально, при том, что в случае удачи выигрыш составит всего лишь величину первоначальной (минимальной) ставки.
Таким образом, предложенная система позволит выигрывать чаще, однако первая же неудача отберет такое количество денег, что продолжить игру будет невозможно.
Следует отметить, что в реальных казино существуют ограничения на размер ставки как снизу, так и сверху, что не позволяет игрокам разворачивать слишком длинные серии.
Несмотря на все предостережения, указанные здесь, главный герой этой задачи по имени Вася решил все же попробовать поиграть в казино по этой системе. Проведя несколько удачных серий, он заметил, что её можно "улучшить". Так, например, при ограничениях на ставки от 10 до 235, последовательность ставок в серии согласно схеме будет такой 10, 20, 40, 80, 160. Однако за счет того, что верхний предел ставок не достигается, используются не все возможности. Так последовательность 10, 25, 55, 115, 235 обладает той же вероятностью выигрыша, но при этом позволяет увеличивать сумму выигрыша, если несколько первых выпадений были неудачными.
Кроме того, Вася хочет попробовать применить подобную схему для ставок и на поля с более высоким коэффициентом (у полей цвета этот коэффициент равен 2, что означает, что в случае выпадения соответствующего цвета игрок, поставивший на него, получает в 2 раза больше, чем поставил, т.е. возвращает свою ставку и получает еще столько же).
Ваша задача - помочь Васе построить серию ставок, обладающую следующими свойствами:
Каждая ставка должна в случае выпадения подходящего числа окупить все предыдущие проигранные ставки и принести (за вычетом этих сумм) выигрыш не меньший, чем выигрыш, который мог бы получиться, если бы сыграла предыдущая ставка.
Длина серии (для увеличения вероятности выигрыша) должна быть максимально возможной.
Если серий максимальной длины несколько, то среди них следует выбрать такую, которая каждый раз максимально увеличивает величину выигрыша. Более точно, если w_i - величина выигрыша игрока, при условии что сыграет i-ая ставка (с учетом вычета сумм предыдущих ставок), то минимальная из величин w_{i+1} - w_i должна быть максимально возможной.
Если серий, удовлетворяющих предыдущим условиям, также несколько, то выбирается такая, при которой выигрыш с первой же ставки будет максимально возможным. Если и таких несколько, то максимальным должен быть выигрыш со второй ставки, с третьей и т.д.
Входные данные
В единственной строке входного файла задаются три натуральных числа min, max и q (1 ≤ min ≤ max ≤ 10^18, 2 ≤ q ≤ 1000), где min и max - размер минимальной и максимальной ставки соответственно, q - коэффициент поля, на которое будут выполняться ставки.
Выходные данные
В первой строке выходного файла выведите число - длину оптимальной серии ставок. Во второй строке должны быть указаны последовательно размеры ставок серии.