401904: GYM100570 C Subrect Query

De Prezer loves rectangles.He has a n × m rectangle which there is a number in each of its cells. We show the number in the j - th column of the i - th row by a_i, j.

De Prezer also loves query. So he gives you q queries. In each query, he gives you number k and asks you to print the number of subrectangles of this rectangle that the difference between the maximum element and the minimum element in them is at most k .

The first line of input contains 3 integers, n, m and q .

In the next n lines, there are informations of the rectangle. i - th line among them, contains m space separated integers, a_i, 1, a_i, 2, ..., a_i, m .

The next q lines, each line contains a single integer k (for that query).

1 ≤ n, m ≤ 400

1 ≤ q ≤ 10

1 ≤ a_i, j ≤ 10⁹ (for each 1 ≤ i ≤ n and 1 ≤ j ≤ m)

0 ≤ k ≤ 10⁹ (for each query)

For each query, print the answer in a single line.

5 4 6
451 451 452 452
452 452 452 452
451 452 450 450
451 451 451 451
452 452 450 450
0
2
773726
724963313
1
1

42
150
150
150
88
88

4 5 8
1314 1287 1286 1290 1295
1278 1271 1324 1317 1289
1305 1305 1284 1300 1309
1318 1296 1301 1274 1315
976296835
12
13
38
16
40
665711658
35

150
34
35
82
37
92
150
77