Куро только что узнал о перестановках и этого его вдохновило придумать новый вид перестановок. Он выбрал \(n\) различных целых положительных чисел и сделал из них множество \(S\). Теперь он определяет волшебную перестановку следующим образом:
- Это перестановка всех целых чисел от \(0\) до \(2^x - 1\), где \(x\) это какое-то неотрицательное целое число.
- Побитовое исключающее или любых двух соседних элементов перестановки лежит в множестве \(S\).
Так как Куро очень восхищённо относится к волшебным перестановкам, то он хочет создать самую длинную возможную волшебную перестановку. Иначе говоря, он хочет найти такое наибольшее неотрицательное целое число \(x\), что существует волшебная перестановка целых чисел от \(0\) до \(2^x - 1\). Поскольку он немного новичок в вопросе перестановок, он хочет чтобы вы ему помогли и нашли это \(x\), а также волшебную перестановку для этого \(x\).
Выходные данные
В первой строке выведите наибольшее неотрицательное целое число \(x\), такое что существует волшебная перестановка чисел от \(0\) до \(2^x - 1\).
Затем выведите \(2^x\) целых чисел задающую волшебную перестановку чисел от \(0\) до \(2^x - 1\). В случае если существует несколько таких волшебных перестановок, выведите любую из них.
Примечание
В первом примере \(0, 1, 3, 2\) образует волшебную перестановку так как:
- \(0 \oplus 1 = 1 \in S\)
- \(1 \oplus 3 = 2 \in S\)
- \(3 \oplus 2 = 1 \in S\)
Где \(\oplus\) обозначает операцию побитового исключающего ИЛИ.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 2 3
|
2
0 1 3 2
|
|
2
|
2
2 3
|
2
0 2 1 3
|
|
3
|
4
1 2 3 4
|
3
0 1 3 2 6 7 5 4
|
|
4
|
2
2 4
|
0
0
|
|
5
|
1
20
|
0
0
|
|
6
|
1
1
|
1
0 1
|