There exists an apartment building with floors and apartments per floor. All the neighbours coexist with each other peacefully and enjoy life in the city. However, these are not safe times. has been breaking into various apartments and stealing white noise CDs from the tenants!

CDs, and wants to listen to as many white noise CDs as possible. To do so, he asks you to determine the total amount of white noise CDs he can get by robbing all apartments between apartment and apartment (inclusive) on floor . As he is very thorough, he will ask you questions in total.

knows that each apartment has#### Input Specification

On the first line, two space separated integers and .

The next lines contain integers representing , the number of CDs in the apartment.

On the next line, one integer , representing the number of questions.

The next lines each contain three integers , and .

**Note:** For 40% of points, and .

#### Output Specification

Output lines each containing one integer, representing the total amount of white noise CDs can get by robbing all apartments between apartment and on floor .

#### Sample Input

```
2 5
1 2 3 4 5
5 6 4 3 6
3
1 3 1
2 5 2
3 4 1
```

#### Sample Output

```
6
19
7
```

#### Explanation of Sample Output

The total white noise CDs contained in apartments 1 to 3 on floor 1 is .

The total white noise CDs contained in apartments 2 to 5 on floor 2 is .

The total white noise CDs contained in apartments 3 to 4 on floor 1 is .

## Comments

Fast I/O needed