004 - 惑星探査

時間制限 1 秒 / メモリ制限 64 MB / 得点 100 / x 7 /


TLE
1sec
MLE
64MB
得点
100

問題

あなたを乗せた超時空移民船は長旅の末,ついに居住可能と思われる惑星を発見した.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 ≤ iM) には,居住予定地の北からi行目に位置するN 区画の情報を表すJ,O,I からなるN 文字の文字列が書かれている.
  • 続くK 行には調査対象となる領域が書かれている.j + M + 2 行目(1 ≤ jK) には, j 番目の領域を表す正整数aj, bj, cj, dj が空白を区切りとして書かれている.(aj, bj) は調査領域の北西の角の区画を,(cj, dj) は調査領域の南東の角の区画を表す.ただし,aj, bj, cj, dj は,1 ≤ ajcjM, 1 ≤ bjdjNを満たす.

出力

標準出力に調査の結果を表す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 区画含む.