004 - 惑星探査

問題

あなたを乗せた超時空移民船は長旅の末，ついに居住可能と思われる惑星を発見した．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 ≤ 1000    居住予定地の南北の長さ(km)
1 ≤ N ≤ 1000    居住予定地の東西の長さ(km)
1 ≤ K ≤ 100000    調査対象となる領域の個数

入力

標準入力から以下の入力を読み込め．

• 1 行目には整数M, N が空白を区切りとして書かれており，居住予定地が南北にM km ，東西にN km の広さであることを表す．
• 2 行目には整数K が書かれており，調査対象となる領域の個数を表す．
• 続くM 行には居住予定地の情報が書かれている．i + 2 行目(1 ≤ i ≤ M) には，居住予定地の北からi行目に位置するN 区画の情報を表すJ，O，I からなるN 文字の文字列が書かれている．
• 続くK 行には調査対象となる領域が書かれている．j + M + 2 行目(1 ≤ j ≤ 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 ≤ a_j ≤ c_j ≤ M, 1 ≤ b_j ≤ d_j ≤ Nを満たす．

出力

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

採点基準

採点用データのうち，配点の30%分については，M ≤ 50 かつK ≤ 100 を満たす．配点の50%分については，M ≤ 50 を満たす．

入出力の例

4 7
4
JIOJOIJ
IOJOIJO
JOIJOOI
OOJJIJO
3 5 4 7
2 2 3 6
2 2 2 2
1 1 4 7
  

1 3 2
3 5 2
0 1 0
10 11 7

この入力例では， 2 番目の領域は上図のように「ジャングル」を3 区画，「海」を5 区画，「氷」を2 区画含む．