小B 有一个长为
n 的整数序列
a，值域为
[1,k]。
他一共有
m 个询问，每个询问给定一个区间
[l,r]，求：
∑ci2(1<=i<=k)
其中
ci 表示数字
ii 在
[l,r]中的出现次数。
小B请你帮助他回答询问。
输入格式
第一行三个整数n,m,k。
第二行 n 个整数，表示 小B 的序列。
接下来的 m 行，每行两个整数 l,r。
输出格式
输出 m 行，每行一个整数，对应一个询问的答案。
输入输出样例
说明/提示
【数据范围】
对于 100% 的数据，1≤n,m,k≤5×104。