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.
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