勇者ビ太郎(Bitaro the Brave)

勇者のビ太郎は,魔王と対峙することとなった.
ビ太郎は,縦H 行,横W 列のマス目上に宝石(Jewel),オーブ(Orb),金塊(Ingot) を配置し,魔法を発
動することによって魔王に攻撃をしようとしている.以下,マス目のうち上からi 行目(1 ≦i ≦H),左か
らj 列目(1 ≦j ≦W) のマスを,マス(i, j) と表す.
ビ太郎は今,それぞれのマスにこれら3 種類のうち1 個を配置した.今から魔法を発動しようとしてい
るが,この魔法の威力はマス目上の宝石,オーブ,金塊の配置によって決まる.具体的には,次の条件を
満たす整数(i, j, k, l) (1 ≦i < k ≦H, 1 ≦j < l≦W) の組の個数が,魔法の威力である.
条件:マス(i, j) には宝石が,マス(i, l) にはオーブが,マス(k, j) には金塊が置かれている.
ビ太郎は,この魔法の威力が気になっている.
マス目上の宝石,オーブ,金塊の配置が与えられたとき,ビ太郎が発動する魔法の威力を求めるプログ
ラムを作成せよ.

• 2 ≦H ≦3 000.
• 2 ≦W ≦3 000.
• S i は長さW の文字列である(1 ≦i ≦H).
• S i の各文字はJ,O,I のいずれかである(1 ≦i ≦H).

1. (20 点) H ≦100,W ≦100.
2. (30 点) H ≦500,W ≦500.
3. (50 点) 追加の制約はない.

入力は以下の形式で標準入力から与えられる.
H W
S 1
:
S H
S i (1 ≦i ≦H) は長さW の文字列で,そのj 文字目(1 ≦j ≦W) がJ のときはマス(i, j) に宝石が,O の
ときはマス(i, j) にオーブが,I のときはマス(i, j) に金塊が置かれていることを表す.

第18 回日本情報オリンピック(JOI 2018/2019) 本選
2019 年2 月10 日(茨城県つくば市)

標準出力に,魔法の威力を表す整数を1 行で出力せよ.

생성자가 기록되지 않았습니다.

출처 JOI 2019 Final