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