Задача E. Минимизация числа ≡

Условие

У вас есть число N. А также есть число M, изначально равное нулю.

Вы можете выполнять следующие операции:

1. Прибавить к M единицу (+)
2. Отнять от M единицу (-)
3. Умножить M на 2 (*)
4. Поделить M нацело 2 (/)

Вы можете сделать до K таких операций, после чего вычисляется число, равное побитовому исключающему "или" (xor) чисел N и M.

Выведите минимальное число, которое возможно получить.

Формат входных данных

Первая строка ввода содержит число K.

Вторая строка содержит число n записанное в двоичной системе счисления.

Формат выходных данных

Выведите битовую запись полученного числа, без ведущих нулей.

Ограничения

0 ≤ N ≤ 2¹⁰⁵

0 ≤ k ≤ 2 * 10⁵

Примечание:

Нельзя использовать операцию 2, если M = 0.

Примеры тестов

15
1000001111011011

1000000000000001

Разбор

Для начала нужно понять, что деление на 2 вообще не принесёт пользы, а вот вычитание может.

Последовательность из h; единиц можно получить следующим образом: h − 1 раз прибавить единичку и умножим на 2, а после этого один раз прибавить единичку. На это потратим (h-1)*2 + 1 операцию.

Но также h единиц можно получить следующим образом:

Прибавить единичку, после чего h раз умножить на 2. И в конце вычесть единичку. Так мы потратим h + 2 операций. Это выгоднее уже при h > 2.

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

Тут важно понимать, что если мы создали блока из единиц и сдвинули его куда-то дальше, то чтобы поставить 1 на любую позицию правее (ближе к началу битовой записи) нам нужно только 1 операция.

Для прохождения примера теста можно воспользоваться следующей последовательностью команд: +****-**+*+**+*