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).

Let's consider empty cells are denoted by '.', then the following figures are stars:

 [Image] 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$. 

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.

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.


-----Input-----

The first line of the input contains two integers $n$ and $m$ ($3 \le n, m \le 1000$) — the sizes of the given grid.

The 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.


-----Output-----

If it is impossible to draw the given grid using stars only, print "-1".

Otherwise 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.


-----Examples-----
Input
6 8
....*...
...**...
..*****.
...**...
....*...
........

Output
3
3 4 1
3 5 2
3 5 1

Input
5 5
.*...
****.
.****
..**.
.....

Output
3
2 2 1
3 3 1
3 4 1

Input
5 5
.*...
***..
.*...
.*...
.....

Output
-1

Input
3 3
*.*
.*.
*.*

Output
-1



-----Note-----

In the first example the output 2

3 4 1

3 5 2



is also correct.

Source: codeforces | Difficulty: HARD
Tags: Dynamic programming

Sorting

Greedy algorithms


Solutions:
import sys
from itertools import accumulate

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7

def build_grid(H, W, intv, _type, space=True, padding=False):
	if space:
		_input = lambda : input().split()
	else:
		_input = lambda : input()
	_list = lambda : list(map(_type, _input()))
	if padding:
		offset = 1
	else:
		offset = 0
	grid = list2d(H + offset * 2, W + offset * 2, intv)
	for i in range(offset, H + offset):
		row = _list()
		for j in range(offset, W + offset):
			grid[i][j] = row[j - offset]
	return grid
(H, W) = MAP()
grid = build_grid(H, W, '#', str, space=0, padding=1)
ans = []
imosw = list2d(H + 2, W + 2, 0)
imosh = list2d(H + 2, W + 2, 0)

def check(i, j):
	sz = min(L[i][j], R[i][j], U[i][j], D[i][j])
	if sz > 1:
		imosw[i][j - sz + 1] += 1
		imosw[i][j + sz] -= 1
		imosh[i - sz + 1][j] += 1
		imosh[i + sz][j] -= 1
		ans.append((i, j, sz - 1))

def check2():
	for i in range(1, H + 1):
		for j in range(1, W + 1):
			if grid[i][j] == '*' and (not imosw[i][j]) and (not imosh[i][j]):
				return False
	return True
L = list2d(H + 2, W + 2, 0)
R = list2d(H + 2, W + 2, 0)
U = list2d(H + 2, W + 2, 0)
D = list2d(H + 2, W + 2, 0)
for i in range(1, H + 1):
	for j in range(1, W + 1):
		if grid[i][j] == '.':
			L[i][j] = 0
		else:
			L[i][j] = L[i][j - 1] + 1
for i in range(1, H + 1):
	for j in range(W, 0, -1):
		if grid[i][j] == '.':
			R[i][j] = 0
		else:
			R[i][j] = R[i][j + 1] + 1
for j in range(1, W + 1):
	for i in range(1, H + 1):
		if grid[i][j] == '.':
			U[i][j] = 0
		else:
			U[i][j] = U[i - 1][j] + 1
for j in range(1, W + 1):
	for i in range(H, 0, -1):
		if grid[i][j] == '.':
			D[i][j] = 0
		else:
			D[i][j] = D[i + 1][j] + 1
for i in range(1, H + 1):
	for j in range(1, W + 1):
		if grid[i][j] == '*':
			check(i, j)
for i in range(1, H + 1):
	for j in range(W + 1):
		imosw[i][j + 1] += imosw[i][j]
for j in range(1, W + 1):
	for i in range(H + 1):
		imosh[i + 1][j] += imosh[i][j]
if check2():
	print(len(ans))
	[print(h, w, sz) for (h, w, sz) in ans]
else:
	print(-1)


import sys
(n, m) = list(map(int, input().split()))
s = [list(input()) for i in range(n)]
u = [[-1 for i in range(m)] for j in range(n)]
d = [[-1 for i in range(m)] for j in range(n)]
l = [[-1 for i in range(m)] for j in range(n)]
r = [[-1 for i in range(m)] for j in range(n)]
for i in range(m):
	acum = 0
	for j in range(n):
		if s[j][i] == '.':
			acum = 0
		else:
			acum += 1
		u[j][i] = acum
