P2709 [Template] Mo's Algorithm / Xiao B's Queries

Xiao B has an integer sequence $a$ of length $n$, with values in $[1, k]$. He has $m$ queries. For each query, given an interval $[l, r]$, compute: $$\sum\limits_{i=1}^k c_i^2$$ where $c_i$ denotes the number of occurrences of the number $i$ in $[l, r]$. Please help Xiao B answer the queries.

The first line contains three integers $n, m, k$. The second line contains $n$ integers, representing Xiao B's sequence. Each of the next $m$ lines contains two integers $l, r$.

Output $m$ lines. Each line contains one integer, which is the answer to a query.

Constraints For $100\%$ of the testdata, $1 \le n, m, k \le 5 \times 10^4$. Translated by ChatGPT 5