CF1015E2 Stars Drawing (Hard Edition)
题目描述
定义一个星星是下面形状的图形：
1. 由' $*$ '组成；
2. 星星的大小就是它向四个方向延伸的' $*$ '个数，注意四个方向要取最短的，不允许出现大小为$0$的星星。
空的格子是' $.$ '，下面是几种星星的例子：
不难发现，左图是大小为$1$的星星，中间的星星大小为$2$，而右侧的星星大小为$3$。
现在给定一个大小为$n\times m$，由' $.$ '和' $*$ '构成的的矩阵。你的任务是使用任意数量和大小的星星，画出这个矩阵上' $*$ '的图案，星星之间可以相交或重合。但星星不能超出矩阵。
输入格式
一个大小为$n\times m(3\le n,m\le 1000)$的字符矩阵，详细见题面
输出格式
若有的' $*$ '不可能归属于任何星星，输出 $-1$。否则先输出所有合法星星的个数，接下来输出所有合法星星的中心坐标和大小（见样例）
说明/提示
In the first example the output
```
2
3 4 1
3 5 2
``` is also correct.