CF633H.Fibonacci-ish II

Yash is finally tired of computing the length of the longest Fibonacci-ish sequence. He now plays around with more complex things such as Fibonacci-ish potentials.

Fibonacci-ish potential of an array a__i is computed as follows:

1. Remove all elements j if there exists i < j such that a__i = a__j.
2. Sort the remaining elements in ascending order, i.e. _a_1 < _a_2 < ... < a__n.
3. Compute the potential as P(a) = _a_1·_F_1 + _a_2·_F_2 + ... + a__n·F__n, where F__i is the i-th Fibonacci number (see notes for clarification).

You are given an array a__i of length n and q ranges from l__j to r__j. For each range j you have to compute the Fibonacci-ish potential of the array b__i, composed using all elements of a__i from l__j to r__j inclusive. Find these potentials modulo m.

亚什终于厌倦了计算最长斐波那契式序列的长度，转而研究更复杂的问题，例如斐波那契式势能（Fibonacci-ish potential）。

数组 $a_i$ 的斐波那契式势能定义如下：

1. 删除所有满足如下条件的元素 $a_j$：存在某个 $i < j$，使得 $a_i = a_j$；
2. 将剩余元素按升序排列，即 $a_1 < a_2 < \dots < a_n$；
3. 计算势能 $P(a) = a_1 \cdot F_1 + a_2 \cdot F_2 + \dots + a_n \cdot F_n$，其中 $F_i$ 表示第 $i$ 个斐波那契数（参见“注释”部分以明确其定义）。

给定一个长度为 $n$ 的数组 $a_i$，以及 $q$ 个查询区间 $[l_j, r_j]$。对每个查询 $j$，需构造子数组 $b_i$，它由 $a_i$ 中下标从 $l_j$ 到 $r_j$（含端点）的所有元素组成，并计算该子数组 $b_i$ 的斐波那契式势能。请输出所有结果对 $m$ 取模后的值。

The first line of the input contains integers of n and m (1 ≤ n, m ≤ 30 000) — the length of the initial array and the modulo, respectively.

The next line contains n integers a__i (0 ≤ a__i ≤ 109) — elements of the array.

Then follow the number of ranges q (1 ≤ q ≤ 30 000).

Last q lines contain pairs of indices l__i and r__i (1 ≤ l__i ≤ r__i ≤ n) — ranges to compute Fibonacci-ish potentials.

输入的第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 30\,000$）——分别为初始数组的长度和模数。

第二行包含 $n$ 个整数 $a_i$（$0 \leq a_i \leq 10^9$）——数组的元素。

接下来一行给出查询区间个数 $q$（$1 \leq q \leq 30\,000$）。

最后 $q$ 行每行包含一对下标 $l_i$ 和 $r_i$（$1 \leq l_i \leq r_i \leq n$）——表示需计算 Fibonacci-ish 势能的区间。

Print q lines, i-th of them must contain the Fibonacci-ish potential of the i-th range modulo m.

输出 q 行，其中第 i 行必须包含第 i 个区间对应的 Fibonacci-ish 势（模 m 意义下）。

For the purpose of this problem define Fibonacci numbers as follows:

1. _F_1 = _F_2 = 1.
2. F__n = F__n - 1 + F__n - 2 for each n > 2.

In the first query, the subarray [1,2,1] can be formed using the minimal set {1,2}. Thus, the potential of this subarray is 1*1+2*1=3.

本题中，斐波那契数列定义如下：

1. $F_1 = F_2 = 1$；
2. 对每个 $n > 2$，有 $F_n = F_{n-1} + F_{n-2}$。

在第一个查询中，子数组 $[1,2,1]$ 可由最小集合 $\{1,2\}$ 构成。因此，该子数组的势为 $1 \times 1 + 2 \times 1 = 3$。