Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

*Cherry isn't feeling well right now as she found a problem that she couldn't solve. So she started to listen to On the Sea and you, to make her happy, have to solve the problem for her.*

For any non-negative integer $n$, let $f(n)$ be the median of the submasks of $n$.

You are given two integers $l$ and $r$. You have to find the median of the sequence $f(l), f(l + 1), \ldots, f(r)$.

*An integer $x$ is a submask of $y$ if $x$ can be obtained by replacing some (possibly none or all) $1$-s in the binary representation of $y$ by $0$-s.*

*The median of a sequence is the value of an element which is in the middle of the sequence after sorting it in non-decreasing order. If the length of the sequence is even, the left of two middle elements is used. For example, the median of $[4,2,7,5]$ is $4$ since after sorting the sequence, it will look like $[2,4,5,7]$ and the left of two middle elements is equal to $4$. The median of $[7,1,2,9,6]$ equals $6$since after sorting, the value $6$ will be in the middle of the sequence.*

The first line of the input contains a single integer $t(1 \le t \le 10^5)$ denoting the number of test cases. The description of $t$ test cases follows.

The first and only line of each test case contains two space-separated integers $l$ and $r$ $(1 \le l \le r \le 10^9)$.

For each test case, print a single line containing the median of the of the sequence $f(l), f(l + 1), \ldots, f(r)$.

Input | Output |
---|---|

3 1 5 7 10 696969 69696969 | 0 1 8073418 |

In the second test case, The sorted list of the submasks of $7$ is $[0, 1, 2, 3, 4, 5, 6, 7]$, so $f(7) = 3$ . So we have to find the median of the sequence $f(7), f(8), f(9), f(10)$, and the list of these values is $[3, 0, 1, 2]$, and finally, the median of this list is $1$. |

92% Solution Ratio

Ashiqur.141492Earliest,

adnan_tokyFastest, 0.1s

Ashiqur.141492Lightest, 1.0 MB

TasdidShortest, 760B

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.