AT_joi2011ho1.惑星探査 (Planetary Exploration)

你所乘坐的超时空移民船经过长途跋涉，终于发现了一颗似乎可以居住的行星。这颗被命名为 JOI 星的行星，正如其名，是一个由“丛林”（Jungle）、“海洋”（Ocean）、“冰原”（Ice）三种地形交错分布的严酷星球。经过简单调查，已经绘制出了居住预定地附近的地图。

居住预定地呈南北 $M$ 千米、东西 $N$ 千米的矩形，被划分为每边长 $1$ 千米的正方形区块。总共有 $MN$ 个区块，从北向南第 $p$ 行、西向东第 $q$ 列的区块记作 $(p,\ q)$。最西北角的区块为 $(1,\ 1)$，最东南角的区块为 $(M,\ N)$。每个区块的地形为“丛林”、“海洋”或“冰原”之一，分别用英文字母 J、O、I 表示。

现在，为了制定详细的移居计划，需要调查 $K$ 个矩形区域内分别包含多少“丛林”、“海洋”、“冰原”区块。

从标准输入读取以下数据。

• 第 $1$ 行包含两个整数 $M,\ N$，表示居住预定地南北长 $M$ 千米，东西长 $N$ 千米。
• 第 $2$ 行包含一个整数 $K$，表示需要调查的区域个数。
• 接下来的 $M$ 行，每行包含一个由 J、O、I 组成的长度为 $N$ 的字符串，表示居住预定地从北到南第 $i$ 行的区块信息。
• 接下来的 $K$ 行，每行包含四个正整数 $a_j,\ b_j,\ c_j,\ d_j$，用空格分隔，表示第 $j$ 个调查区域。$(a_j,\ b_j)$ 表示调查区域的西北角区块，$(c_j,\ d_j)$ 表示调查区域的东南角区块。满足 $1 \leq a_j \leq c_j \leq M$，$1 \leq b_j \leq d_j \leq N$。

输出 $K$ 行，每行包含三个整数，依次表示第 $j$ 个调查区域内“丛林”（J）、“海洋”（O）、“冰原”（I）区块的数量，整数之间用空格分隔。

任务

给定居住预定地的信息和需要调查的区域信息，请编写程序，计算每个区域内分别包含多少“丛林”、“海洋”、“冰原”区块。

限制

$1 \leq M \leq 1\,000$（居住预定地南北长度，单位：千米）
$1 \leq N \leq 1\,000$（居住预定地东西长度，单位：千米）
$1 \leq K \leq 100\,000$（需要调查的区域个数）

评分标准

在评分数据中，30% 的数据满足 $M \leq 50$ 且 $K \leq 100$。
50% 的数据满足 $M \leq 50$。

样例说明 1

在本输入样例中，第 $2$ 个调查区域如上图所示，包含 $3$ 个“丛林”区块、$5$ 个“海洋”区块和 $2$ 个“冰原”区块。

由 ChatGPT 4.1 翻译