EIU Programming Practices and Exams

Today is Sunday, the weather is beautiful and sunny, very suitable for participating in outdoor activities, so Duong asked his mother to let him go play video games. When we arrived at the internet cafe, there was only one empty machine left and there were many people waiting, all of them fighting for the empty machine. The shop owner saw this and immediately gave us a difficult problem to chase them all away.

The shop owner gives a list with a single integer n. There is only one type of operation that can be performed on that list. For each operation, it is necessary to delete any integer x from the list with x not less than or equal to 1, then insert in the original position of x the following three numbers: floor(x/2), x mod 2, floor(x/2) in the given order. Repeat this operation until all elements in the list become 0 or 1.

Just hearing this was difficult, so the shop owner decided to ask more difficult questions. He wanted to know how many 1s there were in the list in the range from L to R. Duong was so busy thinking about the game that he no longer had the mind to program. Please help Duong answer the shop owner's super easy questions so that Duong can quickly enter the game to carry the team.

Input

-      A single line containing three integers n, L, R (0 <= n < 2⁵⁰, 0 <= R - L <= 10¹⁵, R >=1, L >= 1), respectively the original source on the list and the two limits (range) the shop owner will ask

The testcase ensures that R does not exceed the list length after performing operations.

Output

A single line containing an integer – number of 1s in the range L to R.

Sample