I. 区间和

给定一长度为n的正整数序列 ${a_n}$，其中最大的数不超过 $m$。给出 $q$ 个询问，每次询问子区间 $l_i$ 到 $r_i$，要求你计算 $\sum_{x=1}^m{min(count_x,x)\times x}$ 的值，其中 $count_x$ 表示 $x$ 在子区间 $l_i$ 到 $r_i$ 的出现次数。

第一行一个整数 $T(1\leq T\leq 3)$ 代表数据组数。 每组数据第一行三个数字 $n,m,q(1\leq n,m,q\leq 5*10^5)$。 下面一行 $n$ 个数字 第 $i$ 个数字代表 $a_i$。 接下来 $q$ 行，每行两个数 $l_i,r_i(1\leq l_i \leq r_i \leq n)$ 表示每个询问。

每组数据 $q$ 行,代表每个询问的结果。

输入样例

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

输出样例

6
11
6
1
14