for i in range(m):
	acum = 0
	for j in range(n - 1, -1, -1):
		if s[j][i] == '.':
			acum = 0
		else:
			acum += 1
		d[j][i] = acum
for i in range(n):
	acum = 0
	for j in range(m):
		if s[i][j] == '.':
			acum = 0
		else:
			acum += 1
		l[i][j] = acum
for i in range(n):
	acum = 0
	for j in range(m - 1, -1, -1):
		if s[i][j] == '.':
			acum = 0
		else:
			acum += 1
		r[i][j] = acum
ans = []
t1 = [[0 for i in range(m)] for j in range(n)]
t2 = [[0 for i in range(m)] for j in range(n)]
for i in range(n):
	for j in range(m):
		d1 = min(l[i][j], r[i][j], u[i][j], d[i][j]) - 1
		if d1 > 0:
			ans.append([i + 1, j + 1, d1])
			t1[i + d1][j] += 1
			t1[i - d1][j] -= 1
			t2[i][j - d1] += 1
			t2[i][j + d1] -= 1
dp = [['.' for i in range(m)] for j in range(n)]
for i in range(n):
	acum = 0
	for j in range(m):
		acum += t2[i][j]
		if acum != 0 or t2[i][j] != 0:
			dp[i][j] = '*'
for i in range(m):
	acum = 0
	for j in range(n):
		acum += t1[j][i]
		if acum != 0 or t1[j][i] != 0:
			dp[j][i] = '*'
if dp != s:
	print(-1)
	return
print(len(ans))
for i in ans:
	print(*i)


def main():
	(n, m) = map(int, input().split())
	ll = [c == '*' for _ in range(n) for c in input()]
	nm = n * m
	RLUD = [*[range(i, i + m) for i in range(0, nm, m)], *[range(i, nm, m) for i in range(m)]]
	cc = [1000] * nm
	for f in (True, False):
		for r in RLUD:
			v = 0
			for i in r:
				if ll[i]:
					v += 1
					if cc[i] > v:
						cc[i] = v
				else:
					v = cc[i] = 0
		if f:
			ll.reverse()
			cc.reverse()
	cc = [c if c != 1 else 0 for c in cc]
	for f in (True, False):
		for r in RLUD:
			v = 0
			for i in r:
				if v > cc[i]:
					v -= 1
				else:
					v = cc[i]
				if v:
					ll[i] = False
		if f:
			ll.reverse()
			cc.reverse()
	if any(ll):
		print(-1)
	else:
		res = []
		for (i, c) in enumerate(cc):
			if c:
				res.append(f'{i // m + 1} {i % m + 1} {c - 1}')
		print(len(res), '\n'.join(res), sep='\n')

def __starting_point():
	main()
__starting_point()


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=10 ** 6, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(10)]
pp = [0] * 10

def SieveOfEratosthenes(n=10):
	p = 2
	c = 0
	while p * p <= n:
		if prime[p] == True:
			c += 1
			for i in range(p, n + 1, p):
				pp[i] += 1
				prime[i] = False
		p += 1

def binarySearch(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = arr[n - 1]
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] >= key:
			res = arr[mid]
			right = mid - 1
		else:
			left = mid + 1
	return res

def binarySearch1(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = arr[0]
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] > key:
			right = mid - 1
		else:
			res = arr[mid]
			left = mid + 1
	return res
(n, m) = map(int, input().split())
l = []
tot = []
done = [[0 for i in range(m)] for j in range(n)]
for i in range(n):
	l.append(input())
colsum = [[0 for i in range(m)] for j in range(n)]
rowsum = [[0 for i in range(m)] for j in range(n)]
col = [[0 for i in range(m)] for j in range(n)]
row = [[0 for i in range(m)] for j in range(n)]
for i in range(n):
	for j in range(m):
		if l[i][j] == '*':
			rowsum[i][j] = 1
			colsum[i][j] = 1
			row[i][j] = 1
			col[i][j] = 1
for i in range(n):
	for j in range(1, m):
		if l[i][j] == '.':
			continue
		rowsum[i][j] += rowsum[i][j - 1]
for i in range(n):
	for j in range(m - 2, -1, -1):
		if l[i][j] == '.':
			continue
		row[i][j] += row[i][j + 1]
for i in range(m):
	for j in range(n - 2, -1, -1):
		if l[j][i] == '.':
			continue
		col[j][i] += col[j + 1][i]
