E - 暗号化(Encipherment)

Time Limit: 4 sec / Memory Limit: 256 MB

問題文

kagamizは, ハッシュについて勉強をしている.
kagamizはローリングハッシュについて蟻本で学び, ハッシングが文字列探索に有効な手法だということを知った.

そこで, kagamizは, 任意の多重集合についてハッシングすることが出来ないかということを考え, 以下のようなハッシュ関数を考案した.


Pを素数とする. ハッシュ化する列を {x_1,x_2,x_3,...,x_n} とし, 全ての x_iについて, j≦iかつ x_j=x_iが成り立つような jの個数をC_iとすると,
(ハッシュ値) = Σx_i^{C_i} mod P

このハッシュ関数は容易に衝突ケースが作れてしまうが, ともかくこの関数を用いた以下の問題をあなたに解かせることにした.

問題: 長さNの数列{a_1,a_2,a_3,...,a_N} がある. この数列の Q 個の部分列について, それぞれ前述のハッシュ値を求めなさい.


入力

N Q P
a_1 a_2 ... a_N
s_1 t_1
s_2 t_2
.
.
.
s_Q t_Q
最初に数列の長さ N , ハッシュ値を求めたい連続した部分列の個数 Q , 素数 P が与えられる.
次に, 長さ N の数列 {a_1,a_2,..,a_N} が与えられる.
最後に, Q個の部分列の端点[s_i, t_i]が与えられる.

出力

Q個の部分列に対して, 数列中で s≦i≦t を満たす項に対して, 問題文のハッシュ関数を用いて得たハッシュ値を改行区切りで出力せよ.

制約

  • 1 ≦ N ≦ 10^5 数列の長さ
  • 1 ≦ Q ≦ 10^5 ハッシュ値を求めたい連続した部分列の個数
  • 1 ≦ P ≦ 10^9 ハッシュ関数で用いる素数
  • 1 ≦ a_i ≦ 10^6 数列の各項の値
  • 1 ≦ s_i ≦ t_i ≦ N  各部分列の端点

部分点

配点の 20% 分については, i≠jのときa_i≠a_j を満たす.


入力例 1

10 10 8999
2 1 1 2 1 2 1 2 1 2
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10

出力例 1

2
3
4
8
9
17
18
34
35
67

入力例 2

6 6 2
1 2 3 4 5 6
1 2
2 3
3 4
4 4
5 5
6 6

出力例 2

1
1
1
0
1
0
(Story) kyuridenamida
(Problem) kyuridenamida
(Tester) fura2

kyuridenamida「ところでこの問題文, 全然暗号化じゃないですよね.」