Description

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:

where $c_i$ denotes the number of occurrences of the number $i$ in $[l, r]$.

Please help Xiao B answer the queries.

Input Format

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 Format

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

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

6
9
5
2

Hint

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

Translated by ChatGPT 5