2146D1. Max Sum OR (Easy Version)

bitmasks, constructive algorithms, divide and conquer, greedy, trees, *1500

https://codeforces.com/problemset/problem/2146/D1

This is the easy version of the problem. The difference between the versions is that in this version, 𝑙=0, and 𝑟<2⋅105. You can hack only if you solved all versions of this problem.

You are given two integers 𝑙 and 𝑟 (𝑙≤𝑟).

Let 𝑛=𝑟−𝑙+1. We will create two arrays 𝑎 and 𝑏, both consisting of 𝑛 integers. Initially, both 𝑎 and 𝑏 are equal to [𝑙,𝑙+1,…,𝑟]. You have to reorder the array 𝑎 arbitrarily to maximize the following value:

∑𝑖=1𝑛(𝑎𝑖|𝑏𝑖).

Here, | denotes the bitwise OR operation.

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

Input

Each test contains multiple test cases. The first line contains the number of test cases 𝑡 (1≤𝑡≤104). The description of the test cases follows.

The only line of each test case contains two integers 𝑙 and 𝑟 (0=𝑙≤𝑟<2⋅10^5) — the minimum and maximum elements in 𝑎.

Let 𝑛=𝑟−𝑙+1. It is guaranteed that the sum of 𝑛 over all test cases does not exceed 2⋅10^5.

Output

For each test case, print a single integer in the first line of output — the maximum value of ∑𝑖=1𝑛(𝑎𝑖|𝑏𝑖).

Then, print 𝑛 distinct integers 𝑎1,𝑎2,…,𝑎𝑛 in the second line — the array 𝑎 after reordering.

If there are multiple answers, you may print any of them.

Example

Input

Output

12
3 2 1 0 
90
7 8 5 4 3 2 9 0 1 6
240
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

Note

In the first test case, the reordered array 𝑎 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 𝑎 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.

【尹显齐 25物理学院】可以看出，可能的最大答案是 $n (n - 1)$ （即所有数都满足 $a_{i} | b_{i} = a_{i} + b_{i}$ ），下面给出一个构造使得所有数都满足该条件。

我们不难发现，如果两个数加起来等于 $2^{k} - 1$ ，则它们按位与运算的值也是 $2^{k} - 1$ 。于是我们可以这样做：对于当前的 $n$ ，令 $x$ 为比 $n$ 大的第一个形式为 $2^{k} - 1$ 的数，则从 $x - n$ 到 $n$ 的所有数都可以找到对应的数使得它们的和为 $x$ 。然后我们发现接下来只用处理从 $0$ 到 $x - n - 1$ 的数就行了，可用递归方便地解决。

python

for _ in range(int(input())):
    l,r = map(int,input().split())
    n = r-l+1
    print(n*(n-1))
    ans = [0]*(n)
    def sol(k):
        if k <= 0:
            return
        lbt = 2**(k.bit_length())-1-k
        for i in range(lbt,k+1):
            ans[i] = 2**(k.bit_length())-1-i
        sol(lbt-1)
    sol(n-1)
    print(*ans)

2146D1. Max Sum OR (Easy Version) ​

2146D1. Max Sum OR (Easy Version)