Вам задан набор Y из n различных целых положительных чисел y1, y2, ..., yn.
Назовём набор X из n различных целых положительных чисел x1, x2, ..., xn генератором для Y, если из набора X можно получить набор Y, применяя к элементам набора X следующие две операции:
- Умножить произвольное число xi на два, то есть заменить xi на 2·xi.
- Умножить произвольное число xi на два и прибавить единицу, то есть заменить xi на 2·xi + 1.
Обратите внимание, не требуется, чтобы все числа в наборе X были различны после выполнения каждой операции.
Наборы в данной задаче сравниваются как множества чисел. Другими словами, два набора различных чисел X и Y совпадают, если, выписав оба набора в отсортированном порядке, мы получим одинаковые массивы.
Заметьте, что любой набор чисел (или его перестановка) сам является одним из своих генераторов.
По заданному набору Y найдите его генератор, в котором максимальное число минимально.
Выходные данные
Выведите n чисел — генератор для заданного набора Y, в котором максимальное число как можно меньше. Если подходящих наборов несколько, разрешается вывести любой из них.