Mister Xamster Fibonaccini sevmir. Sadəcə riyaziyyatçını deyil, onunla əlaqəli hər şeyi də. O, xüsusilə Fibonacci ədədlərindən zəhləsi gedir. Xatırladaq ki, Fibonacci ədədləri aşağıdakı qayda ilə müəyyən olunur:
[ \beginalign* f_0 = a;
f_1 = b;
f_i = f_i-1 + f_i-2, i 2. \endalign* ]
Bundan əlavə, Mister Xamster Nim oyununu oynamağı çox sevir. O, hətta Nim turnirlərini öz tövləsində keçirir. Təbii ki, evində kimsə Fibonacci ədədinə bərabər sayda daş götürsə (hətta bu gediş ona qələbə gətirsə belə), buna dözməz.
Bu gün Mister Xamster balaca Petya ilə Nim oynamağa qərar verdi. O, masanın üzərinə N Nim yığını düzür və oğlana birinci gedişi etməyə icazə verir. Lakin Mister Xamster unudur ki, Petya'nın xüsusi bir bacarığı var: o həmişə soruşur: "Əgər mən yığınları l-dən r-ə kimi seçsəm və oynasaq, hansı yığından qalib gediş edə bilərəm?"
Çoxlu sual olduğu üçün və Mister Xamster uşaqlıqda aldığı psixoloji travmaya görə proqramlaşdırmanı sevmir (informatika müəllimi ona Fibonacci ədədlərini hesablamağı tapşırardı), suallara siz cavab verməlisiniz. Tələsin, yoxsa Mister Xamster sizdən də zəhləsi gedəcək!
Birinci sətrdə üç ədəd var: , və (1 \le a, b \le 20, 1 \le N \le 10^5).
İkinci sətrdə ədəd b_i (1 \le b_i \le 10^6) — yığınların ölçüləri verilib.
Üçüncü sətrdə bir ədəd (1 \le M \le 10^5) — Petya'nın sorğularının sayı verilir.
Növbəti sətrdə l_i, r_i (1 \le l_i \le r_i \le N) — Petya'nın -ci sual üçün seçdiyi yığınların indeksləridir.
Hər bir sorğu üçün, ayrılıqda sətirdə bir tam ədəd çıxışa yazın — Mister Xamsteri məğlub edə biləcək yığınların sayı.
Nümunə 1