Містер Хамстер ненавидить Фібоначчі. І не лише самого математика, але й усе, що з ним пов'язано. Особливо він ненавидить числа Фібоначчі. Нагадаємо, що числа Фібоначчі задаються за наступним правилом: \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 На кожен запит виведіть у окремому рядку єдине ціле число -- кількість купок, з яких можна забрати камені так, щоб обіграти містера Хамстера.