P5673 "SWTR-2" Picking Gifts

$\mathrm{Sunny}$ has an $npy$ called little $\mathrm{b}$. Little $\mathrm{b}$'s birthday is coming soon, and $\mathrm{Sunny}$ wants to buy her some gifts.

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.

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 $m$ lines. For each query, output one integer $v$ in one line, the value of this interval in little $\mathrm{b}$'s view.

--- ### 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