← 返回题目列表

Codeforces · 633/H

H. 斐波那契 II

中文机器翻译题面 查看原题

Yash 终于厌倦了计算最长斐波那契序列的长度。他现在正在研究更复杂的事物,例如斐波那契势。

数组 ai 的斐波那契势计算如下:

1. 如果存在 i < j 使得 ai = aj,则删除所有元素 j。
2. 将剩余元素按升序排序,即a1 < a2 < ... < an。
3. 将势计算为 P(a) = a1·F1 + a2·F2 + ... + an·Fn,其中 Fi 是第 i 个斐波那契数(请参阅注释以了解说明)。

给定一个长度为 n 的数组 ai,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 行包含索引对 li 和 ri (1 ≤ li ≤ ri ≤ n) - 计算斐波那契势的范围。

输出

打印 q 行,其中第 i 行必须包含第 i 个范围模 m 的斐波那契势。

示例

输入 #1

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

输出 #1

3
3

注意

出于此问题的目的,将斐波那契数定义如下:

1. F1 = F2 = 1。
2.对于每个n > 2,Fn = Fn - 1 + Fn - 2。

在第一个查询中,可以使用最小集合 {1,2} 形成子数组 [1,2,1]。因此,该子数组的势为1*1+2*​​1=3。