Галя играет в одномерный морской бой на поле размера 1 × n. В этой игре на клеточном поле расположены a кораблей, каждый состоит из b последовательных клеток. При этом одна клетка не может являться частью более чем одного корабля, однако, корабли могут соприкасаться.
Гале неизвестно положение кораблей. Галя может делать выстрелы по клеткам, при этом после каждого выстрела ей сообщается, является эта клетка частью какого-нибудь корабля (в таком случае считается, что Галя «попала»), или нет (тогда Галя «промахнулась»).
Галя уже сделала k выстрелов и все из них были промахами.
Перед вами стоит задача определить минимальное количество позиций, выстрелив в которые, Галя гарантированно попадет хотя бы в один из кораблей.
Гарантируется, что существует хотя бы одна расстановка кораблей, удовлетворяющая описанным условиям.
Выходные данные
В первую строку выведите минимальное количество позиций, выстрелив в которые, Галя гарантированно попадёт хотя бы в один из кораблей.
Во вторую строку выведите позиции, в которые Галя должна стрелять.
Каждая позиция должна быть выведена ровно один раз. Позиции разрешается выводить в произвольном порядке. Позиции пронумерованы с 1 до n, начиная с самой левой.
Если существует несколько решений, выведите любое из них.
Примечание
В первом примере известно, что остался один корабль длины два. Он может располагаться как слева от уже сделанного выстрела (символа «1»), так и справа. Таким образом, чтобы наверняка попасть в него, надо произвести два выстрела: один в левую часть, другой в правую.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 1 2 1
00100
|
2
4 2
|
|
2
|
13 3 2 3
1000000010001
|
2
7 11
|