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 включительно, и мы будем играть, из каких кучек я смогу взять камни так, чтобы совершить выигрышный ход?" Поскольку вопросов очень много, а мистер Хамстер ненавидит программирование из-за детской психологической травмы (учитель информатики заставлял его вычислять числа Фибоначчи), то отвечать на вопросы придётся вам. Спешите, а то мистер Хамстер возненавидит и вас!
Input
В первой строке следуют 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) – промежуток, на котором предлагает выбрать кучки Петя во время очередного вопроса.
Output
На каждый запрос выведите в отдельной строке единственное целое число – количество кучек, из которых можно забрать камни так, чтобы обыграть мистера Хамстера.