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.

Difficulty: introductory

Starter code:

Solutions:
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
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 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())
    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()

import sys
input = sys.stdin.readline

n,m=list(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)


# -*- coding: utf-8 -*-

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)


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)















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)














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)

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

print(len(ans))
for i in ans:print(*i)

def main():

    n,m = list(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(list(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(list(range(n))):
            if S[i][j] == '.':
                cnt = 0
            else:
                cnt += 1
                D[i][j] = cnt

    #print(L)
    #print(R)
    #print(U)
    #print(D)
    #T = [['.']*m for _ in range(n)]
    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

    #print(imosH)
    #print(imosV)

    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]

    #print(imosH)
    #print(imosV)

    #print(T)
    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)
                    return
    else:
        print(len(ans))
        for i in range(len(ans)):
            print(*ans[i])

def __starting_point():
    main()

__starting_point()