题目描述

你的菜园由 $h\times w$ 个单位正方形地块组成。你从整个网格的左上角出发，只能沿地块边界行走，最后回到起点。行走路线围成区域内部的所有地块都视为被巡查。

路线不能自相交。边界道路足够宽，因此允许多次沿同一条地块边界经过，而这些经过可以视为互不相交。

字符矩阵 garden 描述每块地：

• I：你希望巡查的地块；
• X：绝对不能被巡查的地块；
• .：是否被巡查都无所谓。

设菜园中共有 $k$ 个 I。对于每个 $1\le t\le k$，求一条最短闭合路线，使得恰好有 $t$ 个 I 位于路线内部，并且没有任何 X 位于路线内部。

输入格式

第一行输入两个整数 $h,w$。

接下来 $h$ 行，每行一个长度为 $w$ 的字符串，表示菜园。

输出格式

第一行输出整数 $k$，即 I 的数量。

若 $k>0$，第二行输出 $k$ 个整数。第 $t$ 个整数表示恰好巡查 $t$ 个 I 时的最短路线长度。

若 $k=0$，只输出第一行的 0。

数据范围

• $1\le h,w\le50$；
• 每个字符只可能是 .,I,X；
• 整个矩阵中非 . 字符总数不超过 $10$；
• 至少有一个 I，或输出数组为空。

样例

输入

1 1
I

输出

1
4