AT_joi2011ho1 惑星探査 (Planetary Exploration)

[problemUrl]: https://atcoder.jp/contests/joi2011ho/tasks/joi2011ho1 あなたを乗せた超時空移民船は長旅の末，ついに居住可能と思われる惑星を発見した．JOI 星と名付けられたその惑星は，その名の通り「ジャングル (Jungle)」，「海 (Ocean)」，「氷 (Ice)」の $ 3 $ 種類の地形が入り組んだ過酷な惑星である．簡単な調査により，居住予定地近辺の地図が作成された． 居住予定地は南北 $ M $ km，東西 $ N $ km の長方形の形をしており，$ 1 $ km 四方の正方形の区画に分けられている．区画は全部で $ MN $ 個あり，北から $ p $ 行目，西から $ q $ 列目の区画を $ (p,\ q) $ で表す．北西の角の区画が $ (1,\ 1) $ であり，南東の角の区画が $ (M,\ N) $ である．各区画の地形は，「ジャングル」，「海」，「氷」のいずれかであり，「ジャングル」は `J`，「海」は `O`，「氷」は `I` の英字 $ 1 $ 文字で表される. さて，詳細な移住計画を立てるにあたり，$ K $ 箇所の長方形領域内に「ジャングル」，「海」，「氷」がそれぞれ何区画含まれるかを調べることにした．

標準入力から以下のデータを読み込め． - $ 1 $ 行目には整数 $ M,\ N $ が空白を区切りとして書かれており，居住予定地が南北に $ M $ km，東西に $ N $ km の広さであることを表す． - $ 2 $ 行目には整数 $ K $ が書かれており，調査対象となる領域の個数を表す． - 続く $ M $ 行には居住予定地の情報が書かれている．$ i\ +\ 2 $ 行目 ($ 1\ \leqq\ i\ \leqq\ M $) には，居住予定地の北から $ i $ 行目に位置する $ N $ 区画の情報を表す `J`，`O`，`I` からなる $ N $ 文字の文字列が書かれている． - 続く $ K $ 行には調査対象となる領域が書かれている．$ j\ +\ M\ +\ 2 $ 行目 ($ 1\ \leqq\ j\ \leqq\ K $) には，$ j $ 番目の領域を表す正整数 $ a_j,\ b_j,\ c_j,\ d_j $ が空白を区切りとして書かれている．$ (a_j,\ b_j) $ は調査領域の北西の角の区画を，$ (c_j,\ d_j) $ は調査領域の南東の角の区画を表す．ただし，$ a_j,\ b_j,\ c_j,\ d_j $ は，$ 1\ \leqq\ a_j\ \leqq\ c_j\ \leqq\ M $，$ 1\ \leqq\ b_j\ \leqq\ d_j\ \leqq\ N $ を満たす．

標準出力に調査の結果を表す $ K $ 行を出力せよ．出力の $ j $ 行目には，$ j $ 番目の調査領域に含まれる「ジャングル」(`J`) の区画数，「海」(`O`) の区画数，「氷」(`I`) の区画数を表す $ 3 $ つの整数を，この順に空白を区切りとして書け．

### 課題 居住予定地の情報と，調査対象となる領域の情報が与えられたとき，それぞれの領域について，「ジャングル」，「海」，「氷」が何区画含まれているかを求めるプログラムを作成せよ． ### 制限 $ 1\ \leqq\ M\ \leqq\ 1\,000 $ 居住予定地の南北の長さ (km)$ 1\ \leqq\ N\ \leqq\ 1\,000 $ 居住予定地の東西の長さ (km)$ 1\ \leqq\ K\ \leqq\ 100\,000 $ 調査対象となる領域の個数- - - - - - ### 採点基準 採点用データのうち，配点の $ 30 $ %分については，$ M\ \leqq\ 50 $ かつ $ K\ \leqq\ 100 $ を満たす．配点の $ 50 $ %分については，$ M\ \leqq\ 50 $ を満たす． - - - - - - ### Sample Explanation 1 !\[e49255ca4684c5e6be34240da39319ed.png\](https://img.atcoder.jp/joi2011ho/e49255ca4684c5e6be34240da39319ed.png) この入力例では， $ 2 $ 番目の領域は上図のように「ジャングル」を $ 3 $ 区画，「海」を $ 5 $ 区画，「氷」を $ 2 $ 区画含む．