题目描述

小核桃给仓鼠们搭建了一个 $n$ 行 $m$ 列的管道乐园。每个格子都是一个小房间，里面住着一只仓鼠。

每个房间的墙上有若干个管道口，用一个字符表示房间的类型。初始时，各种房间的管道口方向如下：

两个上下或左右相邻的房间，只有在相对的两面墙上都有管道口时，才能互相通行。例如，左边房间有向右的管道口，右边房间有向左的管道口，这两个房间才能接通。只有一边有管道口时，仓鼠不能通过。朝向乐园外面的管道口也不能通行。

乐园还有一个神奇的旋转按钮。每按一次，所有房间的管道口都同时顺时针旋转 90 度，但房间所在的格子不变。例如，L 型房间的管道口会依次变为：

小核桃准备先按若干次按钮，再在一些房间里放置食盆。只要一只仓鼠能够经过管道到达某个放有食盆的房间，它就能吃到食物。仓鼠也可以直接使用自己房间里的食盆，一个食盆可以供任意多只仓鼠使用。

为了让所有仓鼠都能吃到食物，请求出最少需要放置的食盆数量。如果有多种旋转方式都能达到这个最小数量，请选择按按钮次数最少的方式。

由于按 4 次按钮后所有管道口都会恢复原状，只需要考虑按 0、1、2、3 次按钮。

输入格式

从文件 hamster.in 中读取数据。

第一行包含两个整数 $n,m$，分别表示乐园的行数和列数。

接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串。第 $i$ 行的第 $j$ 个字符表示第 $i$ 行、第 $j$ 列房间的类型，保证只包含 I、L、T、X。

输出格式

输出到文件 hamster.out 中。

输出两个整数，依次表示最少需要的食盆数量，以及达到该数量时最少需要按按钮的次数。

样例

1 3
ILI

2 1

2 3
IIL
XXX

1 2

数据规模与约定

对于所有测试数据，保证：

• $1\le n,m\le500$；
• 每行字符串的长度恰好为 $m$；
• 所有房间类型均为 I、L、T、X。

本题采用子任务捆绑评测。各子任务的限制如下；未特别说明的限制均与上述约定相同。

下发文件

下载三组测试数据，非真实测试数据