Description

There are many items in the shop. Each item has:

• An index, from left to right as $1,2,\dots,n$.

• A category, as $p_1,p_2,\dots,p_n$.

• A value, as $v_1,v_2,\dots,v_n$.

$\mathrm{Sunny}$ wants to choose an interval and buy all gifts in this interval to give to little $\mathrm{b}$.

Little $\mathrm{b}$ will check the gifts from right to left. If she sees that gifts of the same category have appeared $k$ times, then she will not check this category anymore (including the $k$-th one). Of course, those gifts will then lose their original value.

Now, $\mathrm{Sunny}$ gives you $m$ intervals and wants you to compute, in little $\mathrm{b}$'s view, the value of each interval.

See the sample for the detailed value calculation.

Input Format

The first line contains three positive integers $n,m,k$ separated by spaces.

The second line contains $n$ positive integers separated by spaces, where the $i$-th number represents $p_i$.

The third line contains $n$ positive integers separated by spaces, where the $i$-th number represents $v_i$.

The next $m$ lines each contain two positive integers $l_i,r_i$, representing the interval of the $i$-th query.

Output Format

Output $m$ lines. For each query, output one integer $v$ in one line, the value of this interval in little $\mathrm{b}$'s view.

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

7
10
11
20
23
28
28
28
20
11
5

Hint

Sample Explanation

$[1,1]:7$.

$[1,2]:3+7=10$.

$[1,3]:8+3=11$, because the category of the gift with index $1$ is $1$, and this is the $k(k=3)$-th time category $1$ appears, so she will not check this category anymore (including this one).

$[1,4]:9+8+3=20$.

$[2,6]:5+6+9+8=28$.

$[3,6]:5+6+9+8=28$.

Constraints and Notes

Testdata $1-4$: $n\leq 100,m\leq 100$.

Testdata $5-6$: $n\leq 5000,m\leq 5000$.

Testdata $7-10$: $n\leq 2\times 10^4,m\leq 10^4$.

Testdata $11-15$: $n\leq 2\times 10^5,m\leq 2\times 10^5$.

Testdata $16-20$: $n\leq 10^6,m\leq 5\times 10^5$.

For testdata $1,2,7,8,11,12,16,17$, $k=n$. For the other testdata, $2\leq k<n$.

For all testdata, $1\leq p_i\leq n,1\leq v_i\leq 2000,1\leq l \leq r \leq n$.

For testdata $1-10$, each is worth $3$ points.

For testdata $11-20$ where $k=n$, each is worth $4$ points.

All other testdata are worth $9$ points each.

For testdata $1-6$, the time limit is $500\rm ms$.

For testdata $7-15$, the time limit is $750\rm ms$.

For testdata $16-20$, the time limit is $1.5\rm s$.

Of course, the setters of SWTR-02 cannot possibly have girlfriends.

Translated by ChatGPT 5