318. Многорукий бандит

Это интерактивная задача

Так получилось, что вы оказались в зале игровых автоматов с целым мешком жетонов. К сожалению, в кассе жетоны назад принимать отказываются, и вы решили испытать удачу.

В зале есть много автоматов, в которые вы можете играть. Для одной игры с автоматом вы используете один жетон. В случае выигрыша, автомат даёт вам один доллар, в случае проигрыша — ничего. У каждого автомата есть фиксированная вероятность выигрыша (которую вы не знаете), но у разных автоматов она разная. Изучив сайт производителя этих автоматов, вы выяснили что вероятность выигрыша у каждого автомата выбирается случайно на этапе изготовления из бета-распределения с определёнными параметрами.

Вам хочется максимизировать свой ожидаемый выигрыш.

Одно исполнение может состоять из нескольких тестов (не более 50).

Каждый тест начинается с того, что вашей программе в одной строке подаются два целых числа, разделённые пробелом: число $N$ — количество жетонов в вашем мешке, и $M$ — количество автоматов в зале ($200 \le N \le 500$, $5 \le M \le 100$). В следующей строке содержатся два вещественных числа $\alpha$ и $\beta$ ($1 \le \alpha, \beta \le 10$) — параметры бета-распределения вероятности выигрыша.

Протокол общения с проверяющей системой такой: вы делаете ровно $N$ запросов. На каждый запрос выведите в отдельную строку номер автомата, в который вы будете играть (от $1$ до $M$ включительно). В качестве ответа в отдельной строке будет стоять либо "0", либо "1", означающие соответственно проигрыш и выигрыш в игре с запрошенным автоматом.

После последнего теста вместо чисел $N$ и $M$ будут стоять два нуля.

Задача будет считаться сданной, если ваше решение не сильно хуже решения жюри. Если ваше решение будет значительно хуже решения жюри, вы получите вердикт <<неправильный ответ>>.

Гарантируется, что если ваше решение не хуже, чем решение жюри, то вероятность получить вердикт <<неправильный ответ>> не превосходит $10^{-6}$.

Ваше решение получит вердикт <<Решение зависло>> (IL), если вы не будете ничего выводить или забудете сделать операцию flush после вывода запроса.

Чтобы выполнить операцию flush, можете использовать (сразу после вывода запроса и перевода строки):

• fflush(stdout) в C++
• sys.stdout.flush() в Python

Пример взаимодействия (в данном случае $N$ не подходит под ограничения входных данных, в реальных тестах таких значений не будет):