一所不知名大学的学生没有体育课。这就是为什么他们中的 $$$q$$$ 决定自己去附近的健身房。健身房开放 $$$n$$$ 天,并设有票务系统。在第 $$$i$$$ 天,一张票的费用等于 $$$a_i$$$。您每天可以自由购买多于一张门票。
您可以在 $$$i$$$ 日或之后的任何一天激活在 $$$i$$$ 日购买的票据。每张激活的门票仅在 $$$k$$$ 天内有效。换句话说,如果您在 $$$t$$$ 天激活票证,则该票仅在 $$$t, t + 1, \dots, t + k - 1$$$ 天有效。
您知道第 $$$j$$$ 个学生希望在从 $$$l_j$$$ 到 $$$r_j$$$(含)的每一天去健身房。每个学生将使用以下策略在任何一天访问健身房 $$$i$$$ ($$$l_j \le i \le r_j$$$):
1. 人来到入口附近的售票处,购买多张票,每张花费$$$a_i$$$(可能是零票);
2. 如果该人至少有一张已激活且仍然有效的门票,则他们只需进入。否则,他们会激活今天或更早购买的一张门票并进入。
请注意,每个学生只从 $$$l_j$$$ 开始去健身房,因此每个学生必须在 $$$l_j$$$ 当天至少购买一张门票。
帮助学生计算去健身房至少需要花多少钱。
输入
第一行包含三个整数 $$$n$$$、$$$q$$$ 和 $$$k$$$ ($$$1 \le n, q \le 300\,000$$$; $$$1 \le k \le n$$$) — 天数、学生人数和每张票仍然有效的天数。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 相应日期一张票的费用。
接下来的 $$$q$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) - 相应学生想要去健身房的天数。
输出
对于每个学生,打印出他们在想要的日子去健身房所需花费的最低金额。
示例
输入 #1
7 5 2 2 15 6 3 7 5 6 1 2 3 7 5 5 7 7 3 5
输出 #1
2 12 7 6 9
注意
让我们看看每个学生如何花他们的钱:
- 第一个学生应该在$$$1$$$当天购买一张票。
- 第二个学生应该在 $$$3$$$ 天购买一张票,在 $$$4$$$ 天购买两张票。请注意,学生可以保留接下来几天购买的门票。
- 第三个学生应该在$$$5$$$当天购买一张票。
- 第四个学生应该在$$$7$$$当天购买一张票。
- 第五个学生应该在 $$$3$$$ 购买一张票,并在 $$$4$$$ 购买一张票。