Sau một hành trình dài, con tàu di dân xuyên không gian và thời gian chở bạn cuối cùng đã tìm thấy một hành tinh có vẻ thích hợp để sinh sống. Hành tinh được đặt tên là JOI; đúng như tên gọi, đây là một hành tinh khắc nghiệt với ba loại địa hình đan xen: rừng rậm (Jungle), biển (Ocean) và băng (Ice). Sau một cuộc khảo sát sơ bộ, bản đồ khu vực dự định định cư đã được lập.

Khu vực dự định định cư có dạng hình chữ nhật, dài \(M\) km theo hướng bắc–nam và \(N\) km theo hướng đông–tây, được chia thành các ô vuông có cạnh \(1\) km. Có tất cả \(MN\) ô. Ô ở hàng thứ \(p\) tính từ phía bắc và cột thứ \(q\) tính từ phía tây được ký hiệu là \((p,q)\). Ô ở góc tây bắc là \((1,1)\), còn ô ở góc đông nam là \((M,N)\). Mỗi ô có đúng một trong ba loại địa hình: rừng rậm, biển hoặc băng, lần lượt được biểu diễn bằng các chữ cái J, O, I.

Để lập kế hoạch định cư chi tiết, bạn cần khảo sát \(K\) vùng hình chữ nhật, đếm số ô rừng rậm, biển và băng trong mỗi vùng.

Yêu cầu

Cho thông tin về khu vực dự định định cư và các vùng cần khảo sát, hãy viết chương trình tính số ô thuộc từng loại địa hình trong mỗi vùng.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa hai số nguyên \(M,N\), cách nhau bởi dấu cách, cho biết kích thước khu vực theo hướng bắc–nam và đông–tây, tính bằng km.
• Dòng thứ hai chứa số nguyên \(K\), là số vùng cần khảo sát.
• \(M\) dòng tiếp theo mô tả khu vực. Dòng \(i+2\) (\(1\le i\le M\)) chứa một chuỗi gồm \(N\) ký tự J, O, I, biểu diễn địa hình của \(N\) ô ở hàng thứ \(i\) tính từ phía bắc.
• \(K\) dòng tiếp theo mô tả các vùng cần khảo sát. Dòng \(j+M+2\) (\(1\le j\le K\)) chứa bốn số nguyên dương \(a_j,b_j,c_j,d_j\), cách nhau bởi dấu cách. Ô \((a_j,b_j)\) là góc tây bắc và ô \((c_j,d_j)\) là góc đông nam của vùng thứ \(j\). Các ô trên biên cũng thuộc vùng khảo sát.

Dữ liệu ra

Ghi ra đầu ra chuẩn \(K\) dòng. Dòng thứ \(j\) chứa ba số nguyên, cách nhau bởi dấu cách, lần lượt là số ô rừng rậm (J), biển (O) và băng (I) trong vùng khảo sát thứ \(j\).

Ràng buộc

• \(1\le M\le1000\).
• \(1\le N\le1000\).
• \(1\le K\le100000\).
• \(1\le a_j\le c_j\le M\) và \(1\le b_j\le d_j\le N\) với mọi \(1\le j\le K\).
• Giới hạn thời gian: \(0.5\) giây. Giới hạn bộ nhớ: \(64\) MB.

Phân nhóm

Bài có tổng cộng \(100\) điểm, gồm \(10\) bộ dữ liệu, mỗi bộ \(10\) điểm. Các điều kiện điểm thành phần dưới đây có thể chồng lấp:

• Các bộ dữ liệu chiếm \(30\%\) tổng số điểm thỏa mãn \(M\le50\) và \(K\le100\).
• Các bộ dữ liệu chiếm \(50\%\) tổng số điểm thỏa mãn \(M\le50\).

Ví dụ

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