The Macau city is referred to as the “Oriental Monte Carlo”. There are
more than thirty casinos in Macau. Every year they lure millions of
gamblers from China and from other countries. The gambling industry makes
up for about 40% of the city's GDP.
Vova learned from his friends in Guangzhou that Macau has special casinos
for programmers only. Vova found that quite interesting and he immediately
decided to visit a programmer casino. One such casino was located by Vova's
hotel, so in the evening he took some cash and went there.
Indeed, there must have been programmers sitting at the casino tables, because the
tables had no cards or pieces. Instead, each player had a notepad lying in
front of him. A player wrote some numbers in his notepad. Vova was
explained that the game goes like this. First each player writes a number
one on a clear notepad page. Then the croupier starts reading out a
sequence of zeroes and ones, one digit at a time. If the croupier reads
out a number zero, all players add a zero to the end of the last number in their
pages. And if the croupier reads out a number one, then the player can either add
this number one to the end of the last number or write it on a new line,
thus starting a new number. After the croupier stops reading out the
digits, each player converts all his binary numbers into decimals, then
glues them all into a single decimal number in the order, in which they
were recorded. The player with the minimum resulting number wins.
For example, if the croupier reads out the sequence of 1011100101, the
first player writes binary letters 1, 1011 and 100101 decimals
1, 11 and 37), and the second player writes 110, 11100 and 101
(decimal 6, 28 and 5), then the winner is the second player as 6285 is
less than 11137.
Before joining in the game, Vova decided to learn to play optimally well
for the simple case when the croupier's sequence is represented as a
binary record of all integers one by one from 2 to n (in the above given
example n was equal to five). But as Vova failed to quickly come up with the
optimal strategy, he asked you to help him.
The single line contains an integer n (2 ≤ n ≤ 100 000).
In the first line print, how many numbers Vova should write down if he
plays optimally well. In the second line print the numbers' lengths in
bits in the order they are written. If there are multiple solutions that
result in the minimum decimal number, print any of them.
In the sample you need to write down all the digits the croupier reads out
into the second number. In this case after the numbers are converted to
decimals and glued together, we get number 1741.
Problem Author: Ilya Zvigintsev
Problem Source: Open Ural FU Personal Contest 2013