#H26. 【拓展题】晶体分裂

【拓展题】晶体分裂

Background

  你受命前往一颗遥远的行星,完成一项极其重要的任务。这颗行星的核心储存着古老的能量晶体,这些能量晶体拥有神秘的自我分裂特性。为了通过这一考验,你需要分裂这些能量晶体,将它们变成能量稳定的形式。

Description

  最初,这颗能量晶体的能量数值为 m。你可以在每次操作中选择能量值大于 1 的晶体,将其分裂为三个较小的能量晶体,例如现有晶体能量为 xx,分解为三个小晶体:$\lfloor x/2 \rfloor,\ x \mod 2,\ \lfloor x/2 \rfloor$。分裂的过程会持续,直到所有晶体的能量都稳定为 01

  在完成所有分裂后,你需要在一定范围内(从第 k 个到第 s 个位置)观察这些能量晶体的状态,确定其中有多少晶体的能量值为 1。只有正确回答这个问题,你才能完成任务,安全返回母舰。

Format

Input

  第一行包含三个整数 m,k,sm, k, s $(0 \leq m \leq 10^{14}, 0 \leq s - k \leq 10^5, 1 \leq k, s)$,表示初始能量数值与查询范围。

  输入保证 k,sk, s 合法,下标从 1 开始。

Output

  一个整数,表示给定范围内 1 的总数。

Samples

7 1 4
4
77186498974 15392062479 15392086306
13383