Derek is a ~~finance bro~~ professional investor researching stocks. One particular stock has been public for days. Each day the stock was valued at dollars.

For ranges of days , he wants to know the mean price of the stock, rounding down. Unfortunately, his software doesn't have this option available. Can you help Derek answer his queries?

#### Constraints

For all subtasks,

##### Subtask 1 [10%]

##### Subtask 2 [90%]

No additional constraints.

#### Input Specification

The first line of input will contain space-separated integers and .

The next line will contain space-separated integers .

The next lines will contain space-separated integers and , denoting that Derek want's to know the mean price of the stock between days and inclusive.

#### Output Specification

For each one of derek's queries output the mean price of the stock between those days on a new line.

#### Sample Input

```
6 3
100 98 98 96 95 99
1 6
1 2
1 3
```

#### Sample Input

```
97
99
98
```

#### Explanation

For the first query, the mean price is .

For the second query, the mean price is .

For the third query, the mean price is .

## Comments