森林监测：高风险点统计

故事背景

林业部门用网格记录了每片区域的火险指数。为安排巡护力量，他们需要快速统计任意矩形区域内“高于或等于阈值 T 的网格点数量”。

题目描述

给定一个 n×m 的整数矩阵 a 和一个阈值 T。接着有 q 次询问，每次给出矩形 (x1, y1) 到 (x2, y2)（1 基），请输出该区域内满足 a[i][j] ≥ T 的格子数量。

输入格式

• 第一行包含四个整数 n、m、q、T。
• 接下来 n 行，每行 m 个整数，表示矩阵 a。
• 接下来 q 行，每行四个整数 x1、y1、x2、y2。

输出格式

输出 q 行，每行一个整数，表示对应区域内高风险格子的数量。

输入输出样例 #1

输入 #1

3 3 2 10
1 10 2
9 11 12
10 3 4
1 1 3 3
2 2 3 3

输出 #1

4
2

样例解释 #1

全图中 ≥10 的点为 {10,11,12,10} 共 4 个；在 (2,2)-(3,3) 内为 {11,12} 共 2 个。

说明/提示

• 数据范围示例：1 ≤ n,m ≤ 1000；1 ≤ q ≤ 2×10^5；-10^9 ≤ a[i][j] ≤ 10^9。
• 提示：可构造二值矩阵 b[i][j] = (a[i][j] >= T ? 1 : 0)，对 b 计算二维前缀和并在 O(1) 时间回答计数查询。