D. Контрольные точки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Gildong разрабатывает игру, состоящую из $$$n$$$ уровней, пронумерованных от $$$1$$$ до $$$n$$$. Игрок начинает игру на $$$1$$$-м уровне и должен проходить их в порядке возрастания номера. Игрок выигрывает, когда он проходит $$$n$$$-й уровень.

На каждом уровне есть не более одной контрольной точки, но она всегда есть на $$$1$$$-м уровне. В начале игры, только контрольная точка на $$$1$$$-м уровне активирована, а все остальные деактивированы. Когда игрок доходит до $$$i$$$-го уровня, на котором есть контрольная точка, эта контрольная точка активируется.

Для каждой попытки прохождения уровня, игрок может либо пройти уровень, либо проиграть. Если он проходит $$$i$$$-й уровень, игрок следует на $$$i+1$$$-й уровень. Если он проигрывает на $$$i$$$-м уровне, игрок отправляется на самую последнюю активированную контрольную точку, и ему требуется снова проходить уровни начиная с этой контрольной точки.

Например, если $$$n = 4$$$ и контрольные точки расположены на $$$1$$$-м и $$$3$$$-м уровнях. Игрок начинает на $$$1$$$-м уровне. Если он проигрывает на $$$1$$$-м уровне, ему требуется снова проходить $$$1$$$-й уровень, потому что контрольная точка на $$$1$$$-м уровне это последняя активированная контрольная точка. Если игрок проходит $$$1$$$-й уровень, он двигается на $$$2$$$-й уровень. Если он проигрывает на нем, он отправляется обратно на $$$1$$$-й уровень. Если он проходит $$$1$$$-й уровень и $$$2$$$-й уровень, он отправляется на $$$3$$$-й уровень и активирует контрольную точку на $$$3$$$-м уровне. Теперь если он проиграет на $$$3$$$-м уровне, или на $$$4$$$-м уровне после прохождения $$$3$$$-го, он отправится обратно на $$$3$$$-й уровень. Если он пройдет и $$$3$$$-й уровень, и $$$4$$$-й, он выиграет игру.

Gildong хочет, чтобы сложности уровней были одинаковы. Он просит вас найти любую систему уровней и контрольных точек используя не больше чем $$$2000$$$ уровней, чтобы математическое ожидание количества попыток на всех уровней (до прохождения игры) было равно $$$k$$$, для игрока, который проходит каждой уровень с вероятностью $$$\cfrac{1}{2}$$$.

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

Каждый тест состоит из одного или нескольких наборов входных данных. В первой строке записано количество наборов входных данных $$$t$$$ ($$$1 \le t \le 50$$$).

Каждый набор входных данных состоит из ровно одной строки. В строке записано одно целое число $$$k$$$ ($$$1 \le k \le 10^{18}$$$) — математическое ожидание суммарного числа попыток по всем уровням, которое Gildong хочет получить для игрока, который проходит каждый уровень с вероятностью $$$\cfrac{1}{2}$$$.

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

Для каждого набора входных данных, выведите $$$-1$$$, если невозможно построить такую систему уровней и контрольных точек с не более чем $$$2000$$$ уровней.

Иначе, выведите две строки. В первой строке должно быть записано одно целое число $$$n$$$ ($$$1 \le n \le 2000$$$) — количество уровней. Во второй строке должны быть записаны $$$n$$$ целых чисел, $$$i$$$-е из них описывает, установлена ли контрольная точка в $$$i$$$-м уровне. $$$i$$$-е число должно быть $$$0$$$, если $$$i$$$-й уровень не содержит контрольную точку, и $$$1$$$, если содержит. Обратите внимание, что первое число должно быть равно $$$1$$$, согласно условию.

Пример
Входные данные
4
1
2
8
12
Выходные данные
-1
1
1
4
1 1 1 1
5
1 1 0 1 1
Примечание

В первом и втором наборе входных данных, можно видеть, что самая простая конструкция имеет только $$$1$$$ уровень с контрольной точкой. Это требует $$$2$$$ попытки прохождения, поэтому невозможно построить конструкцию с $$$1$$$ попыткой.

В третьем наборе входных данных, это занимает $$$2$$$ попытки в среднем чтобы пройти каждый уровень, и игрок всегда может повторить уровень без откатывания не прошлые уровни. Таким образом, математическое ожидание равно $$$8$$$. Обратите внимание, что есть решения с меньшим количеством уровней, но вам не требуется минимизировать их количество.