5303 - 第二十四章 双指针和莫队:区间数字统计

通过次数

13

提交次数

21

时间限制 : 1 秒
内存限制 : 128 MB

有一个长为 n 的整数序列 a,值域为 [1,k]
他一共有 m 个询问,每个询问给定一个区间 [l,r],求: \sum\limits_{i=1}^k c_i^2

其中 c_i 表示数字 i[l,r] 中的出现次数。

输入

第一行三个整数 n,m,k

第二行 n 个整数,表示序列。

接下来的 m 行,每行两个整数 l,r

输出

输出 m 行,每行一个整数,对应一个询问的答案。

样例

输入

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

输出

6
9
5
2

提示

【数据范围】
对于 100\% 的数据,1\le n,m,k \le 5\times 10^4