Multiple of k

本题是 P1306 的多组询问版，建议先通过P1306后再尝试本题。

时间限制：3s

空间限制：256MB

题目描述

现有长度为 \(n\) 的数列 \(a\) ，给定正整数 \(k\) ，请回答 \(q\) 次询问，每次询问给定 \(L,R\)，求所有的二元组\((i,\ j)\)的个数，使得：

• \(L\le i\le j\le R\)
• \(a_i+a_{i+1}+..+a_j\)是 \(k\) 的倍数

输入格式

第一行三个正整数 \(n,k,q\)

接下来一行包含 \(n\) 个整数，表示这个数列。

接下来 \(q\) 行每行两个整数 \(L, R\)，表示一次询问

输出格式

共 \(q\) 行，每行一个正整数，表示满足条件的二元组的个数。

样例输入1

8 2 6
1 1 1 0 1 0 1 1
1 4
1 3 
2 4
1 1
2 2
3 8

样例输出1

4
2
3
0
0
9

样例输入2

52 3 61
2 2 1 1 2 0 2 2 0 0 1 1 0 2 1 2 1 1 1 1 0 1 1 2 1 0 0 2 2 0 0 2 0 2 1 2 2 1 1 0 0 0 0 2 1 0 0 0 2 0 0 0 
8 28
9 13
10 30
27 42
20 30
18 26
38 52
7 45
42 42
23 39
17 19
36 45
18 47
21 23
3 24
17 37
21 29
11 45
3 12
34 43
16 22
48 49
50 52
2 24
33 41
12 12
41 44
15 31
8 41
18 46
23 26
24 45
17 46
30 39
11 40
44 47
12 31
4 20
11 35
7 13
25 30
12 13
14 33
19 44
49 51
30 44
32 36
19 31
27 42
21 48
1 49
18 51
20 42
9 20
7 14
12 16
35 40
1 2
28 46
13 30
43 45

样例输出2

72
4
71
48
19
12
51
263
1
49
1
24
169
1
78
72
12
217
15
24
8
1
6
87
18
0
6
48
195
154
4
99
169
15
151
6
70
48
106
7
5
1
70
121
3
40
4
26
48
156
413
212
96
22
9
6
6
0
71
55
3

数据范围及限制

\(1\le n, q\le 2*10^5, 1\le k \le 5*10^5, 0\le a_i<k\)

请注意，答案可能不在\(32\)位整数范围内。