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

通过次数

13

提交次数

21

Time Limit : 1 秒
Memory Limit : 128 MB

有一个长为 nn 的整数序列 aa，值域为 [1,k][1,k]。
他一共有 mm 个询问，每个询问给定一个区间 [l,r][l,r]，求： ∑i=1kci2\sum\limits_{i=1}^k c_i^2

其中 cic_i 表示数字 ii 在 [l,r][l,r] 中的出现次数。

Input

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

第二行 nn 个整数，表示序列。

接下来的 mm 行，每行两个整数 l,rl,r。

Output

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

Examples

Input
复制

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

Output
复制

6
9
5
2

Hint

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

上一题 下一题
请先登陆