Problem Name: Planetary Exploration
Problem Description: After a long journey, the interdimensional immigrant ship you are on has finally discovered a planet that appears to be habitable. The planet, named JOI, is a harsh planet with three types of terrain: "Jungle," "Ocean," and "Ice," as the name suggests. Based on a simple survey, a map of the area near the planned residential area was created. The residential area is a rectangle with a length of M km from north to south and N km from east to west, and is divided into square sections with sides of 1 km. There are a total of MN sections, and the section in the p-th row from the north and the q-th column from the west is represented by (p,q). The section in the northwest corner is (1, 1) and the section in the southeast corner is (M,N). The terrain of each section is represented by a single English letter: "Jungle" is J, "Ocean" is O, and "Ice" is I.
Now, in order to make a detailed migration plan, it was decided to investigate how many sections of "Jungle," "Ocean," and "Ice" are included in K rectangular areas.
Task
Create a program that, given information about the planned residential area and information about the rectangular areas to be surveyed, calculates how many sections of "Jungle," "Ocean," and "Ice" are included in each area.
Constraints
1 ≤
M
≤ 1000: The length of the planned residential area from north to south (km)
1 ≤
N
≤ 1000: The length of the planned residential area from east to west (km)
1 ≤
K
≤ 100000: The number of areas to be surveyed
Input
Read the following input from standard input.
The first line contains two integers
M
and
N
separated by a space, indicating that the planned residential area has a length of
M
km from north to south and a length of
N
km from east to west.
The second line contains an integer
K
, indicating the number of areas to be surveyed.
The next
M
lines contain information about the planned residential area. The
i
+2nd line (1 ≤
i
≤
M
) contains an
N
-character string made up of J, O, and I, representing the information about the
N
sections from the north to the
i
-th row of the planned residential area.
The next
K
lines contain information about the areas to be surveyed. The
j
+
M
+2nd line (1 ≤
j
≤
K
) contains four integers
a
j
,
b
j
,
c
j
, and
d
j
separated by spaces, representing the northwest corner section (
a
j
,
b
j
) and the southeast corner section (
c
j
,
d
j
) of the
j
-th area to be surveyed. However,
a
j
,
b
j
,
c
j
, and
d
j
satisfy 1 ≤
a
j
≤
c
j
≤
M
and 1 ≤
b
j
≤
d
j
≤
N
.
Output
For each area, output a line consisting of three integers separated by a space: the number of sections of "Jungle" (J), the number of sections of "Ocean" (O), and the number of sections of "Ice" (I) contained in the area, in that order.
Scoring
For 30% of the test cases, the condition
M
≤ 50 and
K
≤ 100 is satisfied. For 50% of the test cases, the condition
M
≤ 50 is satisfied.
Example Input and Output
Input Example
4 7
4
JIOJOIJ
IOJOIJO
JOIJOOI
OOJJIJO
3 5 4 7
2 2 3 6
2 2 2 2
1 1 4 7
Output Example
1 3 2
3 5 2
0 1 0
10 11 7
In this example, the second area contains 3 sections of "Jungle," 5 sections of "Ocean," and 2 sections of "Ice," as shown in the figure above.
The problem statement and test data are based on those of the
Information Olympiad Japan
, which are created and made public by the Information Olympiad Japan Committee.