eolymp
bolt
Try our new interface for solving problems
Məsələlər

Fibonacci haters` nim 3. Return of Peter

Fibonacci haters` nim 3. Return of Peter

Zaman məhdudiyyəti 5 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Мистер Хамстер ненавидит Фибоначчи. И не только самого математика, но и всё, что с ним связано. Особенно он ненавидит числа Фибоначчи. Напомним, что числа Фибоначчи задаются по следующему правилу:

f_{0 }= a;

f_{1 }= b;

f_{i }= f_{i-1 }+ f_{i-2}, i2.

А ещё мистер Хамстер обожает играть в ним. Он даже проводит соревнования по ниму у себя в сарае. И, конечно же, он не потерпит в своём доме ход, на котором кто-то берёт число камней, равное какому-то из чисел Фибоначчи, пусть даже этот ход принесёт победу. Сегодня мистер Хамстер решил сыграть с маленьким Петей – он разложил на столе N кучек нима и предоставил мальчику право первого хода. Но мистер Хамстер забыл, что у Пети есть суперспособность постоянно спрашивать: "А если я выберу кучки с номерами от l до r включительно, и мы будем играть, из каких кучек я смогу взять камни так, чтобы совершить выигрышный ход?" Поскольку вопросов очень много, а мистер Хамстер ненавидит программирование из-за детской психологической травмы (учитель информатики заставлял его вычислять числа Фибоначчи), то отвечать на вопросы придётся вам. Спешите, а то мистер Хамстер возненавидит и вас!

Giriş verilənləri

В первой строке следуют 3 числа: a, b и N (1a, b20, 1N10^5). Вторая строка содержит размеры кучек b_{i }(1b_{i }≤ 10^6). В третьей строке находится число M (1M10^5) – количество вопросов Пети. Последующие M строк содержат пары чисел l_i, r_{i }(1l_{i }≤ r_{i }≤ N) – промежуток, на котором предлагает выбрать кучки Петя во время очередного вопроса.

Çıxış verilənləri

На каждый запрос выведите в отдельной строке единственное целое число – количество кучек, из которых можно забрать камни так, чтобы обыграть мистера Хамстера.

Nümunə

Giriş verilənləri #1
2 1 5
1 2 3 4 5
3
1 5
1 4
2 5
Çıxış verilənləri #1
1
0
1

Müəllif Олег Петров
Mənbə Летняя школа Севастополь 2013, Волна 2, День 6