У Serval есть два \(n\)-битных двоичных числа \(a\) и \(b\). Он хочет поделиться этими числами с Toxel.
Так как Toxel больше нравится число \(b\), Serval решил изменить \(a\) на \(b\) с помощью нескольких (возможно, нуля) операций. За одну операцию Serval может выбрать любое положительное целое число \(k\) от \(1\) до \(n\), и заменить \(a\) на одно из следующих чисел:
- \(a\oplus(a\ll k)\)
- \(a\oplus(a\gg k)\)
Другими словами, операция сдвигает каждый бит числа \(a\) налево или направо на \(k\) позиций, при этом переполненные биты удаляются, а недостающие биты дополняются \(0\). Побитовое исключающее ИЛИ результата сдвига и изначального \(a\) присваиваются обратно \(a\).
У Serval нет много времени. Он хочет применить не более \(n\) операций, чтобы изменить \(a\) на \(b\). Пожалуйста, помогите ему найти последовательность операций, или определите, что невозможно изменить \(a\) на \(b\) за не более \(n\) операций. Вам не нужно минимизировать количество операций.
В этой задаче \(x\oplus y\) обозначает побитовое исключающее ИЛИ чисел \(x\) и \(y\). \(a\ll k\) и \(a\gg k\) обозначают логический сдвиг влево и логический сдвиг вправо.
Выходные данные
Для каждого набора входных данных, если невозможно изменить \(a\) на \(b\) за не более \(n\) операций, выведите одно число \(-1\).
Иначе, в первой строке выведите количество операций \(m\) (\(0\le m\le n\)).
Если \(m>0\), во второй строке выведите \(m\) целых чисел \(k_{1},k_{2},\dots,k_{m}\) обозначающих операции. Если \(1\le k_{i}\le n\), это обозначает логический сдвиг влево \(a\) на \(k_{i}\) позиций. Если \(-n\le k_{i}\le-1\), это обозначает логический сдвиг вправо \(a\) на \(-k_{i}\) позиций.
Если существует несколько решений, выведите любое из них.
Примечание
В первом наборе входных данных:
Первая операция изменяет \(a\) на \(\require{cancel}00111\oplus\cancel{001}11\underline{000}=11111\).
Вторая операция изменяет \(a\) на \(\require{cancel}11111\oplus\underline{00}111\cancel{11}=11000\).
Биты с зачеркиванием — это биты с переполнением, которые удаляются. Биты с подчеркиванием являются дополненными битами.
Во втором наборе входных данных \(a\) уже равно \(b\), поэтому никаких операций делать не нужно.
В третьем наборе входных данных можно показать, что \(a\) невозможно изменить на \(b\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5
00111
11000
1
1
1
3
001
000
|
2
3 -2
0
-1
|