Summing Squared Frequencies

Given an integer sequence \( a_1, a_2, \dots, a_n \) of length \( n \) with each element in the range \([1, k]\), and \( m \) queries, each query provides a range \([\ell, r]\). For each query, compute the following sum:

\[ \sum_{i=1}^{k} c_i^2 \]

Here, \( c_i \) denotes the number of times the integer \( i \) appears in the subarray \( a_{\ell}, a_{\ell+1}, \dots, a_r \).

inputFormat

The first line contains three integers \( n \), \( m \), and \( k \) separated by spaces.

The second line contains \( n \) integers \( a_1, a_2, \dots, a_n \) separated by spaces.

Each of the next \( m \) lines contains two integers \( \ell \) and \( r \) representing a query.

outputFormat

For each query, output the computed sum on a separate line.

sample

5 3 3
1 2 1 3 2
1 3
2 5
1 5

5
6
9