Problem5180--海啸

5180: 海啸

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

有一个沿海地区,可以看作有 n 行 m 列的城市,第i行第j列的城市海拔为 h[i][j]。
由于沿海,所以这个地区经常会发生海啸。
海啸发生时,部分城市会被淹没,具体来说,海水高度会达到 d,因此海拔低于 d 的城市都会被淹没。
现在有 q 次询问,每次问你一个矩形区域中,有多少城市不会被淹没。

Input

第一行三个整数 n,m,d,具体含义见题目描述。
接下来 n 行,每行 m 个整数,其中第 i 行第 j 列的整数为 h[i][j],具体含义见题目描述。
第 n+2 行一个整数 q,表示询问数。
接下来 q 行,每行四个整数 a,b,x,y,表示询问从第 a 行第 b 列到第 x 行第 y 列的矩形地区中,有多少地区不会被淹没。即有多少个i,j,满足 a i x,b j y,且 h[i][j] > d。

Output

共 q 行,第 i 行一个整数,表示第 i 个询问的答案。

Sample 1 Input

3 3 3
1 2 3
2 1 5
4 3 2
2
1 2 2 3
2 1 3 3

Sample 1 Output

2
3

Source/Category

基础算法 4.2.前缀和