You may have heard of "spooky action at a distance", or you may have not. It doesn't matter. There exists a line of ~N~ particles, of which the ~i^\text{th}~ particle and the ~N-i+1^\text{th}~ particle are quantum entangled. Note that what is described in this problem is not how quantum entanglement really works. Each particle has an electric charge ~e_i~. You happen to know the electric charges of all ~N~ particles in order.

When you look at a particle ~i~, due to the fact that it is entangled, it will instantaneously have the charge of particle ~N-i+1~, and particle ~N-i+1~ will have the charge of particle ~i~. You can only look at a maximum of ~K~ particles before you become blinded. Thus, you are curious: what is the maximum sum of the charges of the particles ~l~ to ~r~, inclusive, if I look at EXACTLY ~K~ particles? Note that you can look at a particle at one position multiple times.

You must answer ~Q~ of these questions. These questions must be answered online.

Input Specification

The first line will contain three integers ~N, K, Q~ ~(1 \le N, Q \le 10^5, 0 \le K \le N)~.

The second line will contain ~N~ integers, ~e_i~ ~(|e_i| \le 10^9)~.

The next ~Q~ lines will each contain two integers, ~l, r~ ~(1 \le l \le r \le N)~, a question as defined above.

After each question, you must output the answer before you will receive the next question. In some languages, you may need to flush in order for the interactor to receive your answer. The interactor may take up to 1.5 seconds of the time limit.

Output Specification

Output ~Q~ lines. On the ~i^\text{th}~ line, output one integer: the maximum sum of charges of the particles in ~[l, r]~.

Subtasks

Subtask 1 [14%]

~N \le 10^3~

Subtask 2 [27%]

~K \le \min(N, 10^3)~

Subtask 3 [59%]

No additional constraints.

Sample Input 1

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

Sample Output 1

10
18
14
10
3

Explanation For Sample 1

For the first question, if we choose ~i=3~ and look ~K=3~ times, we get the line of particles 3 4 3 8 -5 1 0, whose sum of charges from ~l=1~ to ~r=3~ is ~3+4+3 = 10~. It turns out, this is the maximum possible sum.