409787: GYM103743 D Finding Pairs

You are given three integers $$$n$$$, $$$k$$$ and $$$q$$$ along with a sequence $$$a_1,a_2,...,a_n$$$. You have to process $$$q$$$ queries.

For each query, you will be given two integers $$$l$$$, $$$r$$$. Then, you should find a sequence of length $$$2m$$$ that consists of pairwise distinct integers, denoted as $$$b_1,b_2,...,b_{2m}$$$, such that $$$l\leq b_1,b_2,...,b_{2m}\leq r$$$, and for each $$$i\in [1,m]$$$, $$$|b_{2i-1}-b_{2i}|=k$$$. $$$m$$$ is a non-negative integer determined by you. Among all the valid sequences, you should find the maximum value of $$$a_{b_1}+a_{b_2}+...+a_{b_{2m}}$$$, and output it for each query.

The first line contains three integers $$$n$$$, $$$k$$$, $$$q$$$ ($$$1\leq n,q\leq 10^5$$$, $$$1\leq k\leq n$$$).

The second line contains $$$n$$$ integers $$$a_1,a_2,...,a_n$$$ ($$$-10^9\leq a_i\leq10^9$$$), indicating the given sequence.

Each of the following $$$q$$$ lines contains two integers $$$l$$$, $$$r$$$ ($$$1\leq l\leq r\leq n$$$), indicating a query.

For each query, output an integer in a single line indicating the answer.

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

10
12
12
14
0