There exists an apartment building with ~F~ ~(1 \le F \le 5)~ floors and ~R~ ~(1 \le R \le 10\,000)~ apartments per floor. All the neighbours coexist with each other peacefully and enjoy life in the city. However, these are not safe times. aurpine has been breaking into various apartments and stealing white noise CDs from the tenants!

aurpine knows that each apartment has ~C_i~ ~(1 \le C_i \le 100)~ 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 ~a~ and apartment ~b~ ~(1 \le a \le b \le R)~ (inclusive) on floor ~c~ ~(1 \le c \le F)~. As he is very thorough, he will ask you ~Q~ ~(1 \le Q \le 500\,000)~ questions in total.

Input Specification

On the first line, two space separated integers ~F~ and ~R~.

The next ~F~ lines contain ~R~ integers representing ~C_i~, the number of CDs in the ~i^\text{th}~ apartment.

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

The next ~Q~ lines each contain three integers ~a~, ~b~ and ~c~.

Note: For 40% of points, ~1 \le R \le 1000~ and ~1 \le Q \le 20~.

Output Specification

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

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 ~1+2+3 = 6~.

The total white noise CDs contained in apartments 2 to 5 on floor 2 is ~6+4+3+6 = 19~.

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