for i in range(m):
	for j in range(1, n):
		if l[j][i] == '.':
			continue
		colsum[j][i] += colsum[j - 1][i]

def check(x, y):
	i = x
	j = y
	ans = min(row[i][j], rowsum[i][j], colsum[i][j], col[i][j]) - 1
	if ans == 0:
		return []
	return [ans]
h = [[0 for i in range(m + 1)] for j in range(n)]
v = [[0 for i in range(m)] for j in range(n + 1)]
for i in range(n):
	for j in range(m):
		if l[i][j] == '*':
			ans = check(i, j)
			for j1 in ans:
				tot.append([i + 1, j + 1, j1])
				h[i][j - j1] += 1
				h[i][j + j1 + 1] -= 1
				v[i - j1][j] += 1
				v[i + j1 + 1][j] -= 1
for i in range(n):
	for j in range(1, m):
		h[i][j] += h[i][j - 1]
for i in range(m):
	for j in range(1, n):
		v[j][i] += v[j - 1][i]
for i in range(n):
	for j in range(m):
		if l[i][j] == '*' and h[i][j] == 0 and (v[i][j] == 0):
			print(-1)
			sys.exit(0)
print(len(tot))
for i in tot:
	print(*i)


(n, m) = list(map(int, input().split()))
c = []
for j in range(n):
	d = []
	s = input()
	for i in s:
		d.append(i)
	c.append(d)
a = []
b = []
e = []
g = []
for j in range(n):
	k = [0] * m
	e.append(k)
for j in range(n):
	k = [0] * m
	g.append(k)
dpu = []
for j in range(n):
	k = [0] * m
	dpu.append(k)
dpd = []
for j in range(n):
	k = [0] * m
	dpd.append(k)
dpl = []
for j in range(n):
	k = [0] * m
	dpl.append(k)
dpr = []
for j in range(n):
	k = [0] * m
	dpr.append(k)
for i in range(n):
	for j in range(m):
		if c[i][j] == '*':
			if i > 0:
				dpu[i][j] += dpu[i - 1][j] + 1
			else:
				dpu[i][j] = 1
			if j > 0:
				dpl[i][j] = dpl[i][j - 1] + 1
			else:
				dpl[i][j] = 1
i = n - 1
while i >= 0:
	j = m - 1
	while j >= 0:
		if c[i][j] == '*':
			if i < n - 1:
				dpd[i][j] += dpd[i + 1][j] + 1
			else:
				dpd[i][j] = 1
			if j < m - 1:
				dpr[i][j] = dpr[i][j + 1] + 1
			else:
				dpr[i][j] = 1
		j += -1
	i += -1
for i in range(1, n - 1):
	for j in range(1, m - 1):
		if c[i][j] == '*':
			k = min(dpd[i][j] - 1, dpu[i][j] - 1, dpr[i][j] - 1, dpl[i][j] - 1)
			if k == 0:
				pass
			elif k > 0:
				a.append([i + 1, j + 1, k])
				e[i - k][j] += 1
				if i + k < n - 1:
					e[i + k + 1][j] += -1
				g[i][j - k] += 1
				if j + k < m - 1:
					g[i][j + k + 1] += -1
for i in range(m):
	for j in range(1, n):
		if c[j - 1][i] == '*':
			e[j][i] += e[j - 1][i]
for i in range(n):
	for j in range(1, m):
		if c[i][j - 1] == '*':
			g[i][j] += g[i][j - 1]
f = 0
for i in range(n):
	for j in range(m):
		if c[i][j] == '*' and e[i][j] <= 0 and (g[i][j] <= 0):
			f = 1
			break
if f == 1:
	print(-1)
else:
	print(len(a))
	for j in a:
		print(*j)


import sys
from math import *

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return map(int, minp().split())

