Маленький Петя очень любит играть с маленькой Машей. Недавно мама подарила ему игру под названием «Ноль-один». Петя сразу же предложил Маше сыграть в эту игру.

Перед игрой на столе выкладывается несколько карточек в один ряд, слева направо. На каждой карточке написано число: 0 либо 1. Игроки ходят по очереди, первой ходит Маша. На каждом ходу игроку требуется взять одну карточку со стола, а все остальные карточки сдвинуть так, чтобы закрыть пустоту на месте вытянутой карточки. Например, если перед чьим-то ходом на столе карточки образовывали последовательность 01010101, то после вытягивания четвертой по счету карточки (нумерация с единицы), последовательность станет такой: 0100101.

Игра заканчивается, когда на столе остается ровно две карточки. Цифры на этих карточках задают число в двоичной системе счисления: старший бит находится слева. Цель Маши — минимизировать это число, а цель Пети — максимизировать его.

Перед самым началом игры случилась неприятность. Дети пролили сок на некоторые карточки и цифры на них расплылись. На каждой из испорченных карточек могло быть написано как число 0, так и число 1. Рассмотрим все возможные начальные расклады (до проливания сока). Для каждого из этих раскладов найдем, какие 2 карточки останутся на столе после игры, при условии, что и Петя, и Маша играют оптимально. Упорядоченная пара цифр, написанных на этих двух карточках, называется исходом игры. Ваша задача — найти множество исходов для всех возможных начальных раскладов.