Fibonacci haters` nim 3. Return of Peter
Містер Хамстер ненавидить Фібоначчі. І не лише самого математика, але й усе, що з ним пов'язано. Особливо він ненавидить числа Фібоначчі. Нагадаємо, що числа Фібоначчі задаються за наступним правилом:
f_{0 }= a;
f_{1 }= b;
f_{i }= f_{i-1 }+ f_{i-2}, i ≥ 2.
А ще містер Хамстер обожнює грати у нім. Він навіть проводить змагання з німу у себе в сараї. І, звичайно ж, він не потерпить у своїй будівлі хід, на якому хтось бере число каменів, рівне якомусь з чисел Фібоначчі, нехай навіть цей хід принесе перемогу. Сьогодні містер Хамстер вирішив зіграти з маленьким Петею – він розклав на столі N купок німа і надав хлопчику право першого ходу. Але містер Хамстер забув, що у Петі є суперздатність постійно запитувати: "А якщо я виберу купки з номерами від l до r включно, і ми будемо грати, з яких купок я змогу взяти камені так, щоб здійснити виграшний хід?" Оскільки питань дуже багато, а містер Хамстер ненавидить програмування із-за дитячої психологічної травми (учитель інформатики заставляв його обчислювати числа Фібоначчі), то відповідати на питання доведеться вам. Спішіть, а то містер Хамстер зненавидить і вас!
Вхідні дані
У першому рядку йде 3 числа: a, b та N (1 ≤ a, b ≤ 20, 1 ≤ N ≤ 10^5). Другий рядок містить розмври купок b_{i }(1 ≤ b_{i }≤ 10^6). У третьому рядку знаходиться число M (1 ≤ M ≤ 10^5) – кількість питань Петі. Наступні M рядків містять пари чисел l_i, r_{i }(1 ≤ l_{i }≤ r_{i }≤ N) – проміжок, на якому пропонує вибрати купки Петя під час чергового запитання.
Вихідні дані
На кожен запит виведіть у окремому рядку єдине ціле число – кількість купок, з яких можна забрати камені так, щоб обіграти містера Хамстера.