H. Фибоначчиеватость II
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Фибоначчиеватый потенциал массива 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-е из которых должно быть равно фибоначчиеватому потенциалу итого отрезка массива.

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

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

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