D2. Максимальная сумма ИЛИ (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии $$$0\leq l\leq r \lt 2^{30}$$$. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Даны два целых числа $$$l$$$ и $$$r$$$ ($$$l\le r$$$).

Обозначим $$$n = r - l + 1$$$. Мы создадим два массива $$$a$$$ и $$$b$$$, оба состоящие из $$$n$$$ целых чисел. Изначально оба массива $$$a$$$ и $$$b$$$ равны $$$[l, l+1, \ldots, r]$$$. Вам нужно произвольно переставить массив $$$a$$$, чтобы максимизировать следующее значение:

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

Здесь $$$|$$$ обозначает операцию побитового ИЛИ.

Вам также нужно построить возможный способ перестановки массива $$$a$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число в первой строке вывода — максимальное значение $$$\sum\limits_{i=1}^n \left (a_i\;|\;b_i \right )$$$.

Затем выведите $$$n$$$ различных целых чисел $$$a_1, a_2, \ldots,a_n$$$ во второй строке — массив $$$a$$$ после перестановки.

Если существует несколько ответов, вы можете вывести любой из них.

Пример
Входные данные
7
0 3
0 9
0 15
6 10
1 4
3 6
1000000007 1000000009
Выходные данные
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 
70
10 8 7 6 9
20
2 1 4 3 
28
4 3 6 5 
3000000039
1000000008 1000000007 1000000009
Примечание

В первом наборе входных данных переставленный массив $$$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$$$. Можно доказать, что это максимально возможное значение выражения.