Problem A. Alternating Binary Sequence ≡

Statement

Let there be an infinite sequence of binary strings s[1], s[2], s[3], …. Each string is obtained as follows:

For each k, string s[k] is a concatenation of altering blocks of digits.

In particular:

• If k is odd then the string starts with 0, followed by 1, then 0, then 11, then 0, then 111, and so on. Thus, each block of ones is one symbol longer than the previous one. The total length of the string is equal to k.
• If k is even then the string starts with 1, followed by 0, then 1, then 00, then 1, then 000, and so on. Thus, each block of zeros is one symbol longer than the previous one. The total length of the string is equal to k.

The first 10 strings are:

0
10
010
1010
01011
101001
0101101
10100100
010110111 
1010010001

Given an integer n find and output the string s[n].

Input format

The first line of the input contains a single integer n.

Output format

Output a single string of length n as described in the problem statement.

Constraints

1 ≤ n ≤ 10⁵

Sample tests

1

0

5

01011

11

01011011101

Problem B. Badger ≡

Statement

A badger is hiding in its complicated burrow, which is a long straight tunnel. The borrow is separated into N consecutive chambers, numbered 1 through N. The badger is very smart and sleeps in one of the chambers each night.

A team of two hunters learned about badger's habits and came up with a shrewd plan. Each night they will check the chambers with a certain step. In particular, on night i they check all the chambers with numbers divisible by A_i or B_i.

The badger will be caught if at least one hunter will check a chamber that it is sleeping in.

Your task is to find the number of safe chambers for the night i, i.e. chambers that the badger can sleep in without any of the hunters finding it.

Input format

The first line of the input contains two integers N and K — the number of chambers in the borrow and the number of nights.

The following K lines each contain two integers A_i, B_i — step size of each of the hunters.

Output format

Output K integers — numbers of safe chambers in the badger's borrow for each of the nights.

Constraints

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

Sample tests

10 2
2 3
1 4

3
0

100 3
2 3
3 15
17 19

33
67
90