Drunken Binary
Time Limit: 1 second
Lisa recently found out about binary numbers and was fasinated by them. However, after a while, she got bored, and started pondering about the great wonders of life and other things, such as the effect of binary numbers getting drunk and misbehaving. Why do binary numbers only use the numbers 0 and 1? Why not we introduce another number, say, 2, to the binary system? So now, instead of representing the numeber 6 with 110, we could do so with 22 (2 x 2 + 2). Naturally, there is more than one way to represent different numbers now. But how much?
Instead of slowly counting up the number of ways for each and every number, she decided to enlist the help of the all high and great mighty programmer, you. However, she is not intrested in the actual number itself, but rather the difference of the number of ways to represent a number in druken binary format between two numbers (don't ask; they are the most confusing creatures on earth after all). That is to say, suppose the number 4 can be expressed in 3 ways, and the number 5 can be expressed in 2 ways, she only wants the differnce, of the two numbers, which in this case is 2 - 3 = -1. Now if she chooses two numbers that are not consecutive numbers, say i and j, she wants the sum of all the differnce between each two consecutive numbers a, a + 1 for all i <= a, a + 1 <= j (see sample input for example). Since the answer maybe rather large, output the floor of the square root of the answer. If the original answer happens to be negative, like the one shown above, output the negative of the floor of the square root of the absoulute value of the original answer. Since she also happens to guarentee you certain promises that cannot be listed here for the sake of not corrupting the younger readers that are out here, you decided to agree to her strange request. So what are you waiting for? Start coding!
Input
The first line of input contiains two space-separated integers, N and TC. It is guarenteed that i and j will at most have a number of N, and TC is the number of test cases.
The next TC lines each contan another 2 space-seperated integers, i and j, representing the start and end point of the sequence that you are suppose to find the sum of differences of. Note that i and j may not neccesary be distinct; that is to say, i may sometimes be equal to j.
Output
The output should contain TC lines. Each line should cantain the floor of the square root of the sum of the diffences of the number of ways to represent a number in binary format if we allow for 2 between i and j (well unless it results in a negative number, in which case follow the rule above).
Constraints
0 <= i, j <= N
0 <= N <= 1,000,000,000
1 <= TC <= 1000
However, not all the test cases will have such a high TC or N. In particular:
Subtask 1 (20%): N <= 1,000,000
Subtask 2 (10%): j = i or i + 1 for all test cases
Subtask 3 (10%): TC <= 10
Subtask 4 (60%): No further constraints
Sample Input 1
5 1
4 5
Sample Output 1
-1
Explanation: see story
Sample Input 2
10 2
1 4
7 7
Sample Output
1
0
Explantion:
TC 1: the number of ways to represent a number in binary format if we allow the use of two for the following numebrs 1, 2, 3 and 4 is 1, 2, 1 and 3 respectively. The differeces are 1, -1 and 2, and the sum is just 2. The floor of the square root of this is just simply 1.
TC 2: the number of ways to represent a number in binary format if we allow the use of two for the following numebrs 7 and 7 must be the same, no? The floor of the square root of 0 turns out to be (drum roll) 0.