Fibonacci haters` nim 3. Return of Peter#5988
Sign in

Fibonacci haters` nim 3. Return of Peter

5 seconds
256 megabytes
Medium

Mr. Hamster hates Fibonacci. Not only the mathematician himself, but everything associated with him. He especially hates the Fibonacci numbers. Recall that Fibonacci numbers are defined as follows:

\begin{align*} f_0 &= a; \\ f_1 &= b; \\ f_i &= f_{i-1} + f_{i-2}, \quad i \ge 2. \end{align*}

In addition, Mr. Hamster loves playing Nim. He even organizes Nim tournaments in his shed. Naturally, he refuses to tolerate a move in which someone takes as many stones as a Fibonacci number, even if that move brings victory.

Today, Mr. Hamster decided to play Nim with little Petya. He arranged heaps of Nim on the table and gave the boy the right to make the first move. However, Mr. Hamster forgot that Petya has a superpower: he can always ask, "If I choose heaps numbered from to inclusive, and we play the game, from which heaps can I make a move to guarantee a win?"

Since there are too many queries, and Mr. Hamster hates programming because of childhood psychological trauma (his informatics teacher made him compute Fibonacci numbers), you have to answer the queries for him. Hurry, or Mr. Hamster will start hating you, too!

Input

The first line contains three integers: , , and (1 \le a, b \le 20, 1 \le N \le 10^5).

The second line contains integers b_i (1 \le b_i \le 10^6) — the sizes of the heaps.

The third line contains a single integer (1 \le M \le 10^5) — the number of Petya's queries.

Each of the following lines contains two integers l_i, r_i (1 \le l_i \le r_i \le N) — the indices of heaps Petya selects for the -th query.

Output

For each query, output on a separate line a single integer — the number of heaps from which it is possible to take stones to beat Mr. Hamster.

Examples

Example 1

Loading
Loading