定义初始数列为每个数字都为 $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$ 行，每行一个整数，表示至少需要的操作次数。

样例数据

样例 1 输入

5 4 1
1 1 2 1 1
1 5

样例 1 输出

2

样例 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$。

样例 2 输入

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

样例 2 输出

22
10
9

子任务

• 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$。