{"problem":{"name":"E2. Stars Drawing (Hard Edition)","description":{"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","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF1015E2"},"statements":[{"statement_type":"Markdown","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._\n\n## Input\n\nThe first line of the input contains two integers $n$ and $m$ ($3 \\le n, m \\le 1000$) — 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.\n\n## Output\n\nIf 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.\n\n[samples]\n\n## Note\n\nIn the first example the output\n\n2\n3 4 1\n3 5 2\n\nis also correct.","is_translate":false,"language":"English"},{"statement_type":"Markdown","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 1000$）——给定网格的尺寸。\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也是正确的。\n\n## Input\n\n输入的第一行包含两个整数 $n$ 和 $m$（$3 \\leq n, m \\leq 1000$）——给定网格的尺寸。接下来的 $n$ 行每行包含 $m$ 个字符，第 $i$ 行描述网格的第 $i$ 行。保证网格仅由字符 '_*_' 和 '_._' 组成。\n\n## Output\n\n如果无法仅用 _星形_ 绘出给定的网格，请输出 \"_-1_\"。否则，在第一行输出一个整数 $k$（$0 \\leq k \\leq n \\cdot m$）——绘制给定网格所需的 _星形_ 数量。接下来的 $k$ 行每行包含三个整数：$x_j$、$y_j$ 和 $s_j$，其中 $x_j$ 是星形中心字符的行索引，$y_j$ 是列索引，$s_j$ 是星形的大小。每个星形必须完全位于网格内部。\n\n[samples]\n\n## Note\n\n在第一个示例中，输出\n2\n3 4 1\n3 5 2\n也是正确的。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ G \\in \\{*, .\\}^{n \\times m} $ be the input grid of size $ n \\times m $.  \nA *star* centered at $ (x, y) $ with size $ s \\in \\mathbb{Z}^+ $ is the set of cells:  \n$$\n\\{(x, y)\\} \\cup \\{(x - i, y) \\mid 1 \\le i \\le s\\} \\cup \\{(x + i, y) \\mid 1 \\le i \\le s\\} \\cup \\{(x, y - i) \\mid 1 \\le i \\le s\\} \\cup \\{(x, y + i) \\mid 1 \\le i \\le s\\}\n$$  \nA star is *valid* if all its cells lie within the grid boundaries: $ 1 \\le x \\pm s \\le n $ and $ 1 \\le y \\pm s \\le m $.\n\n**Constraints**  \n1. $ 3 \\le n, m \\le 1000 $  \n2. Each cell of $ G $ is either $ * $ or $ . $  \n3. Stars may overlap; total number of stars $ k \\le n \\cdot m $  \n4. Each star must have size $ s_j \\ge 1 $ and be completely contained in the grid.\n\n**Objective**  \nFind a set $ \\mathcal{S} = \\{(x_j, y_j, s_j) \\mid j = 1, \\dots, k\\} $ of valid stars such that:  \n$$\n\\bigcup_{j=1}^{k} \\text{star}(x_j, y_j, s_j) = \\{ (i, j) \\in [n] \\times [m] \\mid G[i][j] = * \\}\n$$  \nand $ \\text{star}(x_j, y_j, s_j) \\cap \\{ (i, j) \\mid G[i][j] = . \\} = \\emptyset $ for all $ j $.  \n\nIf no such set $ \\mathcal{S} $ exists, output $ -1 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF1015E2","tags":["binary search","dp","greedy"],"sample_group":[["6 8\n....*...\n...**...\n..*****.\n...**...\n....*...\n........","3\n3 4 1\n3 5 2\n3 5 1"],["5 5\n.*...\n****.\n.****\n..**.\n.....","3\n2 2 1\n3 3 1\n3 4 1"],["5 5\n.*...\n***..\n.*...\n.*...\n.....","\\-1"],["3 3\n*.*\n.*.\n*.*","\\-1"]],"created_at":"2026-03-03 11:00:39"}}