You may have heard of "spooky action at a distance", or you may have not. It doesn't matter. There exists a line of particles, of which the particle and the 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 . You happen to know the electric charges of all particles in order.

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

You must answer of these questions. **These questions must be answered online.**

#### Input Specification

The first line will contain three integers .

The second line will contain integers, .

The next lines will each contain two integers, , 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 lines. On the line, output one integer: the maximum sum of charges of the particles in .

#### Subtasks

##### Subtask 1 [14%]

##### Subtask 2 [27%]

##### 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 and look times, we get the line of particles `3 4 3 8 -5 1 0`

, whose sum of charges from to is . It turns out, this is the maximum possible sum.

## Comments