Задача 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

Задача B. Badger ≡

Условие

Барсук прячется в своей сложной норе, которая представляет собой длинный прямой тоннель. Нора разделена на N последовательных камер, пронумерованных от 1 до N. Барсук очень умный и каждую ночь он спит в одной из камер.

Команда из двух охотников узнала о привычках барсука и разработала хитрый план. Каждую ночь они будут проверять камеры с определённым шагом. А именно, в ночь i они проверяют все камеры, номера которых кратны числу A_i или B_i.

Барсук будет пойман, если хотя бы один охотник проверит камеру, в которой он спит.

Ваша задача — определить, сколько у барсука безопасных камер в ночь i, то есть камер, в которых он может спать, и ни один охотник его не найдёт.

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

Первая строка содержит два целых числа N и K — количество камер в норе и количество ночей.

Следующие K строк содержат по два целых чисел A_i, B_i — числа, определяющие шаг проверки для каждого охотника.

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

Выведите K целых чисел — количество безопасных камер в норе барсука по дням.

Ограничения

1 ≤ N ≤ 10⁹, 1≤K≤10⁴ 1 ≤ A_i, B_i ≤ 10⁹

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

10 2
2 3
1 4

3
0

100 3
2 3
3 15
17 19

33
67
90