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。