Задача A. Alternating Binary Sequence ≡

Условие

Формируется бесконечная последовательность бинарных строк s[1], s[2], s[3], … по следующему правилу:

Для всех k, строка s[k] строится путем конкатенации (соединения) чередующихся блоков цифр.

А именно:

• Если k — нечетное, строка начинается с 0, после которого следует 1, затем 0, затем 11, затем 0, затем 111, и так далее. Каждый следующий блок единиц на одну единицу длиннее предыдущего. Общая длина строки равна k.
• Если k — четное, строка начинается с 1, после которого следует 0, затем 1, затем 00, затем 1, затем 000, и так далее. Каждый следующий блок нулей на один нуль длиннее предыдущего. Общая длина строки равна k.

Первые 10 строк выглядят так:

0
10
010
1010
01011
101001
0101101
10100100
010110111 
1010010001

Вам дано число n. Ваша задача — найти и вывести строку s[n].

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

Первая строка входных данных содержит одно целое число n.

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

Выведите одну строку длины n в соответствии с правилами описанными в условии.

Ограничения

1 ≤ n ≤ 10⁵

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

1

0

5

01011

11

01011011101