Это интерактивная задача.
Джон и его воображаемый друг играют в игру. По кругу расположено \(n\) лампочек. Лампочки пронумерованы от \(1\) до \(n\) по часовой стрелке, то есть, лампочки \(i\) и \(i + 1\) являются соседними для любого \(i = 1, \ldots, n - 1\), а также соседними являются лампочки \(n\) и \(1\). Исходно все лампочки выключены.
Джон и его друг ходят по очереди, начиная с Джона. Джон в качестве своего действия может завершить игру либо сделать ход. Чтобы сделать ход, Джон выбирает положительное число \(k\) и может включить любые \(k\) лампочек на свой выбор. Его друг в ответ может выбрать любые \(k\) подряд идущих лампочек и выключить их (выбранные лампочки, которые уже были выключены, остаются выключенными), где \(k\) равно числу, которое выбрал Джон на последнем ходу. Например, если \(n = 5\) и Джон только что включил три лампочки, то его друг может выключить лампочки \(1, 2, 3\), или \(2, 3, 4\), или \(3, 4, 5\), или \(4, 5, 1\), или \(5, 1, 2\).
После этого Джон снова может завершить игру или сходить, и так далее. Однако, Джон не может сделать более \(10^4\) ходов.
Джон хочет максимизировать количество включенных лампочек, а его друг хочет минимизировать это количество. Ваша задача — предъявить стратегию за Джона, которая достигает оптимального результата. Ваша программа будет играть за Джона против программы жюри, которая играет за его друга.
Пусть в игре \(n\) лампочек. Обозначим \(R(n)\) количество включенных лампочек в конце игры, если оба игрока действуют оптимально. Ваша программа должна сделать не более \(10^4\) ходов и завершить игру не менее чем с \(R(n)\) включенными лампочками. Детали реализации приведены в секции «Протокол взаимодействия».
По техническим причинам взломы по этой задаче невозможны.
Протокол взаимодействия
Исходно ваша программа получит на вход одно целое число \(n\) (\(1 \leq n \leq 1000\)) — количество лампочек в игре. После этого программа жюри будет ожидать ваших действий.
Чтобы сделать ход, выведите в одной строке целое число \(k\) (\(1 \leq k \leq n\)), а зачем \(k\) различных целых чисед \(l_1, \ldots, l_k\) (\(1 \leq l_i \leq n\)) — номера лампочек, которые вы хотите включить. Индексы можно выводить в любом порядке. Можно пытаться включать лампочки, которые уже включены (в таком случае их состояние не изменится).
Если ваш ход по какой-либо причине некорректен, или вы совершили более \(10^4\) ходов, программа жюри выведет одно число \(-1\). В противном случае, программа жюри выведет одно целое число \(x\) (\(1 \leq x \leq n)\). Это означает, что в ответ были выключены \(k\) лампочек, начиная с лампочки номер \(x\) в порядке по часовой стрелке.
Чтобы вместо следующего хода завершить игру, выведите в отдельной строке одно число \(0\). Тест будет пройден, если в этот момент включено не менее \(R(n)\) лампочек (значение \(R(n)\) и полученный вердикт не будут сообщены вашей программе). Это действие не включается в количество сделанных ходов (то есть, разрешается завершить игру после ровно \(10^4\) ходов).
Чтобы получить правильный вердикт, ваша программа должна завершиться сразу, как только выведет \(0\) либо получит ответ \(-1\).
Не забудьте сбросить буфер вывода после каждого действия.
Примечание
Если \(n = 3\), любой ход Джона может быть отменен обратно, поэтому \(R(3) = 0\) и завершить игру сразу является верной стратегией.
\(R(4) = 1\), и одна из стратегий, которая достигает этого результата, приведена во втором примере.
Пустые строки в примерах взаимодействия приведены для наглядности, в решении их выводить не нужно.