def main():
	(n, m) = mints()
	res = []
	a = [None] * n
	l = [None] * n
	r = [None] * n
	s = [0] * n
	for i in range(n):
		a[i] = list(minp())
		l[i] = [i for i in range(m)]
		r[i] = [i for i in range(m)]
		s[i] = [0] * m
	for i in range(n):
		j = 0
		b = a[i]
		ll = l[i]
		rr = r[i]
		while j < m:
			if b[j] == '*':
				jj = j + 1
				while jj < m and b[jj] == '*':
					jj += 1
				jj -= 1
				for k in range(j, jj + 1):
					ll[k] = j
					rr[k] = jj
				j = jj + 1
			else:
				j += 1
	for i in range(m):
		j = 0
		while j < n:
			if a[j][i] == '*':
				jj = j + 1
				while jj < n and a[jj][i] == '*':
					jj += 1
				jj -= 1
				for k in range(j, jj + 1):
					x = min(i - l[k][i], r[k][i] - i, k - j, jj - k)
					s[k][i] = x
					if x > 0:
						res.append((k + 1, i + 1, x))
				j = jj + 1
			else:
				j += 1
	for i in range(n):
		j = 0
		ss = s[i]
		rr = r[i]
		c = -1
		while j < m:
			if ss[j] > 0 and c < ss[j]:
				c = ss[j]
			if c >= 0:
				rr[j] = '*'
			else:
				rr[j] = '.'
			j += 1
			c -= 1
		j = m - 1
		c = -1
		while j >= 0:
			if ss[j] > 0 and c < ss[j]:
				c = ss[j]
			if c >= 0:
				rr[j] = '*'
			c -= 1
			j -= 1
	for i in range(m):
		j = 0
		c = -1
		while j < n:
			x = s[j][i]
			if x > 0 and c < x:
				c = x
			if c >= 0:
				r[j][i] = '*'
			j += 1
			c -= 1
		j = n - 1
		c = -1
		while j >= 0:
			x = s[j][i]
			if x > 0 and c < x:
				c = x
			if c >= 0:
				r[j][i] = '*'
			if r[j][i] != a[j][i]:
				print(-1)
				return
			c -= 1
			j -= 1
	print(len(res))
	for i in res:
		print(*i)
main()


def main():
	(n, m) = map(int, input().split())
	S = [list(str(input())) for _ in range(n)]
	L = [[0] * m for _ in range(n)]
	R = [[0] * m for _ in range(n)]
	U = [[0] * m for _ in range(n)]
	D = [[0] * m for _ in range(n)]
	for i in range(n):
		cnt = 0
		for j in range(m):
			if S[i][j] == '.':
				cnt = 0
			else:
				cnt += 1
				L[i][j] = cnt
		cnt = 0
		for j in reversed(range(m)):
			if S[i][j] == '.':
				cnt = 0
			else:
				cnt += 1
				R[i][j] = cnt
	for j in range(m):
		cnt = 0
		for i in range(n):
			if S[i][j] == '.':
				cnt = 0
			else:
				cnt += 1
				U[i][j] = cnt
		cnt = 0
		for i in reversed(range(n)):
			if S[i][j] == '.':
				cnt = 0
			else:
				cnt += 1
				D[i][j] = cnt
	imosH = [[0] * (m + 1) for _ in range(n)]
	imosV = [[0] * m for _ in range(n + 1)]
	ans = []
	for i in range(1, n - 1):
		for j in range(1, m - 1):
			if S[i][j] == '.':
				continue
			l = L[i][j] - 1
			r = R[i][j] - 1
			u = U[i][j] - 1
			d = D[i][j] - 1
			s = min([l, r, u, d])
			if s == 0:
				continue
			ans.append((i + 1, j + 1, s))
			imosV[i - s][j] += 1
			imosV[i + s + 1][j] -= 1
			imosH[i][j - s] += 1
			imosH[i][j + s + 1] -= 1
	from itertools import accumulate
	for i in range(n):
		imosH[i] = list(accumulate(imosH[i]))
	for j in range(m):
		for i in range(1, n + 1):
			imosV[i][j] += imosV[i - 1][j]
	for i in range(n):
		for j in range(m):
			if S[i][j] == '*':
				if imosH[i][j] <= 0 and imosV[i][j] <= 0:
					print(-1)
					exit()
	else:
		print(len(ans))
		for i in range(len(ans)):
			print(*ans[i])
main()


import sys
input = lambda : sys.stdin.readline().rstrip()
(h, w) = map(int, input().split())
s = [list('.' * (w + 2))] + [list('.' + input() + '.') for _ in range(h)] + [list('.' * (w + 2))]
b = [[0] * (w + 2) for _ in range(h + 2)]
c = [[0] * (w + 2) for _ in range(h + 2)]
for i in range(1, h + 2):
	for j in range(1, w + 2):
		if s[i][j] == '*':
			b[i][j] = b[i - 1][j] + 1
			c[i][j] = c[i][j - 1] + 1
