bzoj#P3781. 小B的询问

小B的询问

题目描述

小 B 有一个序列,包含 nn1k1 \sim k 之间的整数。他一共有 mm 个询问,每个询问给定一个区间 [L,R][L,R],求 ci2\sum c_i^2 的值,其中 ii 的值从 11kk,其中 cic_i 表示数字 ii[L,R][L,R] 中的重复次数。小 B 请你帮助他回答询问。

输入格式

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

第二行,nn 个整数,表示小 B 的序列。

接下来的 mm 行,每行两个整数 L,RL,R

输出格式

mm 行,每行一个整数,其中第 ii 行的整数表示第 ii 个询问的答案。

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

数据规模与约定

对于 100%100\% 的数据,1n,m,k5×1041 \le n,m,k \le 5 \times 10^4