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 \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$.

这是该问题的困难版本。两个版本的区别在于，在本版本中，$0\leq l\leq r \lt 2^{30}$。仅当您已解决该问题的所有版本时，才可进行 hack。

给定两个整数 $l$ 和 $r$（满足 $l\le r$）。

令 $n = r - l + 1$。我们将构造两个长度均为 $n$ 的整数数组 $a$ 和 $b$。初始时，$a$ 和 $b$ 均等于 $[l, l+1, \ldots, r]$。您需要对数组 $a$ 进行任意重排，以最大化如下值：

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

其中，$|$ 表示按位或运算。

您还需构造一种可行的 $a$ 的重排方案。

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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例仅一行，包含两个整数 $l$ 和 $r$（$0\leq l \leq r \lt 2^{30}$）——即数组 $a$ 中的最小值和最大值。

令 $n = r - l + 1$。保证所有测试用例的 $n$ 之和不超过 $2\cdot 10^5$。

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.

对于每个测试用例，在输出的第一行打印一个整数——$\sum\limits_{i=1}^n \left (a_i\;|\;b_i \right )$ 的最大值。

然后，在第二行打印 $n$ 个互不相同的整数 $a_1, a_2, \ldots,a_n$——重排后的数组 $a$。

如果存在多个答案，你可以输出其中任意一个。

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.

在第一个测试用例中，重排后的数组 $a$ 为 $[3,2,1,0]$。该表达式的值为 $(3\;|\;0)+(2\;|\;1)+(1\;|\;2)+(0\;|\;3)=3+3+3+3=12$。可以证明这是该表达式可能取得的最大值。

在第二个测试用例中，重排后的数组 $a$ 为 $[7,8,5,4,3,2,9,0,1,6]$。该表达式的值为 $90$。可以证明这是该表达式可能取得的最大值。

在第三个测试用例中，可以证明 $240$ 是该表达式可能取得的最大值。

在第四个测试用例中，重排后的数组 $a$ 为 $[10,8,7,6,9]$。该表达式的值为 $(10\;|\;6)+(8\;|\;7)+(7\;|\;8)+(6\;|\;9)+(9\;|\;10)=14+15+15+15+11=70$。可以证明这是该表达式可能取得的最大值。