Система мартінгейл
Однією з "виграшних" схем управління ставками при грі у рулетку є система мартінгейл. Суть її полягає у наступному:
Ставки виконуються серіями. Серія починається з деякої мінімальної ставки, яка робиться на "червоне" або "чорне".
Якщо ставка зіграла, то серія завершується і гравець може починати нову з мінімальної ставки.
Якщо ж гравець програв, то для того, щоб повернути цей (і можливо попередні програші) гравець знову ставить на той же колір, подвоюючи ставку.
Уявну виграшність такої схеми обгрунтовують ніби природним аргументом, що оскільки обидва кольори при одному кидку мають рівні шанси випадіння, то кількість появи кожного кольору повинна бути приблизно однаковою, а значить довга серія випадіння одного кольору збільшує ймовірність того, що дуже швидко повинен випасти протилежний колір.
Наспавді ж, кулька не має пам'яті, і тому події випадіння чисел при різних кидках незалежні одна від одної. Тому незалежно від того, які кольори і ставки були при попередніх кидках, ймовірність вграшу при черговому кидку буде як і раніше становити 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 - коефіцієнт поля, на яке будуть виконуватись ставки.
Вихідні дані
У першому рядку вихідного файлу виведіть число - довжину оптимальної серії ставок. У другому рядку повинні бути вказані послідовні розміри ставок серії.