题目背景

$\mathrm{Sunny}$ 有个 $npy$ 叫做小 $\mathrm{b}$。

小 $\mathrm{b}$ 的生日就要到了，$\mathrm{Sunny}$ 想给她买一些礼物。

题目描述

商店里摆着琳琅满目的商品，每个商品都有：

• 编号，从左到右依次为 $1,2,\dots n$。

• 种类，分别为 $p_1,p_2,\dots p_n$。

• 价值，分别为 $v_1,v_2,\dots v_n$。

$\mathrm{Sunny}$ 想从中挑选一个区间，将这个区间里的所有礼物买下来送给小 $\mathrm{b}$。

小 $\mathrm{b}$ 会从右往左依次查看 $\mathrm{Sunny}$ 送给他的礼物，如果她看到同一种类的礼物出现了 $k$ 次，那么她就不会再去查看这种礼物（包括第 $k$ 个），当然，这些礼物也就失去了原本的价值。

现在，$\mathrm{Sunny}$ 给你了 $m$ 个区间，想让你求出在小 $\mathrm{b}$ 眼中，这个区间的价值。

具体的价值计算见样例。

输入格式

第一行由空格隔开的三个正整数 $n,m,k$。

第二行 $n$ 个由空格隔开的正整数，第 $i$ 个数代表 $p_i$。

第三行 $n$ 个由空格隔开的正整数，第 $i$ 个数代表 $v_i$。

接下来 $m$ 行，第 $i$ 行两个正整数 $l_i,r_i$，表示第 $i$ 次询问的区间。

输出格式

输出 $m$ 行，对于每一个询问，输出一行一个整数 $v$，为这个区间在小 $\mathrm{b}$ 眼中的价值。

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

提示

---

样例说明

$[1,1]:7$。

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

$[1,3]:8+3=11$，因为编号为 $1$ 的礼物种类为 $1$，这是种类 $1$ 出现的第 $k(k=3)$ 次，所以她不会再看这种礼物（包括这个）。

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

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

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

---

数据范围与约定

测试点 $1-4:n\leq 100,m\leq 100$。

测试点 $5-6:n\leq 5000,m\leq 5000$。

测试点 $7-10:n\leq 2\times 10^4,m\leq 10^4$。

测试点 $11-15:n\leq 2\times 10^5,m\leq 2\times 10^5$。

测试点 $16-20:n\leq 10^6,m\leq 5\times 10^5$。

对于测试点 $1,2,7,8,11,12,16,17$，有 $k=n$，其余测试点有 $2\leq k<n$。

对于所有测试点，有 $1\leq p_i\leq n,1\leq v_i\leq 2000,1\leq l \leq r \leq n$。

---

对于测试点 $1-10$，每个 $3$ 分。

对于测试点 $11-20$ 中 $k=n$ 的，每个 $4$ 分。

其余测试点每个 $9$ 分。

---

对于测试点 $1-6$，时间限制 $500ms$。

对于测试点 $7-15$，时间限制 $750ms$。

对于测试点 $16-20$，时间限制 $1.5s$。

对于所有测试点，空间限制 $128MB$。

---

当然了，SWTR-02 的出题人们是不可能有 girlfriends 的。