题目描述

小 B 有一个序列，包含 $n$ 个 $1 \sim k$ 之间的整数。他一共有 $m$ 个询问，每个询问给定一个区间 $[L,R]$，求 $\sum c_i^2$ 的值，其中 $i$ 的值从 $1$ 到 $k$，其中 $c_i$ 表示数字 $i$ 在 $[L,R]$ 中的重复次数。小 B 请你帮助他回答询问。

输入格式

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

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

接下来的 $m$ 行，每行两个整数 $L,R$。

输出格式

$m$ 行，每行一个整数，其中第 $i$ 行的整数表示第 $i$ 个询问的答案。

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

6
9
5
2

数据规模与约定

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