Invitation Delivery in a Fibonacci Morphism

In this problem, we study a fascinating transformation process. In the beginning, there are S copies of a being called Suika (each initially "large" and denoted by B). Every second the following happens simultaneously for each element in the current sequence:

• If an element is large (B), it splits into one large and one small element – in order, the large (B) comes first and then a small (L).
• If an element is small (L), it grows into a large one (B) but does not split.

Thus, if you denote the large state by B and the small state by L, and apply the transformation rules to each element in order, then starting from a single B the first few seconds produce:

Time 0:               B
Time 1:               B L
Time 2:               B L B
Time 3:               B L B B L
Time 4:               B L B B L B L B

It can be checked that the transformation is equivalent to the following morphism on letters:

$$B \to B L, \quad L \to B.$$

Note that if we denote by \(F\) the infinite fixed point (the limit as time \(t \to \infty\)) of this morphism (starting with B), then for an initial sequence with a single B the limiting sequence is \(F\). If we start with S copies of B, the overall infinite sequence is the concatenation of S copies of \(F\).

Suika, however, wants to save energy and send invitations only using a contiguous block of the large elements (B) in the final infinite configuration. In other words, given an interval [l, r] (with 1-based indexing) on the final sequence (which is the limit of the transformation process), you are to compute how many large elements (B) there are in that interval. (Only large Suikas can deliver invitations.)

Note: Although the infinite word is obtained as a fixed point of the above morphism, it turns out that the infinite Fibonacci word \(F\) (i.e. the fixed point of the morphism) can be characterized in a cutting–sequence manner. In fact, one may show that for
\(1 \le i < \infty\), the \(i\)th character \(F[i]\) is B if and only if

$$\lfloor(i+1)p\rfloor - \lfloor ip\rfloor = 1,$$

where $$p = \frac{\sqrt{5}-1}{2}.$$

Consequently, the number \(A(n)\) of B's in the first \(n\) characters of \(F\) is given by:

$$A(n)=\lfloor (n+1)p\rfloor.$$

Since any finite segment in our infinite sequence (which, for all practical finite queries, lies entirely in the first copy of \(F\)) is identical to that in \(F\), the answer for a query [l, r] is:

$$\text{ans} = A(r) - A(l-1) = \lfloor (r+1)p \rfloor - \lfloor l\,p \rfloor. $$

You are given S (the initial number of large Suikas) and Q queries. Each query consists of two integers l and r. Output the number of deliveries (i.e. the number of B's) in the subsequence from index l to r (inclusive).

inputFormat

The input begins with a line containing two integers S and Q (1 ≤ S ≤ 10⁹, 1 ≤ Q ≤ 10⁵). (Note: Although S is given, due to the nature of the transformation, any finite interval lies in the first copy of the infinite word.)

Each of the following Q lines contains two integers l and r (1 ≤ l ≤ r ≤ 10¹⁸), representing one query.

outputFormat

For each query, output a single line containing an integer: the number of B characters in the interval [l, r].

sample

1 3
1 5
2 4
3 3

3
2
1

</p>