Программист Петров, впервые отправившийся на соревнования за пределы родного вуза, вдруг понял, как плохо работать на чужом компьютере, где даже нет любимого текстового редактора. А тут еще жюри подсунуло текст, отформатированный какой-то противным DOSовским текстовым редактором так, чтобы правые концы строк были одинаковыми. Способ форматирования был использован тот самый, единственно доступный в этом редакторе — где ни попадя были добавлены лишние пробелы. Читать такой текст — одно мучение. Хорошо еще, что на сетевом диске нашелся FAR Manager, а с помощью него все эти противные пробелы можно быстро вырезать, заменяя комбинацию из двух пробелов на один. Правда, пробелов много, и такую операцию придется повторить несколько раз — ведь после замены FAR уже не ищет заменяемую комбинацию в обработанном тексте. Поэтому, если пробелов было подряд шесть штук, то заменять два пробела на один придется трижды. Шесть пробелов заменятся на три, три на два, два на один.

Петров уже нажал Ctrl+F7, но вдруг задумался — а может, надо заменять не два пробела на один, а сначала по три на один, а уже потом два на один? Для текста, где встречается не более пяти пробелов выйдет не хуже, а вот если пробелов может быть до десяти, то одну замену удастся сэкономить! Петров — настоящий программист, и врожденная тяга к оптимизации взяла свое. Диалог замены так и остался на мониторе, текст забыт, а Петров схватил карандаш и начал покрывать поля «Кнута» какими-то формулами. Вот ведь странный человек, вместо того чтобы заменять пробелы, сидит и что-то дифференцирует…

Если и вам мешают пробелы, попробуйте найти свой способ самой быстрой замены. Предположим, что в тексте есть подстроки длиной не более чем в L пробелов (могут встречаться строки пробелов любой длины от 1 до L). Ваша задача — определить минимальное количество замен, исправляющих группы подряд идущих пробелов на один, и составить план проведения таких замен. Если таких планов несколько, то вы должны выбрать среди них оптимальный — такой, который позволяет заменить любую последовательность пробелов длины не более K (K ≥ L) для максимально возможного K. Если есть несколько оптимальных планов замены, можете вывести любой из них.

Единственная строка содержит число L, L < 2000000 — максимальная длина группы пробелов, которая встречается в тексте.

Выведите R — минимальное число замен, а в следующих R строках должен быть описан оптимальный план проведения замен. Каждая из этих строк должна содержать длину группы пробелов, которые будут заменены на один в ходе соответствующей замены.