# Practice on Toph

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

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 So we have to find the median of the sequence |

92% Solution Ratio

Ashiqur.141492Earliest,

adnan_tokyFastest, 0.1s

Ashiqur.141492Lightest, 1.0 MB

TasdidShortest, 760B

Login to submit