• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

به علت اعتراض فراوان مردم به مالیات، اداره‌ی مالیات نحوه محاسبه‌ی مالیات را عوض کرده است تا مثلا بگوید که به اعتراضات رسیدگی کرده است.

در این محاسبه‌ی جدید مالیات، افراد با توجه به درآمد و سطح سوادشان مالیات می‌دهند. مثلا مالیات شخصی با سطح سوادی $k$ و درآمد $x$ به این صورت حساب می‌شود:

تابع $f(x, k)$ را به این صورت تعریف میکنیم که اگر $x$ زوج باشد $f(x, k) = x / 2$ و اگر $x$ فرد باشد $f(x, k) = x + k$.

حال دنباله‌ی زیر را در نظر بگیرید:

$$x, f(x, k), f(f(x, k), k), f(f(f(x, k), k), k), ...$$

مقدار مالیات شخصی با درآمد $x$ و سطح سواد $k$ برابر اولین عضو دنباله‌ی بالا است که مقدار آن کمتر یا مساوی $k$ می‌باشد. اندیس این عضو از دنباله را $g(x, k)$ فرض میکنیم.(دنباله از ۰ شماره‌گذاری می‌شود) اگر مرد مالیاتچی از چنین شخصی مالیات بگیرد به اندازه‌ی $g(x, k)$ می‌تواند کارمزد برای خودش بگیرد.

به همان علت که اداره‌ی مالیات همچین تابعی را برای محاسبه‌ی مالیات برگزیده است، میزان سواد افراد در شهر مرد مالیاتچی عددی فرد می‌باشد.

مرد مالیاتچی می‌خواهد از یک محله ثروتمند پول بگیرد. تمامی افراد این محله دارای سطح سواد $d$ می‌باشند. میزان درآمد افراد این محله بین $l$ تا $r$ می‌باشد (دقیقا به ازای هر عدد در این بازه یک نفر است که این درآمد را دارد).

حال به مرد مالیاتچی بگویید که در مجموع او چقدر می‌تواند پول به عنوان کارمزد بسلفد!

ورودی

در تنها سطر ورودی سه عدد $l$، $r$ و $d$ آمده است.

عدد $d$ فرد می‌باشد.

$$1 \le d \le 100 \ 000$$ $$1 \le l \le r \le 10^{16}$$

خروجی

در تنها سطر خروجی میزان درآمد مرد مالیاتچی را خروجی دهید.

مثال

ورودی نمونه ۱

6 6 1

خروجی نمونه ۱

4

دنباله‌ی $f(6, 1)$ به این صورت است:

$$6, 3, 4, 2, 1, 2, 1, 2, 1, 2, ...$$

ورودی نمونه ۲

1 5 3

خروجی نمونه ۲

4