小B 有一个长为 n 的整数序列 a，值域为 [1,k]。  

他一共有 m 个询问，每个询问给定一个区间 [l,r]，求：  

\sum\limits_{i=1}^k c_i^2

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

小B请你帮助他回答询问。

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

第二行 n 个整数，表示 小B 的序列。

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

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

对于 100\% 的数据，1\le n,m,k \le 5\times 10^4。