for i in range(h, -1, -1):
	for j in range(w, -1, -1):
		if s[i][j] == '*':
			b[i][j] = min(b[i][j], b[i + 1][j] + 1)
			c[i][j] = min(c[i][j], c[i][j + 1] + 1)
ans = []
for i in range(1, h + 1):
	for j in range(1, w + 1):
		t = min(b[i][j], c[i][j]) - 1
		if t > 0:
			ans.append((i, j, t))
b = [[0] * (w + 2) for _ in range(h + 2)]
c = [[0] * (w + 2) for _ in range(h + 2)]
for (i, j, t) in ans:
	b[i - t][j] += 1
	b[i + t + 1][j] -= 1
	c[i][j - t] += 1
	c[i][j + t + 1] -= 1
for i in range(h + 1):
	for j in range(w + 1):
		b[i + 1][j] += b[i][j]
		c[i][j + 1] += c[i][j]
		if i != 0 and j != 0:
			if (b[i][j] + c[i][j] > 0) != (s[i][j] == '*'):
				print(-1)
				exit()
print(len(ans))
for i in ans:
	print(*i)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
s = [list(input().rstrip()) for _ in range(n)]
t = [[1000] * m for _ in range(n)]
ok1 = [[0] * m for _ in range(n)]
ok2 = [[0] * m for _ in range(n)]
for i in range(n):
	si = s[i]
	c = 0
	for j in range(m):
		if si[j] == '*':
			c += 1
		else:
			c = 0
		t[i][j] = min(t[i][j], c)
	c = 0
	for j in range(m - 1, -1, -1):
		if si[j] == '*':
			c += 1
		else:
			c = 0
		t[i][j] = min(t[i][j], c)
for j in range(m):
	c = 0
	for i in range(n):
		if s[i][j] == '*':
			c += 1
		else:
			c = 0
		t[i][j] = min(t[i][j], c)
	c = 0
	for i in range(n - 1, -1, -1):
		if s[i][j] == '*':
			c += 1
		else:
			c = 0
		t[i][j] = min(t[i][j], c)
ans = []
for i in range(n):
	for j in range(m):
		tij = t[i][j] - 1
		if tij >= 1:
			ans.append((i + 1, j + 1, tij))
			ok1[max(0, i - tij)][j] += 1
			if i + tij + 1 < n:
				ok1[i + tij + 1][j] -= 1
			ok2[i][max(0, j - tij)] += 1
			if j + tij + 1 < m:
				ok2[i][j + tij + 1] -= 1
for i in range(1, n):
	for j in range(1, m):
		ok1[i][j] += ok1[i - 1][j]
		ok2[i][j] += ok2[i][j - 1]
for i in range(n):
	for j in range(m):
		if s[i][j] == '*':
			if not (ok1[i][j] or ok2[i][j]):
				ans = -1
				print(ans)
				exit()
k = len(ans)
print(k)
for ans0 in ans:
	print(*ans0)


import math
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
(n, m) = map(int, input().split())
l = []
tot = []
done = [[0 for i in range(m)] for j in range(n)]
for i in range(n):
	l.append(input())
colsum = [[0 for i in range(m)] for j in range(n)]
rowsum = [[0 for i in range(m)] for j in range(n)]
col = [[0 for i in range(m)] for j in range(n)]
row = [[0 for i in range(m)] for j in range(n)]
for i in range(n):
	for j in range(m):
		if l[i][j] == '*':
			rowsum[i][j] = 1
			colsum[i][j] = 1
			row[i][j] = 1
			col[i][j] = 1
for i in range(n):
	for j in range(1, m):
		if l[i][j] == '.':
			continue
		rowsum[i][j] += rowsum[i][j - 1]
for i in range(n):
	for j in range(m - 2, -1, -1):
		if l[i][j] == '.':
			continue
		row[i][j] += row[i][j + 1]
for i in range(m):
	for j in range(n - 2, -1, -1):
		if l[j][i] == '.':
			continue
		col[j][i] += col[j + 1][i]
for i in range(m):
	for j in range(1, n):
		if l[j][i] == '.':
			continue
		colsum[j][i] += colsum[j - 1][i]

