Height Difference Query

You are given n friends with initial heights \(a_i\). Over m years, in each year the j-th friend grows by \(b_{i,j}\) in the i-th year. After that, you will be given q queries.

Each query consists of three integers \(x, y, z\). It asks for the height difference between friend \(y\) and friend \(z\) after \(x\) years, i.e. compute

\( (a_y + \sum_{i=1}^{x} b_{i,y}) - (a_z + \sum_{i=1}^{x} b_{i,z}) \)

Note that when \(x=0\), the query simply compares the initial heights.

inputFormat

The input is given in the following format:

n m
a1 a2 ... an
// Next m lines, each with n integers
b1,1 b1,2 ... b1,n
b2,1 b2,2 ... b2,n
...
bm,1 bm,2 ... bm,n
q
x1 y1 z1
... (q queries)

Here, the first line contains two integers n and m. The second line contains n integers \(a_i\) representing the initial heights. The next m lines describe the yearly growths \(b_{i,j}\) for each friend. Afterwards, the number q indicates how many queries there are, followed by q lines each having three integers \(x, y, z\).

outputFormat

For each query, output a single line with one integer representing the height difference between friend y and friend z after x years.

sample

3 2
10 20 30
1 2 3
2 0 -1
3
0 1 2
1 3 1
2 2 3

-10
22
-10