题目背景

Muxii 是一个雪魔法师。只要他挥起魔法棒，念出神秘的咒语，雪花就会从天而降，在地面上一点一点地积累起厚厚的雪层。正因 Muxii 魔力高超，上帝任命 Muxii 掌管整个世界的雪。

某天，上帝给 Muxii 下达了一个任务：他需要让一个长为 $n$ 的地面上下雪。其中，第 $i$ 个位置的积雪厚度需要达到 $a_i$（$a_i\ge0$，“达到 $a_i$” 指不能低于也不能超过 $a_i$）。然而，上帝不知道的是，Muxii 的能力有限，他每次施法只能让长度 $\le m$ 的区间内下雪 1s，使得这个区间内的积雪厚度增加 $1$。由于任务急迫，Muxii 想要知道，若要完成某些区间的任务，他至少要施法多少次。

题目描述

定义初始数列为每个数字都为 $0$ 的数列。

定义一次操作为将数列的一个区间中每一个数的值增加 $1$，规定该区间的长度不能超过 $m$。

给定一个长度为 $n$ 的数列 $a$，第 $i$ 个数为 $a_i$。

你需要回答 $q$ 次询问。每次询问给定 $l,r$，你需要回答将一个长度为 $r-l+1$ 的初始数列变为 $a$ 中的 $[l,r]$（即数列 $a_l$, $a_{l+1}$, $\cdots$, $a_r$）至少需要多少次操作。

输入格式

第一行三个整数 $n,m,q$。

第二行 $n$ 个整数，第 $i$ 个为 $a_i$。

接下来 $q$ 行，每行两个整数，表示 $l,r$。

输出格式

$q$ 行，每行一个整数，表示至少需要的操作次数。

5 4 1
1 1 2 1 1
1 5

2

10 3 3
4 8 1 2 9 7 4 1 3 5
1 10
3 8
5 5

22
10
9

提示

「样例 1 说明」

一个长度为 $5$ 的初始数列为 $0$ $0$ $0$ $0$ $0$。

第一次操作为，将区间 $[1,3]$ 中每一个数，即第 $1$、$2$、$3$ 个数的值分别增加 $1$。经过该操作后，数列变为 $1$ $1$ $1$ $0$ $0$。

第二次操作为，将区间 $[3,5]$ 中每一个数，即第 $3$、$4$、$5$ 个数的值分别增加 $1$。经过该操作后，数列变为 $1$ $1$ $2$ $1$ $1$。

「数据范围与约定」

• Subtask 1（1 point）：$m=1$。
• Subtask 2（4 points）：$m=n$。
• Subtask 3（10 points）：$n,q\le300$。
• Subtask 4（10 points）：$n,q\le5\times10^3$。
• Subtask 5（15 points）：$m\le5$。
• Subtask 6（15 points）：$m\le100$。
• Subtask 7（20 points）：$n,q\le5\times10^4$。
• Subtask 8（25 points）：无特殊限制。

对于 $100\%$ 的数据，保证 $1\le m\le n\le10^5$，$1\le q\le10^5$，$0\le a_i\le10^9$，$1\le l\le r\le n$。