У вас есть массив \(a_0, a_1, \ldots, a_{n-1}\) длины \(n\). Изначально \(a_i = 2^i\) для всех \(0 \le i \lt n\). Обратите внимание, что элементы массива \(a\) нумеруются с нуля.
Вы хотите развернуть этот массив (то есть сделать \(a_i\) равным \(2^{n-1-i}\) для всех \(0 \le i \lt n\)). Чтобы сделать это, вы можете сделать следующую операцию не более \(250\,000\) раз:
- Выбрать целое число \(i\) (\(0 \le i \lt n\)) и заменить \(a_i\) на \(a_i \oplus a_{(i+1)\bmod n}\).
Здесь \(\oplus\) обозначает операцию побитового исключающего ИЛИ.
Найдите любую последовательность операций, после выполнения которой массив \(a\) окажется развёрнутым. Можно показать, что при данных ограничениях решение всегда существует.
Выходные данные
В первой строке выведите одно число \(k\) (\(0 \le k \le 250\,000\)) — количество использованных операций.
Во второй строке выведите \(k\) чисел \(i_1,i_2,\ldots,i_k\) (\(0 \le i_j \lt n\)), которые обозначают, что на \(j\)-й операции вы выбрали число \(i_j\).
Обратите внимание, что вам не требуется минимизировать количество операций.
Примечание
В примечании красным выделены элементы, находящиеся в позициях, к которым применяются операции.
В первом наборе входных данных массив \(a\) изменится следующим образом:
\([1,\color{red}{2}] \rightarrow [\color{red}{1},3] \rightarrow [2,\color{red}{3}] \rightarrow [2,1]\).
Во втором наборе входных данных массив \(a\) изменится следующим образом:
\([1,\color{red}{2},4] \rightarrow [\color{red}{1},6,4] \rightarrow [7,\color{red}{6},4] \rightarrow [\color{red}{7},2,4] \rightarrow [5,2,\color{red}{4}] \rightarrow [5,\color{red}{2},1] \rightarrow [\color{red}{5},3,1] \rightarrow [6,\color{red}{3},1] \rightarrow [\color{red}{6},2,1] \rightarrow [4,2,1]\).