Эта задача про конфеты. Изначально у вас есть \(1\) конфета, а вы хотите иметь ровно \(n\) конфет.
Вы можете использовать два следующих заклинания в любом порядке не более \(40\) раз суммарно.
- Если у вас сейчас \(x\) конфет, то, используя первое заклинание, можно превратить \(x\) конфет в \(2x-1\) конфету.
- Если у вас сейчас \(x\) конфет, то, используя второе заклинание, можно превратить \(x\) конфет в \(2x+1\) конфету.
Составьте список заклинаний так, чтобы после использования этих заклинаний по порядку у вас было ровно \(n\) конфет, или определите, что это невозможно.
Выходные данные
Для каждого набора входных данных выведите следующее.
Если есть возможность получить \(n\) конфет, использовав заклинания не более \(40\) раз, то в первой строке выведите одно целое число \(m\) (\(1 \le m \le 40\)) — количество использованных вами заклинаний.
Затем во второй строке выведите \(m\) целых чисел \(a_{1}, a_{2}, \ldots, a_{m}\) (\(a_{i}\) должно быть равно \(1\) или \(2\)), разделенных пробелами. Если \(a_{i} = 1\), это означает, что вы используете первое заклинание на \(i\)-м шаге. Если \(a_{i} = 2\), это означает, что вы используете второе заклинание на \(i\)-м шаге.
Обратите внимание, что вам не нужно минимизировать количество операций \(m\), и если есть несколько вариантов ответа, можно вывести любой.
Если ответа не существует, выведите \(-1\).
Примечание
Для \(n=3\) мы можем просто использовать второе заклинание один раз и получить \(2 \cdot 1 + 1 = 3\) конфеты.
Для \(n=7\) мы можем использовать второе заклинание дважды. Применив это один раз, мы получаем \(3\) конфеты, а применив его дважды, мы получаем \(2 \cdot 3 + 1 = 7\) конфет.