描述

小\(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\) 行，每行一个整数，对应一个询问的答案。

样例1

输入样例1

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

输出样例1

6
9
5
2

提示

本题答案可能会超出\( 32 \)位有符号整型数的范围，例如下面这份代码生成的数据。（为测试样例\(3\)）

#include <stdio.h>

int main() {
    int n = 50000, m = 1, k = 1;
    printf("%d %d %d\n", n, m, k);
    for(int i = 1; i < n; ++i)
        printf("1 ");
    puts("1"); printf("1 50000");
    return 0;
}

正确的输出为\(2500000000\)。

限制

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