{"raw_statement":[{"iden":"statement","content":"A _star_ is a figure of the following type: an asterisk character '_*_' in the center of the figure and four rays (to the left, right, top, bottom) of the same positive length. The size of a _star_ is the length of its rays. The size of a star must be a positive number (i.e. rays of length $0$ are not allowed).\n\nLet's consider empty cells are denoted by '_._', then the following figures are _stars_:\n\n<center>![image](https://espresso.codeforces.com/8c02b8076a2983adac7612a1a545c6baca48ed49.png) The leftmost figure is a _star_ of size $1$, the middle figure is a _star_ of size $2$ and the rightmost figure is a _star_ of size $3$.</center>You are given a rectangular grid of size $n \\times m$ consisting only of asterisks '_*_' and periods (dots) '_._'. Rows are numbered from $1$ to $n$, columns are numbered from $1$ to $m$. Your task is to draw this grid using _any_ number of _stars_ or find out that it is impossible. _Stars_ can intersect, overlap or even coincide with each other. The number of _stars_ in the output can't exceed $n \\cdot m$. Each star should be completely inside the grid. You can use stars of same and arbitrary sizes.\n\n_In this problem, you do not need to minimize the number of stars. Just find any way to draw the given grid with at most $n \\cdot m$ stars._"},{"iden":"input","content":"The first line of the input contains two integers $n$ and $m$ ($3 \\le n, m \\le 100$) — the sizes of the given grid.\n\nThe next $n$ lines contains $m$ characters each, the $i$\\-th line describes the $i$\\-th row of the grid. It is guaranteed that grid consists of characters '_*_' and '_._' only."},{"iden":"output","content":"If it is impossible to draw the given grid using _stars_ only, print \"_\\-1_\".\n\nOtherwise in the first line print one integer $k$ ($0 \\le k \\le n \\cdot m$) — the number of _stars_ needed to draw the given grid. The next $k$ lines should contain three integers each — $x_j$, $y_j$ and $s_j$, where $x_j$ is the row index of the central _star_ character, $y_j$ is the column index of the central _star_ character and $s_j$ is the size of the _star_. Each _star_ should be completely inside the grid."},{"iden":"examples","content":"Input\n\n6 8\n....*...\n...**...\n..*****.\n...**...\n....*...\n........\n\nOutput\n\n3\n3 4 1\n3 5 2\n3 5 1\n\nInput\n\n5 5\n.*...\n****.\n.****\n..**.\n.....\n\nOutput\n\n3\n2 2 1\n3 3 1\n3 4 1\n\nInput\n\n5 5\n.*...\n***..\n.*...\n.*...\n.....\n\nOutput\n\n\\-1\n\nInput\n\n3 3\n*.*\n.*.\n*.*\n\nOutput\n\n\\-1"},{"iden":"note","content":"In the first example the output\n\n2\n3 4 1\n3 5 2\n\nis also correct."}],"translated_statement":[{"iden":"statement","content":"一个 _星形_ 是由以下类型的图形构成的：中心位置是一个星号字符 '_*_'，以及四个方向（左、右、上、下）的射线，每条射线长度相同且为正数。星形的大小定义为其射线的长度。星形的大小必须是正数（即长度为 $0$ 的射线是不允许的）。\n\n假设空格用 '_._' 表示，则以下图形是 _星形_：\n\n给你一个大小为 $n \\times m$ 的矩形网格，仅由星号 '_*_' 和点（句点）'_._' 组成。行从 $1$ 到 $n$ 编号，列从 $1$ 到 $m$ 编号。你的任务是使用 _任意数量的_ _星形_ 来绘制这个网格，或者判断这是不可能的。_星形_ 可以相互交叉、重叠甚至完全重合。输出中 _星形_ 的数量不能超过 $n \\cdot m$。每个星形必须完全位于网格内部。你可以使用相同或任意大小的星形。\n\n_在本题中，你不需要最小化星形的数量，只需找到一种使用至多 $n \\cdot m$ 个星形绘制给定网格的方法即可。_\n\n输入的第一行包含两个整数 $n$ 和 $m$（$3 \\leq n, m \\leq 100$）——给定网格的尺寸。\n\n接下来的 $n$ 行，每行包含 $m$ 个字符，第 $i$ 行描述网格的第 $i$ 行。保证网格仅由字符 '_*_' 和 '_._' 组成。\n\n如果无法仅用 _星形_ 绘制给定网格，请输出 \"_-1_\"。\n\n否则，在第一行输出一个整数 $k$（$0 \\leq k \\leq n \\cdot m$）——绘制给定网格所需的 _星形_ 数量。接下来的 $k$ 行，每行包含三个整数：$x_j$、$y_j$ 和 $s_j$，其中 $x_j$ 是星形中心字符的行索引，$y_j$ 是星形中心字符的列索引，$s_j$ 是星形的大小。每个星形必须完全位于网格内部。\n\n在第一个示例中，输出 \n\n也是正确的。"},{"iden":"input","content":"输入的第一行包含两个整数 $n$ 和 $m$（$3 \\leq n, m \\leq 100$）——给定网格的尺寸。接下来的 $n$ 行，每行包含 $m$ 个字符，第 $i$ 行描述网格的第 $i$ 行。保证网格仅由字符 '_*_' 和 '_._' 组成。"},{"iden":"output","content":"如果无法仅用 _星形_ 绘制给定网格，请输出 \"_-1_\"。否则，在第一行输出一个整数 $k$（$0 \\leq k \\leq n \\cdot m$）——绘制给定网格所需的 _星形_ 数量。接下来的 $k$ 行，每行包含三个整数：$x_j$、$y_j$ 和 $s_j$，其中 $x_j$ 是星形中心字符的行索引，$y_j$ 是星形中心字符的列索引，$s_j$ 是星形的大小。每个星形必须完全位于网格内部。"},{"iden":"examples","content":"输入\n6 8\n....*.....\n...**.....\n*****....\n...**.....\n....*.....\n........\n输出\n3\n3 4 1\n3 5 2\n3 5 1\n\n输入\n5 5\n.*...\n*****\n..***\n..**.\n.....\n输出\n3\n2 2 1\n3 3 1\n3 4 1\n\n输入\n5 5\n.*...\n***..\n.*...\n.*...\n.....\n输出\n-1\n\n输入\n3 3\n*.*\n.*.\n*.*\n输出\n-1"},{"iden":"note","content":"在第一个示例中，输出\n2\n3 4 1\n3 5 2\n也是正确的。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z} $ be the dimensions of the grid, with $ 3 \\leq n, m \\leq 100 $.  \nLet $ G \\in \\{*, .\\}^{n \\times m} $ be the input grid, where $ G[i][j] $ denotes the character at row $ i $, column $ j $ (1-indexed).  \n\nA *star* centered at $ (x, y) $ with size $ s \\in \\mathbb{Z}^+ $ is defined as the set of cells:  \n$$\n\\{(x, y)\\} \\cup \\{(x - d, y) \\mid 1 \\leq d \\leq s\\} \\cup \\{(x + d, y) \\mid 1 \\leq d \\leq s\\} \\cup \\{(x, y - d) \\mid 1 \\leq d \\leq s\\} \\cup \\{(x, y + d) \\mid 1 \\leq d \\leq s\\}\n$$  \nA star is *valid* if all its cells lie within the grid bounds: $ 1 \\leq x \\leq n $, $ 1 \\leq y \\leq m $, and $ s \\geq 1 $, with $ x - s \\geq 1 $, $ x + s \\leq n $, $ y - s \\geq 1 $, $ y + s \\leq m $.\n\nLet $ \\mathcal{S} $ be a multiset of valid stars.\n\n**Constraints**  \n1. $ G[i][j] = * $ if and only if there exists at least one star in $ \\mathcal{S} $ covering cell $ (i, j) $.  \n2. $ G[i][j] = . $ if and only if no star in $ \\mathcal{S} $ covers cell $ (i, j) $.  \n3. $ |\\mathcal{S}| \\leq n \\cdot m $.  \n4. Each star in $ \\mathcal{S} $ has size $ s_j \\geq 1 $ and is fully contained in the grid.\n\n**Objective**  \nFind a set $ \\mathcal{S} = \\{(x_j, y_j, s_j)\\}_{j=1}^k $ satisfying the above constraints, or determine that no such set exists (output $-1$).","simple_statement":null,"has_page_source":false}