CF2146D2 Max Sum OR (Hard Version)

This is the hard version of the problem. The difference between the versions is that in this version, $ 0\leq l\leq r

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The only line of each test case contains two integers $ l $ and $ r $ ( $ 0\leq l \leq r

For each test case, print a single integer in the first line of output — the maximum value of $ \sum\limits_{i=1}^n \left (a_i\;|\;b_i \right ) $ . Then, print $ n $ distinct integers $ a_1, a_2, \ldots,a_n $ in the second line — the array $ a $ after reordering. If there are multiple answers, you may print any of them.

In the first test case, the reordered array $ a $ is $ [3,2,1,0] $ . The value of the expression is $ (3\;|\;0)+(2\;|\;1)+(1\;|\;2)+(0\;|\;3)=3+3+3+3=12 $ . It can be proved that this is the maximum possible value of the expression. In the second test case, the reordered array $ a $ is $ [7,8,5,4,3,2,9,0,1,6] $ . The value of the expression is $ 90 $ . It can be proved that this is the maximum possible value of the expression. In the third test case, it can be proved that $ 240 $ is the maximum possible value of the expression. In the fourth test case, the reordered array $ a $ is $ [10,8,7,6,9] $ . The value of the expression is $ (10\;|\;6)+(8\;|\;7)+(7\;|\;8)+(6\;|\;9)+(9\;|\;10)=14+15+15+15+11=70 $ . It can be proved that this is the maximum possible value of the expression.