Олимпиадный тренинг

Задача . H. Фибоначчиеватость II


Задача

Темы: реализация Структуры данных *3100

Яшу надоело искать самую длинную фибоначчиеватую последовательность, и он придумал себе новое развлечение — вычисление фибоначчиеватых потенциалов.

Фибоначчиеватый потенциал массива ai вычисляется следующим образом:

  1. Удалить все элементы j, такие что существует i < j, для которого ai = aj.
  2. Упорядочить оставшиеся элементы в порядке возрастания, то есть a1 < a2 < ... < an.
  3. Вычислить потенциал как P(a) = a1·F1 + a2·F2 + ... + an·Fn, где Fi означает i-е число Фибоначчи (смотрите примечания для уточнения).

Вам дан массив ai длины n и q отрезков с lj по rj. Для каждого такого отрезка j требуется вычислить фибоначчиеватый потенциал массива bi, составленного из элементов ai с lj по rj включительно. Вычислите эти значения по модулю m.

Входные данные

В первой строке входных данных записаны целые числа n и m (1 ≤ n, m ≤ 30 000) — длина массива и модуль, по которому требуется производить вычисления, соответственно.

В следующей строке записаны n целых чисел ai (0 ≤ ai ≤ 109) — элементы массива.

Далее следует число отрезков q (1 ≤ q ≤ 30 000).

Последние q строк содержат пары индексов lj и rj (1 ≤ lj ≤ rj ≤ n) — отрезки, на которых следует вычислить фибоначчиеватый потенциал.

Выходные данные

Выведите q целых чисел, i-е из которых должно быть равно фибоначчиеватому потенциалу итого отрезка массива.

Примечание

В данной задаче числа Фибоначчи определяются следующим образом:

  1. F1 = F2 = 1.
  2. Fn = Fn - 1 + Fn - 2 для всех n > 2.

Примеры
№Входные данныеВыходные данные
1 5 10
2 1 2 1 2
2
2 4
4 5 
3
3

time 5000 ms
memory 512 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет