Bitaro Dũng Cảm đang đối mặt với Quỷ Vương. Để tấn công, Bitaro đặt các viên ngọc, quả cầu và thỏi kim loại lên một bảng gồm \(H\) hàng và \(W\) cột rồi niệm phép. Ô ở hàng thứ \(i\) từ trên xuống và cột thứ \(j\) từ trái sang phải được ký hiệu là \((i,j)\).

Bitaro đã đặt đúng một vật thuộc một trong ba loại trên vào mỗi ô. Sức mạnh của phép thuật bằng số bộ bốn số nguyên \((i,j,k,\ell)\) thỏa mãn \(1 \le i < k \le H\), \(1 \le j < \ell \le W\) và điều kiện sau: ô \((i,j)\) chứa một viên ngọc, ô \((i,\ell)\) chứa một quả cầu, còn ô \((k,j)\) chứa một thỏi kim loại.

Cho cách sắp xếp các vật trên bảng, hãy tính sức mạnh của phép thuật mà Bitaro niệm.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(H\) và \(W\).

Trong \(H\) dòng tiếp theo, dòng thứ \(i\) chứa chuỗi \(S_i\) có độ dài \(W\), mô tả hàng thứ \(i\). Ký tự thứ \(j\) của \(S_i\) là J nếu ô \((i,j)\) chứa một viên ngọc, O nếu chứa một quả cầu và I nếu chứa một thỏi kim loại.

Dữ liệu ra

In ra một dòng chứa sức mạnh của phép thuật.

Ràng buộc

• \(2 \le H,W \le 3000\).
• Mỗi chuỗi \(S_i\) có độ dài \(W\) và chỉ chứa các ký tự J, O, I.

Phân nhóm

1. \(20\) điểm: \(2 \le H,W \le 100\); mỗi \(S_i\) có độ dài \(W\) và chỉ gồm J, O, I.
2. \(30\) điểm: \(2 \le H,W \le 500\); mỗi \(S_i\) có độ dài \(W\) và chỉ gồm J, O, I.
3. \(50\) điểm: \(2 \le H,W \le 3000\); mỗi \(S_i\) có độ dài \(W\) và chỉ gồm J, O, I.

Ví dụ

3 4
JOIJ
JIOO
IIII

3

4 4
JJOO
JJOO
IIJO
IIIJ

17

Nguồn

Bản dịch tiếng Việt từ đề tiếng Anh chính thức của Ủy ban Olympic Tin học Nhật Bản, vòng chung kết JOI 2018/2019, bài 1. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.