给定三个整数 $n, k, q$ 以及一个序列 $a_1, a_2, \dots, a_n$。你需要处理 $q$ 个查询。

对于每个查询，给定两个整数 $l, r$。你需要找到一个长度为 $2m$ 的序列，由两两不同的整数 $b_1, b_2, \dots, b_{2m}$ 组成，满足 $l \le b_1, b_2, \dots, b_{2m} \le r$，且对于每个 $i \in [1, m]$，都有 $|b_{2i-1} - b_{2i}| = k$。其中 $m$ 是由你决定的非负整数。在所有合法的序列中，你需要找到 $a_{b_1} + a_{b_2} + \dots + a_{b_{2m}}$ 的最大值，并为每个查询输出该值。

输入格式

第一行包含三个整数 $n, k, q$ ($1 \le n, q \le 10^5, 1 \le k \le n$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$)，表示给定的序列。

接下来的 $q$ 行，每行包含两个整数 $l, r$ ($1 \le l \le r \le n$)，表示一个查询。

输出格式

对于每个查询，输出一行，包含一个整数，表示答案。

样例

输入 1

7 2 5
-1 2 4 -3 6 5 3
1 5
2 6
3 7
1 7
2 4

输出 1

10
12
12
14
0