def check(x, y):
	i = x
	j = y
	ans = min(row[i][j], rowsum[i][j], colsum[i][j], col[i][j]) - 1
	if ans == 0:
		return []
	return [ans]
h = [[0 for i in range(m + 1)] for j in range(n)]
v = [[0 for i in range(m)] for j in range(n + 1)]
for i in range(n):
	for j in range(m):
		if l[i][j] == '*':
			ans = check(i, j)
			for j1 in ans:
				tot.append([i + 1, j + 1, j1])
				h[i][j - j1] += 1
				h[i][j + j1 + 1] -= 1
				v[i - j1][j] += 1
				v[i + j1 + 1][j] -= 1
for i in range(n):
	for j in range(1, m):
		h[i][j] += h[i][j - 1]
for i in range(m):
	for j in range(1, n):
		v[j][i] += v[j - 1][i]
for i in range(n):
	for j in range(m):
		if l[i][j] == '*' and h[i][j] == 0 and (v[i][j] == 0):
			print(-1)
			sys.exit(0)
print(len(tot))
for i in tot:
	print(*i)


(n, m) = map(int, input().split())
mat = []
for i in range(n):
	mat.append(list(map(int, input().replace('*', '1').replace('.', '0'))))
(ver, hor) = ([[0 for i in range(m)] for j in range(n)], [[0 for i in range(m)] for j in range(n)])
dp = [[[0 for i in range(4)] for j in range(m)] for k in range(n)]
for i in range(1, n):
	for j in range(1, m):
		(x, y) = (n - i - 1, m - j - 1)
		if mat[i][j] == 1:
			dp[i][j][0] = max(dp[i][j - 1][0], mat[i][j - 1]) + 1
			dp[i][j][1] = max(dp[i - 1][j][1], mat[i - 1][j]) + 1
		if mat[x][y] == 1:
			dp[x][y][2] = max(dp[x][y + 1][2], mat[x][y + 1]) + 1
			dp[x][y][3] = max(dp[x + 1][y][3], mat[x + 1][y]) + 1
stars = []
for i in range(1, n - 1):
	for j in range(1, m - 1):
		if mat[i][j] == 1:
			s = min(dp[i][j]) - 1
			if s > 0:
				stars.append((i + 1, j + 1, s))
				ver[i - s][j] += 1
				if i + s + 1 < n:
					ver[i + s + 1][j] -= 1
				hor[i][j - s] += 1
				if j + s + 1 < m:
					hor[i][j + s + 1] -= 1
for i in range(1, n):
	for j in range(1, m):
		ver[i][j] += ver[i - 1][j]
		hor[i][j] += hor[i][j - 1]
chk = True
for i in range(n):
	for j in range(m):
		if mat[i][j] and max(ver[i][j], hor[i][j]) <= 0:
			chk = False
			break
if chk:
	print(len(stars))
	for i in stars:
		print(*i)
else:
	print(-1)


def main():
	(n, m) = map(int, input().split())
	w = [c == '*' for i in range(n) for c in input()]
	nm = n * m
	q = [*[range(i, i + m) for i in range(0, nm, m)], *[range(i, nm, m) for i in range(m)]]
	e = [1000] * nm
	for f in (True, False):
		for r in q:
			v = 0
			for i in r:
				if w[i]:
					v += 1
					if e[i] > v:
						e[i] = v
				else:
					v = e[i] = 0
		if f:
			w.reverse()
			e.reverse()
	e = [c if c != 1 else 0 for c in e]
	for f in (True, False):
		for r in q:
			v = 0
			for i in r:
				if v > e[i]:
					v -= 1
				else:
					v = e[i]
				if v:
					w[i] = False
		if f:
			w.reverse()
			e.reverse()
	if any(w):
		print(-1)
	else:
		r = []
		for (i, c) in enumerate(e):
			if c:
				r.append(f'{i // m + 1} {i % m + 1} {c - 1}')
		print(len(r), '\n'.join(r), sep='\n')
main()


(n, m) = map(int, input().split())
g = [[*input()] for _ in range(n)]
c = [[0 for _ in range(m)] for _ in range(n)]
for i in range(n):
	v = 0
	for j in range(m):
		v = (v + 1) * (g[i][j] == '*')
		c[i][j] = v
	v = 0
	for j in range(m - 1, -1, -1):
		v = (v + 1) * (g[i][j] == '*')
		c[i][j] = min(c[i][j], v)
