Нім для ненависників Фібоначчі 3. Повернення Петра#5988

Нім для ненависників Фібоначчі 3. Повернення Петра

5 секунд

256 мегабайтів

Середня

Містер Хамстер ненавидить Фібоначчі. І не лише самого математика, а й усе, що з ним пов'язано. Особливо він ненавидить числа Фібоначчі. Нагадаємо, що числа Фібоначчі задаються за таким правилом:

f_{0} f_{1} f_{i} = a; = b; = f_{i - 1} + f_{i - 2}, i \geq 2.

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

Окрім того, містер Хамстер обожнює грати у Нім. Він навіть проводить змагання з Німу у себе в сараї. І, звісно, він не потерпить у своєму домі ходу, у якому хтось бере стільки каменів, скільки якесь із чисел Фібоначчі, навіть якщо цей хід приведе до перемоги.

Сьогодні містер Хамстер вирішив зіграти з маленьким Петром — він розклав на столі $N$ купок Німу і дозволив хлопчику зробити перший хід. Але містер Хамстер забув, що у Петра є суперздібність: він завжди може запитати: «Якщо я виберу купки з номерами від $l$ до $r$ включно, і ми будемо грати, з яких купок я можу взяти камені для переможного ходу?»

Оскільки запитань надто багато, а містер Хамстер ненавидить програмування через дитячу психологічну травму (учитель інформатики змушував його обчислювати числа Фібоначчі), відповідати на запитання маєте ви. Покваптеся, інакше містер Хамстер зненавидить й вас!

Вхідні дані

У першому рядку міститься три числа: $a$ , $b$ та $N$ ( $1 \leq a, b \leq 20$ 1 \leq a, b \leq 20, $1 \leq N \leq 1 0^{5}$ 1 \leq N \leq 10^5).

Другий рядок містить $N$ чисел $b_{i}$ b_i ( $1 \leq b_{i} \leq 1 0^{6}$ 1 \leq b_i \leq 10^6) — розміри купок.

У третьому рядку зазначено одне число $M$ ( $1 \leq M \leq 1 0^{5}$ 1 \leq M \leq 10^5) — кількість запитань від Петра.

Кожен з наступних $M$ рядків містить два числа $l_{i}$ l_i, $r_{i}$ r_i ( $1 \leq l_{i} \leq r_{i} \leq N$ 1 \leq l_i \leq r_i \leq N) — індекси купок, які Петро обирає для $i$ -го запиту.

Вихідні дані

Для кожного запиту виведіть в окремому рядку одне ціле число — кількість купок, з яких можна взяти камені, щоб перемогти містера Хамстера.

Приклади

Приклад 1