你是一家投资公司的交易员。一天，你发现自己负责交易的股票每天都遵循完全重复的规律：一天被划分为 $n$ 个等长的时间段，在第 $i$ 个时间段内，股票价格始终为 $a_i$。一天的第 $n$ 个时间段结束后，紧接着就是下一天的第一个时间段，价格从 $a_n$ 变为 $a_1$。这是千载难逢的机会——只要在工作时间内按照你已经掌握的规律买卖，就一定有办法获利！

你的工作时间并不固定，一段工作时间可能跨越午夜。给定 $q$ 段工作时间。第 $i$ 段工作时间从时间段 $l_i$ 开始，到时间段 $r_i$ 结束，包含两个端点。时间段按时间先后顺序排列如下：

• 若 $l_i \le r_i$，则为 $l_i, l_i + 1, \ldots, r_i$；
• 若 $l_i > r_i$，则为 $l_i, l_i + 1, \ldots, n, 1, 2, \ldots, r_i$。

在每段工作时间内，你至多可以完成 $k$ 次交易。每次交易包括买入一股股票，并在之后的某个时间段将其卖出，利润等于卖出价减去买入价。你在任何时刻至多持有一股股票，因此必须先卖出当前持有的股票，才能再买入。所有买入和卖出都必须在该段工作时间内进行，并遵循上述时间先后顺序。你也可以不进行任何交易，获得 $0$ 的利润。

对于每段工作时间，独立求出你能获得的最大总利润。

输入格式

第一行包含三个整数 $n, k, q$（$1 \le n \le 10^5$，$1 \le k \le 800$，$1 \le q \le 3 \times 10^5$），分别表示一天中的时间段数、每段工作时间内的最大交易次数，以及工作时间的段数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^6$），其中 $a_i$ 是每天第 $i$ 个时间段内的股票价格。

接下来的 $q$ 行，每行包含两个整数 $l_i, r_i$（$1 \le l_i, r_i \le n$），描述第 $i$ 段工作时间。设 $\mathrm{len}_i$ 为这段工作时间内的时间段数。若 $l_i \le r_i$，则 $\mathrm{len}_i = r_i - l_i + 1$；否则，$\mathrm{len}_i = n - l_i + 1 + r_i$。

对于每段工作时间，$l_i$ 和 $\mathrm{len}_i$ 分别从 $[1,n]$ 和 $[\max(1,\lfloor 0.15n \rfloor),\max(1,\lfloor 0.85n \rfloor)]$ 中独立、均匀随机生成。$r_i$ 的值由 $l_i$ 和 $\mathrm{len}_i$ 唯一确定。 具体而言，当区间为 $[1,1]$ 时，随机结果始终为 $1$。

除样例外，恰好有 50 个测试用例。

输出格式

输出 $q$ 行。第 $i$ 行应包含一个整数：在第 $i$ 段工作时间内至多进行 $k$ 次交易时，你能获得的最大利润。

样例

输入格式 1

6 2 3
3 1 4 1 5 9
2 5
5 2
4 4

输出格式 1

7
4
0