for j in range(m):
	v = 0
	for i in range(n):
		v = (v + 1) * (g[i][j] == '*')
		c[i][j] = min(c[i][j], v)
	v = 0
	for i in range(n - 1, -1, -1):
		v = (v + 1) * (g[i][j] == '*')
		c[i][j] = min(c[i][j], v)
for i in range(n):
	for j in range(m):
		if c[i][j] == 1:
			c[i][j] = 0
for i in range(n):
	v = 0
	for j in range(m):
		v = max(v - 1, c[i][j])
		if v:
			g[i][j] = '.'
	v = 0
	for j in range(m - 1, -1, -1):
		v = max(v - 1, c[i][j])
		if v:
			g[i][j] = '.'
for j in range(m):
	v = 0
	for i in range(n):
		v = max(v - 1, c[i][j])
		if v:
			g[i][j] = '.'
	for i in range(n - 1, -1, -1):
		v = max(v - 1, c[i][j])
		if v:
			g[i][j] = '.'
if all((g[i][j] == '.' for i in range(n) for j in range(m))):
	r = [(i + 1, j + 1, c[i][j] - 1) for i in range(n) for j in range(m) if c[i][j]]
	print(len(r))
	for t in r:
		print(*t)
else:
	print(-1)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
MAP = [list(input().strip()) for i in range(n)]
T0 = [[0] * (m + 1) for i in range(n + 1)]
T1 = [[0] * (m + 1) for i in range(n + 1)]
Y0 = [[0] * (m + 1) for i in range(n + 1)]
Y1 = [[0] * (m + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(m):
		if MAP[i][j] == '*':
			T0[i][j] = T0[i - 1][j] + 1
			Y0[i][j] = Y0[i][j - 1] + 1
for i in range(n - 1, -1, -1):
	for j in range(m - 1, -1, -1):
		if MAP[i][j] == '*':
			T1[i][j] = T1[i + 1][j] + 1
			Y1[i][j] = Y1[i][j + 1] + 1
ANS = [[0] * m for i in range(n)]
for i in range(n):
	for j in range(m):
		score = min(T0[i][j], T1[i][j], Y0[i][j], Y1[i][j])
		if score >= 2:
			ANS[i][j] = score
T0 = [[0] * (m + 1) for i in range(n + 1)]
T1 = [[0] * (m + 1) for i in range(n + 1)]
Y0 = [[0] * (m + 1) for i in range(n + 1)]
Y1 = [[0] * (m + 1) for i in range(n + 1)]
for i in range(n):
	for j in range(m):
		T0[i][j] = max(ANS[i][j], T0[i - 1][j] - 1)
		Y0[i][j] = max(ANS[i][j], Y0[i][j - 1] - 1)
for i in range(n - 1, -1, -1):
	for j in range(m - 1, -1, -1):
		T1[i][j] = max(ANS[i][j], T1[i + 1][j] - 1)
		Y1[i][j] = max(ANS[i][j], Y1[i][j + 1] - 1)
SUF = [['.'] * m for i in range(n)]
for i in range(n):
	for j in range(m):
		if T0[i][j] or T1[i][j] or Y0[i][j] or Y1[i][j]:
			SUF[i][j] = '*'
if SUF != MAP:
	print(-1)
else:
	ANSLIST = []
	for i in range(n):
		for j in range(m):
			if ANS[i][j] != 0:
				ANSLIST.append((i + 1, j + 1, ANS[i][j] - 1))
	print(len(ANSLIST))
	for ans in ANSLIST:
		print(*ans)


from collections import defaultdict, deque
from heapq import heappush, heappop
from math import inf
ri = lambda : map(int, input().split())

def solve():
	(n, m) = ri()
	A = [[0 for _ in range(m)] for __ in range(n)]
	left = [[0 for _ in range(m)] for __ in range(n)]
	right = [[0 for _ in range(m)] for __ in range(n)]
	up = [[0 for _ in range(m)] for __ in range(n)]
	down = [[0 for _ in range(m)] for __ in range(n)]
	for r in range(n):
		lst = input()
		for c in range(m):
			if lst[c] == '*':
				A[r][c] = left[r][c] = right[r][c] = up[r][c] = down[r][c] = 1
	for r in range(n):
		for c in range(1, m):
			if A[r][c]:
				left[r][c] += left[r][c - 1]
		for c in range(m - 2, -1, -1):
			if A[r][c]:
				right[r][c] += right[r][c + 1]
	for c in range(m):
		for r in range(1, n):
			if A[r][c]:
				up[r][c] += up[r - 1][c]
		for r in range(n - 2, -1, -1):
			if A[r][c]:
				down[r][c] += down[r + 1][c]
	res = []
	stars = 0
	ROWS = [[0 for _ in range(m)] for __ in range(n)]
	COLS = [[0 for _ in range(m)] for __ in range(n)]
	for r in range(n):
		for c in range(m):
			if A[r][c]:
				can = min(left[r][c], right[r][c], up[r][c], down[r][c])
				can -= 1
				if can > 0:
					stars += 1
					res.append((r + 1, c + 1, can))
				ROWS[r - can][c] += can
				if r + can + 1 < n:
					ROWS[r + can + 1][c] -= can
				COLS[r][c - can] += can
				if c + can + 1 < m:
					COLS[r][c + can + 1] -= can
	valid = [[False for _ in range(m)] for __ in range(n)]
	for r in range(n):
		curr = 0
		for c in range(m):
			curr += COLS[r][c]
			if curr > 0:
				valid[r][c] = True
	for c in range(m):
		curr = 0
		for r in range(n):
			curr += ROWS[r][c]
			if curr > 0:
				valid[r][c] = True
	for r in range(n):
		for c in range(m):
			if A[r][c] and (not valid[r][c]):
				print(-1)
				return
	print(stars)
	for (x, y, z) in res:
		print(x, y, z)
t = 1
while t:
	t -= 1
	solve()


import re
import sys
exit = sys.exit
from bisect import bisect_left as bsl, bisect_right as bsr
from collections import Counter, defaultdict as ddict, deque
from functools import lru_cache
cache = lru_cache(None)
from heapq import *
from itertools import *
from math import inf
from pprint import pprint as pp
enum = enumerate
ri = lambda : int(rln())
ris = lambda : list(map(int, rfs()))
rln = sys.stdin.readline
rl = lambda : rln().rstrip('\n')
rfs = lambda : rln().split()
mod = 1000000007
d4 = [(0, -1), (1, 0), (0, 1), (-1, 0)]
d8 = [(-1, -1), (0, -1), (1, -1), (-1, 0), (1, 0), (-1, 1), (0, 1), (1, 1)]
(m, n) = ris()
(m, n) = (m + 2, n + 2)
grid = ['.' * n]
grid += ['.' + rl() + '.' for _ in range(m - 2)]
grid += ['.' * n]
up = [[0] * n for _ in range(m)]
dw = [[0] * n for _ in range(m)]
lf = [[0] * n for _ in range(m)]
rg = [[0] * n for _ in range(m)]
rs = [[0] * n for _ in range(m)]
cs = [[0] * n for _ in range(m)]
for i in range(1, m - 1):
	for j in range(1, n - 1):
		if grid[i][j] == '*':
			up[i][j] = 1 + up[i - 1][j]
			lf[i][j] = 1 + lf[i][j - 1]
for i in range(m - 1, 0, -1):
	for j in range(n - 1, 0, -1):
		if grid[i][j] == '*':
			dw[i][j] = 1 + dw[i + 1][j]
			rg[i][j] = 1 + rg[i][j + 1]
ans = []
for i in range(1, m - 1):
	for j in range(1, n - 1):
		if grid[i][j] == '.':
			continue
		s = min(up[i - 1][j], dw[i + 1][j], lf[i][j - 1], rg[i][j + 1])
		if s == 0:
			continue
		ans.append((i, j, s))
		rs[i - s][j] += 1
		rs[i + s + 1][j] -= 1
		cs[i][j - s] += 1
		cs[i][j + s + 1] -= 1
for i in range(1, m - 1):
	for j in range(1, n - 1):
		rs[i][j] += rs[i - 1][j]
		cs[i][j] += cs[i][j - 1]
for i in range(1, m - 1):
	for j in range(1, n - 1):
		if grid[i][j] == '.':
			continue
		if rs[i][j] == 0 and cs[i][j] == 0:
			print(-1)
			exit()
print(len(ans))
for (i, j, s) in ans:
	print(i, j, s)