Valued Gift Interval

A store displays n goods arranged from left to right with indices \(1,2,\dots,n\). Each good has a type and a corresponding value. The types are given as \(p_1,p_2,\dots,p_n\) and the values as \(v_1,v_2,\dots,v_n\).

Sunny chooses a contiguous interval of goods and buys all the gifts in that interval to present to little b. When little b receives the gifts, she inspects them from right to left. For each gift type, if she sees that the same type appears for the \(k\)th time during her inspection, she will not inspect that gift (including the \(k\)th one) nor any earlier gifts of that type in the interval. Consequently, those gifts lose their original value.

Your task is: given \(m\) queries each denoting an interval, compute the total value that little b perceives for the gifts in the interval.

Detail Explanation:

Consider an interval \([l,r]\). For a given gift type, suppose it appears \(c\) times in \([l,r]\).

• If \(c < k\), then all gifts of that type are inspected and their values are counted.
• If \(c \ge k\), then only the rightmost \(k-1\) gifts are inspected (i.e. those with the highest indices in \([l,r]\)), and the remaining gifts of that type are ignored.

The answer for a query is the sum of the values of the gifts that are inspected.

Input/Output formats are described below.

inputFormat

The first line contains three integers \(n, m, k\) \( (1 \le n, m \le 10^5)\).
The second line contains \(n\) integers \(p_1, p_2, \dots, p_n\) representing the types of the goods.
The third line contains \(n\) integers \(v_1, v_2, \dots, v_n\) representing the values of the goods.
Then, \(m\) lines follow; each line contains two integers \(l\) and \(r\) \( (1 \le l \le r \le n)\) representing a query interval.

outputFormat

For each query, output a single integer – the total value visible to little b after applying the inspection rule.

sample

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

6
5
6

</p>