Đếm Một Trong Dãy Gấp Đôi

Với số nguyên không âm $n$, định nghĩa dãy nhị phân $F(n)$: - Nếu $n\le 1,F(n)$ chỉ gồm phần tử $n$. - Nếu $n>1,F(n)=F(\lfloor n/2\rfloor )$, tiếp theo là $n\mathrm{mod}2$, rồi lại $F(\lfloor n/2\rfloor )$.

Các vị trí đánh số từ $1$. Cho $l,r$, hãy đếm số phần tử bằng $1$ trong đoạn $[l,r]$.

Input

• Một dòng chứa $n,l,r$.

Output

• In số lượng bit $1$.

Constraints

• $0\le n\le 10^{18}$ và $1\le l\le r\le |F(n)|$.

Scoring

• Subtask $1$ ($50$ điểm): $n\le 10^6$.
• Subtask $2$ ($50$ điểm): không có giới hạn bổ sung.

Example

5 2 6

3