Мистер Хамстер ненавидит Фибоначчи. И не только самого математика, но и всё, что с ним связано. Особенно он ненавидит числа Фибоначчи. Напомним, что числа Фибоначчи задаются по следующему правилу: \textbf{f_\{0 \}= a;} \textbf{f_\{1 \}= b;} \textbf{f_\{i \}= f_\{i-1 \}+ f_\{i-2\}, i} ≥ \textbf{2.} А ещё мистер Хамстер обожает играть в ним. Он даже проводит соревнования по ниму у себя в сарае. И, конечно же, он не потерпит в своём доме ход, на котором кто-то берёт число камней, равное какому-то из чисел Фибоначчи, пусть даже этот ход принесёт победу. Сегодня мистер Хамстер решил сыграть с маленьким Петей -- он разложил на столе \textbf{N} кучек нима и предоставил мальчику право первого хода. Но мистер Хамстер забыл, что у Пети есть суперспособность постоянно спрашивать: "\textit{А если я выберу кучки с номерами от }\textit{\textbf{l}}\textit{ до }\textit{\textbf{r}}\textit{ включительно, и мы будем играть, из каких кучек я смогу взять камни так, чтобы совершить выигрышный ход?}" Поскольку вопросов очень много, а мистер Хамстер ненавидит программирование из-за детской психологической травмы (учитель информатики заставлял его вычислять числа Фибоначчи), то отвечать на вопросы придётся вам. Спешите, а то мистер Хамстер возненавидит и вас! \InputFile В первой строке следуют \textbf{3} числа: \textbf{a}, \textbf{b} и \textbf{N} (\textbf{1} ≤ \textbf{a}, \textbf{b} ≤ \textbf{20}, \textbf{1} ≤ \textbf{N} ≤ \textbf{10^5}). Вторая строка содержит размеры кучек \textbf{b}_\{i \}(\textbf{1} ≤ \textbf{b}_\{i \}≤ \textbf{10^6}). В третьей строке находится число \textbf{M} (\textbf{1} ≤ \textbf{M} ≤ \textbf{10^5}) -- количество вопросов Пети. Последующие \textbf{M} строк содержат пары чисел \textbf{l_i}, \textbf{r}_\{i \}(\textbf{1} ≤ \textbf{l}_\{i \}≤ \textbf{r}_\{i \}≤ \textbf{N}) -- промежуток, на котором предлагает выбрать кучки Петя во время очередного вопроса. \OutputFile На каждый запрос выведите в отдельной строке единственное целое число -- количество кучек, из которых можно забрать камни так, чтобы обыграть мистера Хамстера.