Задача A. ЕГЭ ≡

Условие

При подготовке пакета были использованы материалы сайта школьных олимпиад по информатике.

Школьник Игорь с детства любил компьютер. Он любил на нем играть, смотреть фильмы и делать много других приятных вещей. Иногда он даже программировал на нем. И у него была мечта поступить в университет и стать программистом. Но Игорь был не очень усердным учеником, поэтому день сдачи ЕГЭ по информатике наступил для него совершенно неожиданно. А ведь без хорошего балла за ЕГЭ его мечта так и останется мечтой.

На пробном ЕГЭ ему попалось задание, которое он не знал, как решать. Задание требовало выписать семь подряд идущих символов k-ой строки, начиная с ее i-го символа. Строки строились по правилу:

• S₀ = 0
• S₁ = 01
• S₂ = 0110
• S₃ = 01101001
• S_j = S_j−1 +S_j−1, где S означает строку S, в которой все нули заменены на единицы и наоборот.

Игорь просит Вас помочь решить эту задачу.

Первая группа тестов проверяется в момент сдачи задачи на проверку и стоит 60 баллов. Баллы за эту группу начисляются только при прохождении всех тестов группы. Для всех тестов этой группы выполнено условие k ≤ 20.

Вторая группа тестов проверяется после окончания олимпиады и стоит 40 баллов. Баллы за эту группу начисляются только при прохождении всех тестов группы.

Формат входного файла

Во входном файле дано два числа — k и i (3 ≤ k ≤ 63, 1 ≤ i ≤ 2^k − 7).

Формат выходного файла

Вывести семь подряд идущих символов k-ой строки, начиная с i-го символа. Нумерация символов в строке начинается с единицы.

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

3 1

1101001

4 6

0011001