This is the hard version of the problem. The difference between the versions is that in this version, $$$0\leq l\leq r \lt 2^{30}$$$. You can hack only if you solved all versions of this problem.

You are given two integers $$$l$$$ and $$$r$$$ ($$$l\le r$$$).

Let $$$n = r - l + 1$$$. We will create two arrays $$$a$$$ and $$$b$$$, both consisting of $$$n$$$ integers. Initially, both $$$a$$$ and $$$b$$$ are equal to $$$[l, l+1, \ldots, r]$$$. You have to reorder the array $$$a$$$ arbitrarily to maximize the following value:

$$$$$$\sum_{i=1}^n \left (a_i\;|\;b_i \right ).$$$$$$

Here, $$$|$$$ denotes the bitwise OR operation.

You also need to construct a possible way to reorder the array $$$a$$$.

Input

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 \lt 2^{30}$$$) — the minimum and maximum elements in $$$a$$$.

Let $$$n = r - l + 1$$$. It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

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.

Note

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.

Max Sum OR (Hard Version)

Examples