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 × 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 ⋅ 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 ⋅ m stars.

Input

The first line of the input contains two integers n and m (3 ≤ n, m ≤ 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 ≤ k ≤ n ⋅ 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.
import java.io.*;
import java.util.*;

public class tr2 {
	static PrintWriter out;
	static StringBuilder sb;
	static int inf =(int) 1e7;
	static ArrayList<Integer> primes;
	static int []si;
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		out = new PrintWriter(System.out);
		int n=sc.nextInt();
		int m=sc.nextInt();
		char [][] grid=new char[n][m];
		for(int i=0;i<n;i++)
			grid[i]=sc.nextLine().toCharArray();
		sb=new StringBuilder();
		int c=0;
		int [][] up=new int [n][m];
		int [][] down=new int [n][m];
		int [][] left=new int [n][m];
		int [][] right=new int [n][m];
		for(int j=0;j<m;j++) {
			int d=0;
			for(int i=0;i<n;i++) {
				if(grid[i][j]=='.')
					continue;
				d=1;
				while(i<n && grid[i][j]=='*')
					up[i++][j]=d++;
			}
		}
		for(int j=0;j<m;j++) {
			int d=0;
			for(int i=n-1;i>=0;i--) {
				if(grid[i][j]=='.')
					continue;
				d=1;
				while(i>=0 && grid[i][j]=='*')
					down[i--][j]=d++;
			}
		}
		for(int i=0;i<n;i++) {
			int d=0;
			for(int j=0;j<m;j++) {
				if(grid[i][j]=='.')
					continue;
				d=1;
				while(j<m && grid[i][j]=='*')
					left[i][j++]=d++;
			}
		}
		for(int i=0;i<n;i++) {
			int d=0;
			for(int j=m-1;j>=0;j--) {
				if(grid[i][j]=='.')
					continue;
				d=1;
				while(j>=0 && grid[i][j]=='*')
					right[i][j--]=d++;
			}
		}
		int [][] x=new int[n][m];
		int [][] y=new int[n][m];
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				if(grid[i][j]=='*') {
					int dd=Math.min(Math.min(up[i][j], down[i][j]), Math.min(left[i][j], right[i][j]))-1;
					if(dd>0) {
						sb.append((i+1)+" "+(j+1)+" "+dd+"\n");
						c++;
						x[i-dd][j]++;
						if(i+dd+1<n)
						x[i+dd+1][j]--;
						y[i][j-dd]++;
						if(j+dd+1<m)
						y[i][j+dd+1]--;
					}
				}
			}
		}
		for(int i=0;i<n;i++) {
			for(int j=1;j<m;j++) {
			   y[i][j]+=y[i][j-1];	
			}
		}
		for(int j=0;j<m;j++) {
			for(int i=1;i<n;i++) {
			   x[i][j]+=x[i-1][j];	
			}
		}
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				if((grid[i][j]=='*' && x[i][j]+y[i][j]>0) || (grid[i][j]=='.' && x[i][j]+y[i][j]==0)) {
					
				}
				else {
					System.out.println(-1);
					return;
				}
			}
		}
	    out.println(c);
	    out.println(sb);
		out.flush();
	}
	static void seive() {
		 si=new int [10000001];
		    primes=new ArrayList<>();
		    int N=10000001;
		    si[1]=1;
		    for(int i=2;i<N;i++) {
		    	if(si[i]==0) {
		    		si[i]=i;
		    		primes.add(i);
		    	}
		    	for(int j=0;j<primes.size() && primes.get(j)<=si[i] && (i*primes.get(j))<N;j++)
		    		si[primes.get(j)*i]=primes.get(j);
		    		
		    }
	}
	static public class Vector {

		double x, y; 

		Vector(double a, double b) { x = a; y = b; }

		Vector(Point a, Point b) { this(b.x - a.x, b.y - a.y); }

		Vector scale(double s) { return new Vector(x * s, y * s); }              //s is a non-negative value

		double dot(Vector v) { return (x * v.x + y * v.y); }

		double cross(Vector v) { return x * v.y - y * v.x; }

		double norm2() { return x * x + y * y; }

		Vector reverse() { return new Vector(-x, -y); }

		Vector normalize() 
		{ 
			double d = Math.sqrt(norm2());
			return scale(1 / d);
		}		
	}
     static	public class Line {

		static final double INF = 1e9, EPS = 1e-9;
		
		double a, b, c;
		
		Line(Point p, Point q)
		{
			if(Math.abs(p.x - q.x) < EPS) {	a = 1; b = 0; c = -p.x;	}
			else
			{
				a = (p.y - q.y) / (q.x - p.x);
				b = 1.0;
				c = -(a * p.x + p.y);
			}
						
		}
		
		Line(Point p, double m) { a = -m; b = 1; c =  -(a * p.x + p.y); } 
		
		boolean parallel(Line l) { return Math.abs(a - l.a) < EPS && Math.abs(b - l.b) < EPS; }
		
		boolean same(Line l) { return parallel(l) && Math.abs(c - l.c) < EPS; }
		
		Point intersect(Line l)
		{
			if(parallel(l))
				return null;
			double x = (b * l.c - c * l.b) / (a * l.b - b * l.a);
			double y;
			if(Math.abs(b) < EPS)
				 y = -l.a * x - l.c;
			else
				y = -a * x - c;
			
			return new Point(x, y);
		}
		
		Point closestPoint(Point p)
		{
			if(Math.abs(b) < EPS) return new Point(-c, p.y);
			if(Math.abs(a) < EPS) return new Point(p.x, -c);
			return intersect(new Line(p, 1 / a));
		}
				
	}
	static  public class Polygon { 
		// Cases to handle: collinear points, polygons with n < 3

		static final double EPS = 1e-9;
		
		Point[] g; 			//first point = last point, counter-clockwise representation
		
		Polygon(Point[] o) { g = o; }

		double perimeter()
		{
			double sum = 0.0;
			for(int i = 0; i < g.length - 1; ++i)
				sum += g[i].dist(g[i+1]);
			return sum;
		}
		
		double area() 		//clockwise/anti-clockwise check, for convex/concave polygons
		{
			double area = 0.0;
			for(int i = 0; i < g.length - 1; ++i)
				area += g[i].x * g[i+1].y - g[i].y * g[i+1].x;
			return Math.abs(area) / 2.0;			//negative value in case of clockwise
		}

		boolean isConvex()
		{
			if(g.length <= 3) // point or line
				return false;
			boolean ccw = Point.ccw(g[g.length - 2], g[0], g[1]);		//edit ccw check to accept collinear points
			for(int i = 1; i < g.length - 1; ++i)
				if(Point.ccw(g[i-1], g[i], g[i+1]) != ccw)
					return false;
			return true;
		}
		
		boolean inside(Point p)	//for convex/concave polygons - winding number algorithm 
		{
			double sum = 0.0;
			for(int i = 0; i < g.length - 1; ++i)
			{
				double angle = Point.angle(g[i], p, g[i+1]);
				if((Math.abs(angle) < EPS || Math.abs(angle - Math.PI) < EPS) && p.between(g[i], g[i+1]))
					return true;
				if(Point.ccw(p, g[i], g[i+1]))
					sum += angle;
				else
					sum -= angle;
			}

			return Math.abs(2 * Math.PI - Math.abs(sum)) < EPS;		//abs makes it work for clockwise
		}
		/*
		 * Another way if the polygon is convex
		 * 1. Triangulate the poylgon through p
		 * 2. Check if sum areas == poygon area
		 * 3. Handle empty polygon
		 */
		
		Polygon cutPolygon(Point a, Point b)	//returns the left part of the polygon, swap a & b for the right part
		{
			Point[] ans = new Point[g.length<<1];
			Line l = new Line(a, b);
			Vector v = new Vector(a, b);
			
			int size = 0;
			for(int i = 0; i < g.length; ++i)
			{
				double left1 = v.cross(new Vector(a, g[i]));
				double left2 = i == g.length - 1 ? 0 : v.cross(new Vector(a, g[i+1]));

				if(left1 + EPS > 0)	
					ans[size++] = g[i];
				if(left1 * left2 + EPS < 0)
					ans[size++] = l.intersect(new Line(g[i], g[i+1]));
			}
			
			if(size != 0 && ans[0] != ans[size-1])	//necessary in case g[0] is not in the new polygon
				ans[size++] = ans[0];
			return new Polygon(Arrays.copyOf(ans, size));
		}

		static Polygon convexHull(Point[] points)	//all points are unique, remove duplicates, edit ccw to accept collinear points
		{
			int n = points.length;
			Arrays.sort(points);
			Point[] ans = new Point[n<<1];
			int size = 0, start = 0;

			for(int i = 0; i < n; i++)
			{
				Point p = points[i];
				while(size - start >= 2 && !Point.ccw(ans[size-2], ans[size-1], p))	--size;
				ans[size++] = p;
			}
			start = --size;

			for(int i = n-1 ; i >= 0 ; i--)
			{
				Point p = points[i];
				while(size - start >= 2 && !Point.ccw(ans[size-2], ans[size-1], p))	--size;
				ans[size++] = p; 
			}
			//			if(size < 0) size = 0			for empty set of points
			return new Polygon(Arrays.copyOf(ans, size));			
		}

		Point centroid()		//center of mass
		{
			double cx = 0.0, cy = 0.0;
			for(int i = 0; i < g.length - 1; i++)
			{
				double x1 = g[i].x, y1 = g[i].y;
				double x2 = g[i+1].x, y2 = g[i+1].y;

				double f = x1 * y2 - x2 * y1;
				cx += (x1 + x2) * f;
				cy += (y1 + y2) * f;
			}
			double area = area();		//remove abs
			cx /= 6.0 * area;
			cy /= 6.0 * area;
			return new Point(cx, cy);
		}
	}
	static public class Point implements Comparable<Point>{

		static final double EPS = 1e-9;

		double x, y;                  

		Point(double a, double b) { x = a; y = b; }  
		
		public int compareTo(Point p)
		{
			if(Math.abs(x - p.x) > EPS) return x > p.x ? 1 : -1;
			if(Math.abs(y - p.y) > EPS) return y > p.y ? 1 : -1;
			return 0;
		}
		
		public double dist(Point p) { return Math.sqrt(sq(x - p.x) + sq(y - p.y)); }
		
		static double sq(double x) { return x * x; }
		
		Point rotate(double angle)
		{
			double c = Math.cos(angle), s = Math.sin(angle);
			return new Point(x * c - y * s, x * s + y * c);
		}
		// for integer points and rotation by 90 (counterclockwise) : swap x and y, negate x
		
		Point rotate(double theta, Point p)			//rotate around p
		{
			Vector v = new Vector(p, new Point(0, 0));
			return translate(v).rotate(theta).translate(v.reverse());
		}
		
		Point translate(Vector v) { return new Point(x + v.x , y + v.y); }
		
		Point reflectionPoint(Line l) 	//reflection point of p on line l
		{
			Point p = l.closestPoint(this);
			Vector v = new Vector(this, p);
			return this.translate(v).translate(v);
		}
		
		boolean between(Point p, Point q)
		{
			return x < Math.max(p.x, q.x) + EPS && x + EPS > Math.min(p.x, q.x)
					&& y < Math.max(p.y, q.y) + EPS && y + EPS > Math.min(p.y, q.y);
		}
		
		//returns true if it is on the line defined by a and b
		boolean onLine(Point a, Point b) 
		{
			if(a.compareTo(b) == 0) return compareTo(a) == 0;
			return Math.abs(new Vector(a, b).cross(new Vector(a, this))) < EPS;
		}
		
		boolean onSegment(Point a, Point b)
		{
			if(a.compareTo(b) == 0) return compareTo(a) == 0;
			return onRay(a, b) && onRay(b, a);
		}
		
		//returns true if it is on the ray whose start point is a and passes through b
		boolean onRay(Point a, Point b)
		{
			if(a.compareTo(b) == 0) return compareTo(a) == 0;
			return new Vector(a, b).normalize().equals(new Vector(a, this).normalize());	//implement equals()
		}
		
		// returns true if it is on the left side of Line pq
		// add EPS to LHS if on-line points are accepted
		static boolean ccw(Point p, Point q, Point r)
		{
			return new Vector(p, q).cross(new Vector(p, r)) > 0;
		}
		
		static boolean collinear(Point p, Point q, Point r)
		{
			return Math.abs(new Vector(p, q).cross(new Vector(p, r))) < EPS;
		}
		
		static double angle(Point a, Point o, Point b)  // angle AOB
		{
			Vector oa = new Vector(o, a), ob = new Vector(o, b);
			return Math.acos(oa.dot(ob) / Math.sqrt(oa.norm2() * ob.norm2()));
		}
		
		static double distToLine(Point p, Point a, Point b) //distance between point p and a line defined by points a, b (a != b)
		{
			if(a.compareTo(b) == 0) return p.dist(a);
			// formula: c = a + u * ab
			Vector ap = new Vector(a, p), ab = new Vector(a, b);
			double u = ap.dot(ab) / ab.norm2();
			Point c = a.translate(ab.scale(u)); 
			return p.dist(c);
		}
		// Another way: find closest point and calculate the distance between it and p

		static double distToLineSegment(Point p, Point a, Point b) 
		{
			Vector ap = new Vector(a, p), ab = new Vector(a, b);
			double u = ap.dot(ab) / ab.norm2();
			if (u < 0.0) return p.dist(a);
			if (u > 1.0) return p.dist(b);        
			return distToLine(p, a, b); 
		}
		// Another way: find closest point and calculate the distance between it and p
	}
	static long mod=(long) 1e9+7;
     static long fac (int n) {
    	 if(n==0)
    		 return 1;
    	 if(n==1)
    		 return 1;
    	 long ans=1;
    	 for(int i=1;i<=n;i++)
    		 ans=(i%mod*ans%mod)%mod;
    	 return ans%mod;
     }
    	 static int gcd(int a, int b) {
     
		if (b == 0) {
			return a;
		}
		return gcd(b, a % b);
	}
    static class pair implements Comparable<pair>{
    	int num;
    	int v;
    	pair(int n,int v){
    		num=n;
    		this.v=v;
    	}
    	public String toString() {
    		return num+" "+v;
    	}
	
		public int compareTo(pair o) {
			return o.v-v;
		}
    }
	static class unionfind {
		int[] p;
		int[] size;

		unionfind(int n) {
			p = new int[n];
			size = new int[n];

			for (int i = 0; i < n; i++) {
				p[i] = i;
			}
			Arrays.fill(size, 1);
		}

		int findSet(int v) {
			if (v == p[v])
				return v;
			return p[v] = findSet(p[v]);
		}

		boolean sameSet(int a, int b) {
			a = findSet(a);
			b = findSet(b);
			if (a == b)
				return true;
			return false;
		}

		int max() {
			int max = 0;
			for (int i = 0; i < size.length; i++)
				if (size[i] > max)
					max = size[i];
			return max;
		}

		void combine(int a, int b) {
			a = findSet(a);
			b = findSet(b);
			if (a == b)
				return;
			if (size[a] > size[b]) {
				p[b] = a;
				size[a] += size[b];

			} else {
				p[a] = b;
				size[b] += size[a];
			}
		}
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}

		public Scanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public char nextChar() throws IOException {
			return next().charAt(0);
		}

		public Long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}
}