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 個の部分列について, それぞれ前述のハッシュ値を求めなさい.

• 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 を満たす.

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

2
3
4
8
9
17
18
34
35
67