Planet Exploration

An expedition traveling by spaceship searched for a habitable planet and finally found one. The planet is covered entirely by jungle, sea, and ice. The team drew a map of the habitable region and sent it back to Earth.

The map is a rectangle $N$ cm wide and $M$ cm tall, divided into square cells 1 cm on each side. The terrain of each cell is written as a letter: jungle is J, sea is O, and ice is I.

Back on Earth, $K$ survey regions were chosen. For each region, write a program that counts how many cells of jungle, sea, and ice it contains.

The first line contains the map size $M$ and $N$. ($1 \le M, N \le 1000$)

The second line contains the number of survey regions $K$. ($1 \le K \le 100000$)

Each of the next $M$ lines contains the map: a string of length $N$ made up of J, O, and I.

Each of the following $K$ lines describes one survey region as four integers $a$, $b$, $c$, $d$. The region is a rectangle whose top-left cell is $(a, b)$ and whose bottom-right cell is $(c, d)$, where the first value is the row counted from the top and the second value is the column counted from the left. ($1 \le a \le c \le M$, $1 \le b \le d \le N$)

For each survey region, print the number of jungle, sea, and ice cells inside it, separated by spaces, one region per line. In other words, print the counts of J, O, and I in that order.

The figure below illustrates counting terrain inside one survey region. This region contains 3 jungle (J) cells, 5 sea (O) cells, and 2 ice (I) cells.