题目链接

题意

给你一个长度为 $n$ 的数组，$Q$ 次询问，每次将第 $l$ 个到第 $r$ 个数取出排序去重，求最小的数 $\times fib_1+$ 次小的数 $\times fib_2+$ 第三小的数 $\times fib3...$的总和，答案对 $mod$ 取模。

输入格式

第一行两个数 $n,mod$。

接下来 $n$ 个数，表示这个数组。

然后一个数 $Q$。

接下来 $Q$ 行，每行一个询问 $l,r$。

输出格式

输出 $Q$ 行，每行一个数，表示询问的答案。

样例

5 10
2 1 2 1 2
2
2 4
4 5

3
3

数据范围

$1\le n,m,Q\le 30000$

$1\le a_i\le 10^9$