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}\).
Выходные данные
Для каждого набора входных данных, выведите \(-1\), если невозможно построить такую систему уровней и контрольных точек с не более чем \(2000\) уровней.
Иначе, выведите две строки. В первой строке должно быть записано одно целое число \(n\) (\(1 \le n \le 2000\)) — количество уровней. Во второй строке должны быть записаны \(n\) целых чисел, \(i\)-е из них описывает, установлена ли контрольная точка в \(i\)-м уровне. \(i\)-е число должно быть \(0\), если \(i\)-й уровень не содержит контрольную точку, и \(1\), если содержит. Обратите внимание, что первое число должно быть равно \(1\), согласно условию.
Примечание
В первом и втором наборе входных данных, можно видеть, что самая простая конструкция имеет только \(1\) уровень с контрольной точкой. Это требует \(2\) попытки прохождения, поэтому невозможно построить конструкцию с \(1\) попыткой.
В третьем наборе входных данных, это занимает \(2\) попытки в среднем чтобы пройти каждый уровень, и игрок всегда может повторить уровень без откатывания не прошлые уровни. Таким образом, математическое ожидание равно \(8\). Обратите внимание, что есть решения с меньшим количеством уровней, но вам не требуется минимизировать их количество.